AtCoder Beginner Contest 198 反省

一応、黄色昇格に王手をかける形となった。とはいえ、次は8問制ABCなのでうまく立ち回らないと破滅し再び黄色が遠のいてしまう。

結果を鑑みて

1500(2) 44:33

149位となった。速解き力、数学力、実装力、そして注意力が必要とされる実にやりづらいセットだった。苦手回ではなかったが、どの問題でも嵌って破滅があり得たセットだった。

A - Div

最初、N≦15という制約を見て少し動揺したが、サンプルからN-1をエスパーしてこれに証明を与えてACできた。

B - Palindrome with leading zeros

なぜかわからないが末尾の0を消す方針で回文判定を行なった。しかも回文判定も１文字ずつ。（S==S[: : -1]でいいのに)

結局4分かかって順位表も見てしまって精神が乱れる要因となった。ここらへんのムーブはかなり変だった気がする。 

C - Compass Walking

まず、貪欲に近付いてシミュレーションするのは得策ではなさそうに見えた。そうなると数学することになるが、これもよくわからない。第三の選択肢として二分探索を考えたが、これが実にシンプルな解法だったのでこれが答えだと確信した。

WAが返ってきた。順位表を見ると大勢ペナを出していたのでそこまで焦燥を感じずには済んだ。そのため冷静にWAケースの数からコーナーの発見につなげることができた。

この問題はいつぞやのBishopのような雰囲気を感じた。ここで1ペナつけて12分くらいで200位くらいだったと思う。少し安心した。

D - Send More Money

まず、問題を読んで面倒臭そうに思った。leading zeroを許しているのかどうかもわかりづらい。問題の理解におそらく2~5分かかり、理解すると解法はすぐに生えた。permutationsを使うやや面倒な実装問題であることがわかり、順位表を見るとわずかにEのACがDより多く、Eの方が簡単らしいことが意図せずわかってしまったが敢えてそのままDを解きにかかった。

結局、14分程度かけてこれをACした。このとき、実行時間制限が5secであることにACを取ってから気付いた。ジャッジ中はTLEしないか気が気でなかった。4.4secでギリギリ通って安堵したもののもう少し高速な処理が書けたのではないかと少し思った。

この時点で体感時間的には21:50ほどであったが、実際は21:30ほどで、なかなかよく集中できていたと思う。

E - Unique Color

案の定、この問題は見て少し考えたら解法が生える程度の簡単な問題だった。サンプルを眺めていたときに「出力は昇順か、気をつけないと」と思ったのも束の間、実装に入ると全部忘れて出力をソートせずに出して1ペナつけた。これでパフォーマンスが30~40落ちていると思われる。

最初にミスしそうな点に気付いたらコードにコメントしておくことにしよう。この時点ではpredictorの算出では黄色タッチだった。順位もそこまで悪くなく、安心して次の問題を見ることができた。（とはいえ、Fが異常そうなのはAC数から既に察していた。）

F - Cube

これは解けなかった。難問。

ボリアの数え上げ定理に思いを馳せたが、三次元の回転にどう持って来ればいいのかわからなかった。これに関連して、mod 6でうまいこと順列表現してサイコロの同型判定ができないか考えたりもした。

また、サイコロのパターン列挙は6!で進み、これの同型判定ができればあとは組み合わせ論の計算に落ちることを見出したが、最初の同型判定をどうすればうまく進められるのかわからなかった。対称性のある無向グラフについての判定と見て、隣接行列をうまく照らし合わせられないかと思ったが......。また、それができたとしてもその後の計算も特に方法が思いつかなかった。

そんなこんなで、22時くらいには恐らく解けないし、解かなくても大丈夫な問題だなと判断してそこから10分ほどまた考えた後にお風呂に入って完全に撤退した。（とはいえお風呂でもついつい考察してしまうのだけれど）

総括

出だしのムーブが変だったような気がするが、C~Dあたりのムーブはまあ良かったと思う。Eのようなミスは今後しないようにしたい。