1日に2本も記事を書くなんて珍しいな！ クリスマスイブだしな！
ってなわけで書いてみる！
昨日の ABC334-B ですが、ABCのB問題にしては「数学」をしましょうって感じでつらかったと感じた人も多かったのではないでしょうか
ゴリもそこそこ混乱しました
そこで、
- 場合分けをしない
- 数学的な頭をできるだけ使わない
解き方を考えてみました
「できるだけ」なので、これでも難しい可能性もありますし、もっと良い方法もあるかもしれません。
図をかいてみたので数学の頭でなく感覚でつかんでもらえるとうれしいです！
問題概要
数直線があります。座標を起点に、
おきにクリスマスツリーが置かれます。座標
の間 (両端も含む、
) に、クリスマスツリーは何本ありますか？
は クソデカなのでループを使ってはいけません。
ABC334-B リンク
ゴリの考えたさいきょうの解き方
3ステップあります
1. 
を 
の位置に平行移動させる
公式解法の考え方も初手これでした。
(ゴリはコンテスト中は を
のところに移動してしまったためちょっと大変でした)
これをすると、クリスマスツリーの位置が の倍数のところになるので、かなり見通しがよくなります。 (本番で思いつきたかった...)
なお、必ずしもこの図の通りではありません ( が
の右側にあったり、
が
の左側にあったりします) が、いずれであっても以降の考え方を適用できます
2. 
を、
で割る！
で割ります！
これをすることによって、世界全体が になります！
下の図のように、を中心に、世界がぐにゃっと縮みます！
これによって、座標ごとに生えていたクリスマスツリーは、座標
ごとに生えていることになり、
つまり 整数の座標に 生えていることになります！
ただし、注意点として、や
は
、
といった 有理数となります (整数とは限らない)
(さらに実装上の注意なのですが、Pythonは L/M のように演算すると float型となり、精度が足りなくてWAとなります、回避する方法を後述します)
3. 
を切り上げ、
を切り捨てし、整数にする
と
が中途半端な位置にあるので、それぞれ切り上げ・切り捨てし、整数にしましょう！
これによりと
の間にいくつ整数があるか、計算できます！
これでほぼ答えは出ているのですが、最後に注意としては
クリスマスツリーはと
の両端を数えるので、
R-L で求まる距離に 1 を足しましょう！
(上の図だと、 は4だけど、整数は端点を含むと5つある)
ACコード (その1)
A,M,L,R = map(int,input().split()) L -= A R -= A from decimal import Decimal L = Decimal(L) / Decimal(M) R = Decimal(R) / Decimal(M) from math import ceil,floor L = ceil(L) R = floor(R) print(R - L + 1)
- 2～3行目で
LとRを平行移動しています - 4～6行目で
LとRをそれぞれMで割っています
(先述の通り、単にL/Mなどとすると精度がたりないので、Decimalで精度の良い計算をしています) - 7～9行目で切り上げ、切り捨てをしています
ACコード (その2)
A,M,L,R = map(int,input().split()) L -= A R -= A from fractions import Fraction L = Fraction(L, M) R = Fraction(R, M) from math import ceil,floor L = ceil(L) R = floor(R) print(R - L + 1)
その1とほぼ同じですが、2. のところは Fraction でもできます！
おわり
もっとシンプルな解法などあれば教えてくださるとうれしいです！
