(この記事内では、点灯している点を「黒い点」、消灯している点を「白い点」と呼びます。英語の公式解説内でも同じ表現が用いられています。)
まず、この操作は結局どこに何回操作をかけたか、更に言うと、そこに奇数回操作をかけたか偶数回操作をかけたかのみが結果に影響するので、ある操作をかけられた盤面に対してもう一度同じ操作をかけてやると、元の盤面に戻すことができます。
よって、ある盤面と、そこから何回か操作をかけた盤面とは等価で、どちらからでも同じ元の盤面を復元できます。
次に、黒い点を(斜交座標上の)ある直線x+y=c(cは定数)に集めることを考えます。
ここで、斜交座標上での直線を参考までにいくつか例として示します。座標上での直線とやっていることは変わらないですが、x軸とy軸が斜めに交わっているというイメージでよいです。
さて、ある点をある直線上に移動させると、何が起こるでしょうか?
例として、(-2,-2)上の黒い点を操作によってx+y=1に移動させます。
具体的に、まず、x+y=-4上の点全てに対して、その点を左下とする操作をかけると、点が全てx+y=-3上に来ます。次に、x+y=-3上で同じ操作をすると点がすべてx+y=-2上に来ます。これを繰り返すと、任意のx+y=c(cは定数)に点を移動させることができます。具体的には画像のような感じになります。
図を見て考察すると、点を動かした結果は、偶奇版パスカルの三角形(シェルピンスキーのギャスケット)のある1層となることがわかります。ちなみに、この結果は一意に定まります。なぜなら、直線上のある一点を丁度別の一点に変換することはできない(操作後の黒い点と直線の距離を考えるとわかります)からです。
これを、複数の点でやることを考えます。複数の点でやった結果は、それぞれの点についてやった結果を足し算して偶奇を見ればいいことがわかります。(この図はSample1の途中経過)
ここで、x+y=cのcを十分大きくとれば、全ての点を直線の左下に来るように設定することができます。
そして、全ての点を一直線上に移動させた結果である、直線上に乗った点のパターンは、パスカルの三角形のある一層となる(何故なら、一番最初の始点が一点であるから)のでそれを解析すれば原点(一番最初にともっていたランプの位置)を求めることができます。
ここで、x+y=cの直線上の一番左上の点と右下の点、正確には一番xが小さい点と大きい点だけ分かれば、原点が求められます。
しかし、座標の値が非常に大きいので、直線状に移すシミュレートを愚直に実行するわけにはいきません。そこで、一番xが小さい点と大きい点だけ分かれば、原点が求められるという性質を利用します。
ここで、「ある点Pの色を求める」というクエリを実装しておきます。
これは、パスカルの三角形の性質より全ての点についてそこを始点としてPに向かう経路のパターン数の偶奇がわかればそれを足し算することによってPの色が求解出来るので、nCrの偶奇が高速に求められればクエリは実装出来ます。
このクエリは、Lucasの定理を利用すると容易に実装出来ます。Lucasの定理については Lucasの定理とその証明 | 高校数学の美しい物語 を参照してください。
結論だけ言うと、nCrのn,rのある同じ位のbitであるnb,rbであって、nb=0,rb=1となるものが存在すれば、nCrは偶数、そうでなければ奇数となります。
これで、ある点の色を求めるクエリが実装出来ました、
問題の本体に戻って、「x+y=c上に黒い点を1つ見つけられた」とします。すると、シェルピンスキーのギャスケットの対称性(パスカルの三角形の性質とフラクタル | 高校数学の美しい物語のイメージがあると理解しやすい。2^k+1層目に距離2^kだけ離されて三角形が配置されることから以下のアルゴリズムが示せる。)から、以下のアルゴリズムでx座標最大の点(最も右下の点)を求められます。
1.起点のx座標をVとする。
2.k=60とし、x座標がV+2^kとなるx+y=c上の点が黒かどうか判定し、黒ならVに2^kを加算する。
3.これをk=59,58,...,0まで繰りかえす。
最も左上の点も同様に求められます。
これで、cの値と最も(左上/右下)の点のx座標が分かれば、原点をたどることができ、この問題を解くことができます。
さて、どのようにすれば一つの黒い点を見つけられるでしょうか?(黒い点はパスカルの三角形の高さが増すごとに疎になっていくので乱択では厳しいです)
C1:
C1では、ここから先はウィニングランです。(X,0)が原点なら、十分大きな(C,0)では、かならずこの点は黒かつ右下端となります。これはパスカルの三角形の性質から明らかです。この点を使えば求解できます。
https://atcoder.jp/contests/wtf19-open/submissions/4380752
C2:
解説によると、以下の方針は内部テスト中にyosupo氏に発見されたそうです。
まず、x+y=c上の黒い点をxの(mod 3)の値別に振り分けます。すると、これもパスカルの三角形の性質上、(x座標)≡r(mod 3)を満たす黒い点が奇数個存在するようなrが少なくとも1つ存在します。何故なら、偶奇版パスカルの三角形ではある層にある黒い点の数が必ず2^k(kは非負整数)の形で表せるからです。(2019/10/02追記:ここ嘘でした、以下に正しい説明を続けます)この理由を説明します。
ここでもパスカルの三角形の性質とフラクタル | 高校数学の美しい物語の図を見てもらうと分かりやすいかもしれません。
「ある層のr=(0,1,2)について集計したとき、黒い点の個数(の偶奇)において(奇,奇,偶),(奇,偶,奇),(奇,偶,偶),(偶,奇,奇),(偶,奇,偶),(偶,偶,奇)のいずれかが成立する」ことを状態Xと呼びましょう。状態Xならば条件を満たすrが1つは存在します。(逆は(奇,奇,奇)を除外しているため成立しません。)
まず、1,2層目については明らかに状態Xです。
ここで、3,4層目について考えてみましょう。1,2層目の三角形と同じものを距離2だけ離して配置したような感じになっていますね。ということは、3層目については、1層目の(例えば)(奇,偶,偶)を距離2だけずらして合成、つまり、(奇,偶,偶)+(偶,偶,奇)=(奇,偶,奇)という関係になっているというわけです。距離1または2ずらして合成すると、必ず奇+偶=奇という関係がどこかしらで成立します(奇と偶のうち少ないほうに着目するとわかりやすい)。逆に、同じ偶奇同士が足しあわされて偶数になるといったこともどこかしらで成立します(奇と偶のうち多いほうに着目するとわかりやすい)。よって、状態Xを距離1または2ずらして合成しても状態Xです。なお、距離3ずらして合成する(=全くずれていない)と全てが偶数になってしまいます。距離3以上ずらして合成する場合、距離dずらすときには距離d%3ずらすときと同じ操作を考えればいいこともわかります。
今回の問題の場合、三角形の頂点を配置するタイミングが2^k+1層目になることに留意すると、三角形同士の距離は必ず2^kとなります。そして、これは3の倍数たりえません。なので、常に1つは条件を満たすrが存在することが数学的帰納法を用いて示すことができます。
このrが分かれば、直線に黒い点が全て入るような十分大きい範囲をとって、その範囲を二分探索のように二分割してどちらに奇数個の条件を満たす点が含まれるか?ということを考えることを再帰的に繰り返せば、やがてひとつの黒い点にたどり着きます。
ここで、パスカルの三角形の(k+1)段目のある範囲に含まれる(x座標)≡r(mod 3)を満たす点の個数を数えることは以下の問題が解ければ解けます。
ある自然数である定数kが存在する。0~mのある整数Xのうち、Xを3で割った余りがrであるようなもの かつ kのbit表記において0である桁全てについてXでのその桁が1とならないようなXはいくつ存在するか?
これは、dp[bitの位置][mod 3の値][以下のbit次第でmを超えうるか]という桁DPをすれば解くことができます。
これをN点すべてについて計算し、その結果を各点のx座標を3で割った余りによって調整して合成すれば、その範囲での黒い点の数の偶奇を求めることができます。(なぜなら、加わった操作の回数の総和を求めることができれば操作ごとに黒い点が1だけ増減するので偶奇が確定するから)
https://atcoder.jp/contests/wtf19-open/submissions/4391429
