AtCoder Grand Contest 061

　A一完で青色に落ちました。時間ギリギリでAを解けたのは嬉しかったけど……。

コンテストへのリンク

コンテスト後のツイート

AtCoder Grand Contest 061 終了10分前にAをAC。
A 実験して法則を見つける。大体、bitの立っている位置がN-2の部分集合になっている偶数xでxとx+1の交換が起きる、という感じ。これを、(N-2) & x!=0だと思いこみ、ずっと迷走した。N<=27まで答えが合うのが罠だった。

— titia (@titia_til) February 12, 2023

A - Long Shuffle

　考察過程を書いておきます。

・実験する。N<30くらいについて、手順が終わった後Aがどうなるかを見るが、何も分からない。

・さらに、どんな交換が行われているかも出力してみる。すると、部分部分が打ち消し合いそうだと分かる。

・打ち消し合っているところを消去するコードを書く。すると、交換が各index iについての交換が高々一回だということや、偶数のときは偶数番目しか交換されないこと、2ベキ+2のNについては、最初と最後の二回の交換で表せることに気付く。

・（xをxとx+1番目の交換とすると、たとえば「1 3 1 3」という交換なら打ち消し合う、と思っていたが、間違いなのでは？　という疑問が生じる。最初に出力したAの配列と照らし合わせたら、間違いではありませんでした）

・偶数の場合を考える。交換されるindexを書くと、

-N=10：0 8

-N=12：0 8 2 10

-N=14：0 8 4 12

-N=16：0 8 4 12 2 10 6 14

-N=18：0 16

　のようになっている。

　よく考えると、これは全て偶数なので、ソートして良い。

　そして、10<=N<18ならば、k=8として、(N-2-k) & y != 0 or y=0となるようなyとy+kで交換されるのでは？　と予想。

　上の例だと、

-N=10のときk=0：0, 8

-N=12のときk=2：0, 2, 8, 10

-N=14のときk=4：0, 4, 8, 12

-N=16のときk=6：0, 2, 4, 6, 8, 10, 12, 14

　となりOK。

・Nが奇数の場合は、N-1のときの交換の後で、「N-1の交換場所たちに+1した場所」で交換されると気付く。

→これで解けた！　と思うがWA。

・間違っていたところ一つ目。y<=x-kという条件が必要だった

→まだWA

・二つ目。(N-2-k) & y != 0ではなく、(N-2-k) & y == yが条件だった。これはN=28で実験して気付いた。

→やっとAC

B - Summation By Construction

　解説放送を見てAC。

　この問題はコンテスト中読んでいないので何ともいえない。思いつけるかどうかなので、コンテスト中この問題にかけて勝つ可能性もあったとは思うけど、そういう賭けに勝ったことってあまりないからねぇ……。Aが速く解けていたらそういう賭けをしても良かっただろうけど。