競技プログラミング用 知識集積所
ABC429D - On AtCoder Conference
最終更新：
sport_programming
-
view
問題
必要知識
B以下レベルの内容は省略
考え方
この手の問題だと、人数つまりNの大きさに耐えられるように工夫するところだが、今回はもっと大問題が存在する。
高橋君のスタート地点はMヶ所、つまり最大1兆か所存在するため、1つ1つをどれだけ高速に求めても焼け石に水。
つまり、必要とされる工夫は、複数のスタート地点からの値をまとめて求めることである。
高橋君のスタート地点はMヶ所、つまり最大1兆か所存在するため、1つ1つをどれだけ高速に求めても焼け石に水。
つまり、必要とされる工夫は、複数のスタート地点からの値をまとめて求めることである。
とりあえず人の番号は関係なさそうなので、全員を位置でソートして考える。
最初の人が10にいて、次の人が20にいるとしよう。
この場合、10.5からスタートしても19.5からスタートしても、どこで誰に合ってどこで止まるかは完全に同じである。
つまり、10.5スタートの場合の値を20-10=10倍してしまえば、この10個のスタート地点の分をまとめて計算できることになる。（座標圧縮※と同じ考え方）
この方針であれば、Xの値を求める回数はN回で済むため、間に合う希望が見えてくる。
最初の人が10にいて、次の人が20にいるとしよう。
この場合、10.5からスタートしても19.5からスタートしても、どこで誰に合ってどこで止まるかは完全に同じである。
つまり、10.5スタートの場合の値を20-10=10倍してしまえば、この10個のスタート地点の分をまとめて計算できることになる。（座標圧縮※と同じ考え方）
この方針であれば、Xの値を求める回数はN回で済むため、間に合う希望が見えてくる。
しかし、N回それぞれ愚直に求めては、O(N^2)でまだ間に合わない。
そこで、池の周りに人を2周分並べることを考える。
例えばM=20で、A={5,8,12}である場合、これを{5,8,12,25,28,32,45}と2周分（+番兵として3周目の1人目まで）にしてしまう。
すると、スタート地点が大きくなるほど終端も大きくなる単調性から、どの人まで会うのかを尺取法で求めていくとO(N)でXを1周分を調べきることができる。
そこで、池の周りに人を2周分並べることを考える。
例えばM=20で、A={5,8,12}である場合、これを{5,8,12,25,28,32,45}と2周分（+番兵として3周目の1人目まで）にしてしまう。
すると、スタート地点が大きくなるほど終端も大きくなる単調性から、どの人まで会うのかを尺取法で求めていくとO(N)でXを1周分を調べきることができる。
また、実は1周の全ての場所から調べさえすればよく、問題文通りに0.5から調べる必要はない。
つまり、先ほどの例の場合で0.5から19.5を調べる代わりに5.5から24.5の範囲で調べてもよい。
人がいないところが区間の端にならないのでコードを書きやすくなる。
つまり、先ほどの例の場合で0.5から19.5を調べる代わりに5.5から24.5の範囲で調べてもよい。
人がいないところが区間の端にならないのでコードを書きやすくなる。
