pretestはCまでの四完だったが、システムテストでCが落ちてしまった。
C. Strange Shuffle
詐欺師（impostor）の周囲の値が変わっていくことに着目。右側はkより大きく、左側はkより小さくなる。「kでない箇所」は、左右一個ずつ伝搬していくので、kでない場所を探してから二分探索すれば良い。
-1～+１、-2～+2、と伝搬範囲は広がるので、その範囲ずつ（つまり、大体2*ターン数）移動させていけば良い。
ただし、詐欺師自身の値は変わらないこと、及び、最終的に変化しない状態になったとき、kの箇所は、詐欺師のものともう一つある可能性があることに注意しなくてはいけない。
自分のシステムテストで落ちた実装は、n=4, k=2で、「2 3 2 1」となった最終状態でkでない箇所を探して、1と3を聞き続けるものになってしまっていた。2*ターン数ずつ移動させていたので、その二つしか聞けない！
なので、移動する数を「1*ターン数」や「2*ターン数-1」に直したらACできました。
なお、厳密にはこれでもHack caseがあるかもしれない。後半の二分探索パートでは、kなものを見つけたらただちにそれを答えとして出力するようにしているけど、「もう一つのk」がたまたま当たってしまうことはありそう。（本当にHack caseがあるかは分かってないです）
多分、二分探索パートでkの箇所が見つかったとき、左右の数字も調べるようにすれば、そのケースも除外できるはず。
0 件のコメント:
コメントを投稿