AtCoder Grand Contest 035

結果

　A,Bの2完。順位は悪くなかったしレートも上がったけど嘘解法もありC問題を解けず、反省点は多かった。

A問題

　300点という見た目に惑わされて「簡単に解けるはずなのに全然わからない」と焦るのもいい加減やめよう。確かAGCの300点はABCの300点とは違うと明言されていた気がする。

　周期3でループする感じになることに気づいてやや安心したが実装が上手くできなくてひどかった。各数字の出現回数をmapに詰めてごちゃごちゃ場合分けしてゴリ押しして通したが、よくこれでWA出さなかったものだ。と思って今冷静に見るとどうも間違っているようだ。自分のプログラムではが3の倍数で要素の種類が2種類以上のときは、数列全体のXORが0ならばYesとしているが、それでは次のようなパターンで明らかにYesになってしまう。

6
1 2 4 1 2 4

　他の人のACしたコードで試してみるとちゃんとNoになった。テストケースが弱かった？ なんにしても運が良かっただけ……。

　提出

B問題

　手元でいろんな例を考えると

1. 辺の数は偶数じゃないとダメそう
2. 次数が1のノードは吸い込む側にしかなれない
3. 上の二つに気をつけるとわりと適当に組み始めてもなんとかなる

ということに気づいて、じゃあ次数の小さい順にpriority_queueから取り出して適当に辺を繋いでいくことを繰り返していけばいいんじゃねというコードを出したら通ってしまった。自分の解法の正当性がよくわからないが、解説PDFとやや近い考え方ではあるんだろうか。はっきりとはわからない。

　提出

C問題

　まず構築可能/不可能の条件だけ考えて、2の冪乗+1だけが可能とか、奇数なら可能とかいろいろ考えつつassert仕込んだ提出をして、結局2の冪乗だけNGであると把握した。構築可能な場合、の偶奇で場合分けして、奇数の場合は4以降の数字をで2個セットにして１にくっつければ良くて、というところまではわかったのに偶数の処理がわからなくて結局時間切れ。最後終了3分前に偶数のときは4,5,6をセットにして3にくっつければ消えそうと思ってコード出したときは心拍数めちゃ上がってたけど全然違った。そもそも3にくっつけてもダメだし7,8が組になってしまう時点で論外なのはすぐ気づきたかった。

　惜しかったという感触はあったけど、しかし終了後に解説PDFを読んでも偶数の場合の処理がすぐには理解できなかったのであと10分,20分あっても実は解けなかったかもしれない。ではなくの方にくっつけて、そうすると偶数も奇数もに全部くっつくからそこでが適当な3つ組から構築可能なんだな。やはりすぐ思いつけた自信はないので仕方ないか。

　提出

感想

　今回かなりパズル要素が強い回だと感じた(構築だから？)。その分かわからないけどよくわからない抜け道も発生して順位表が荒れると。いつものAGCといえばそうなのかもしれないが……。自分に関して言えばAは嘘解法、Bは無根拠無証明で通しただけと動きがひどかった。幸運に恵まれて結果自体はいいペースで行っていたのに、まともに解けそうだったC問題をきちんと仕留めきれないようでは。相手のエラーと四球で巡ってきたチャンスに併殺打でおかえしする感触だった。