AtCoder ABC334のB問題
リンクはこちら
AtCoderの解説ではこのコードで正解すると記載されているのだが、例えば、5,3,-1,6と入力するとて計算では「2」となるのに出力は「3」となる。問題的には「3」であっているそうなのだが、なぜ「3」になるのかを教えていただきたい。
a, m, l, r = map(int, input().split())
l -= a
r -= a
print(r//m - (l-1)//m)
※なお、
print(r//m)
print(- (l-1)//m)
と分けて実行したところ
0
2
であった。
r//m - (l-1)//mは、最後に間の-を計算します。
なので、1//3 - (-7)//3 = 0 - (-3) = 3
ちなみに、-7 = (-3)*3 + 2なので、(-7)//3 = -3です。
- (l-1)//mは、先頭から順に計算します。
なので、-(-7)//3 = 7//3 = 2
つまり、確認のためのprint文の２番目をprint((l-1)//m)としてみてください。
-1から6の範囲で、5を基点に3ずつ木を設置するなら-1, 2, 5だから、答えは3で正しいんじゃない？
むしろ、何を根拠に r//m - (l-1)//m という式を立てたのかを説明してほしい。その中に勘違いがあると思うよ。
例えば、点A,L,Rの座標をa=5,l=11,r=15、間隔m=3とする。
点Aの座標がa=0になるように平行移動すると、点L,Rの座標はl=6,r=10となり、間隔はm=3のまま。
原点からRまでに木は10//3 + 1本。(+1は原点の分)
原点からLの１つ手前までに木は(6-1)// + 1本。(LまでにするとLの分まで引きすぎてしまうから)
だから、LとRの間には、
(10//3 + 1) - {(6-1)//3 + 1} = 10//3 - (6-1)//3本の木があることになる。
一般化すると、平行移動後の座標l,rを用いて、本数はr//m - (l-1)//mで求めることができる。
例えば、点A,L,Rの座標をa=5,l=11,r=15、間隔m=3とする。
点Aの座標がa=0になるように平行移動すると、点L,Rの座標はl=6,r=10となり、間隔はm=3のまま。
原点からRまでに木は10//3 + 1本。(+1は原点の分)
原点からLの１つ手前までに木は(6-1)// + 1本。(LまでにするとLの分まで引きすぎてしまうから)
ここまではわかる
そこから先がわからん
その理論は、以下のように基準からみてLとRがどちらか片方に偏ってれば成り立つと思う。
---基準 --- L --- R ---
--- L --- R --- 基準 ---
ただ、以下のように基準からみてLとRが左右に散っている場合成り立たなくない？
--- L ---- 基準 ---- R ----
こういう場合は別の補正が必要になるんじゃない？
r//m（原点を除く右分） - l//m（原点を除く左分） + 1（原点）
--- L ---- 基準 ---- R ----
こういう場合は別の補正が必要になるんじゃない？
r//m（原点を除く右分） - l//m（原点を除く左分） + 1（原点）
はい、この場合は、３つの部分の和だから、
r//m（原点を除く右分） + [-{(l-1)//m} - 1]（原点を除く左分） + 1（原点）
となりますので、同じ結果になります。
原点を除く左分については、例えば、m=5として
l |
... | -12 | -11 | -10 | -9 | - 8 | -7 | -6 | -5 | -4 | -3 | ... |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
-{l//5} |
... | 3 | 3 | 2 | 2 | 2 | 2 | 2 | 1 | 1 | 1 | ... |
-{(l-1)//5} |
... | 3 | 3 | 3 | 2 | 2 | 2 | 2 | 2 | 1 | 1 | ... |
木の本数 |
... | 2 | 2 | 2 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | ... |
となることから、木の本数は-{(l-1)//m} - 1となることがわかります。
@ta282ji
Questioner
すみません。根本的に数学的な理解が足りていなかっただけみたいで、先ほど解決しました。
みなさんご協力ありがとうございました！
この問題、問題文に難がありますね。「今から、Aを基点にしてMmおきに」と書かれているので、Ｍが正なら東向き、Mが負なら西向きに、Aから一方向に移動すると読めます。しかし回答例では東西両方向に移動している。回答例を読めば両方向にツリーを植えることは理解はできますが、日本語がおかしいです。
