初めてのコンテスト

先月AtCoderに登録して、今日初めてコンテストというものに参加した。今回はそのことについて書く。

今回参加したのはAtCoder Grand Contest 033 (通称AGC)。AからFまで全部で6問あった。問題を見たところAとBくらいしか方針が立たなかったので、まずはAから挑戦することにした。

問題の詳細は省くが、Aは感染のシミュレーションのように隣接したものを黒く変化させる問題だった。まず躓いたのが入力である。これは行列を使うのか、それともリストに入れるのか、普通に入れても大丈夫なのか迷った。行列の作り方が分からないのでリストでなんとかしようと思った。forを使って処理しようと思ったが複数行入れようとすると変数が上書きされてしまう。リストの中にリストを入れれば良いのではと思ったが、要素の取り出し方が分からなかったので別の方法を探すことにした。appendで逐一リストに追加していけば上手くいきそうなので書いてみた。書けるには書けるのだが横に繋がった文字を1文字ずつに分解して取り出す方法が分からなかった。ちなみに行列を作るにはNumPyというライブラリを使うらしいが入力の仕方が分からなかったので諦めた。

Aが駄目だったので今度はBを解くことにした。
指定された範囲の中に1つのコマがあり2人が交互に計N回ずつ動し、上下左右に動かす権利を持つ文字列を順に消費していって一方は範囲外に押し出そうとして他方は盤面に残そうと最適行動を取る、という問題だった。問題の解釈に少し時間が掛かったが取り合えず把握したので書くことにした。最初に思いついたのはお互いの文字列を利用して行動を決めるというものだったが、書き方が分からないので別の方法を考えることにした。次に思いついたのは盤面のどこにいるのかによって行動を決めるというものだった。右に移動出来る権利を持つとして、もしも盤面の右側にコマがあれば、盤面の外に出したい人は権利を使い右に移動させ、盤面に残したい人は右に動かさない選択をする、というものだ。ただこれには欠点がある、もし相手が左移動の権利をたくさん持っているとすれば、残したい側は盤面の右にコマがあっても中央に戻すべきではない。やはり相手の文字列を考える必要があるらしい。ともかく難しいことは分からないので一旦コードを書くことにした。

場所によって判断するコードを書いた。綺麗なコードが書けず、移動用の関数を作ったり上下左右の4パターンを全て列挙したり長くなってしまった。試しに実行してみると大量のエラーが出てきた。このエラーに苦戦して1時間以上溶かした。文字に括弧をしてなかったりif文の最後の処理を忘れていたりインデントがずれていたり色々細かいミスがあった。大きなミスとしては関数を定義するdefの使い方を間違えていた。外から文字を持ってきてdef内で処理しようと思っていたのだが、それが原因でエラーが起きてしまった。関数内で文字を定義し直して外に出してから元の文字に代入しなければいけないのかと思ったが、本来便利な機能であるはずのdefでそんな二度手間を必要とする訳がないと思ったので別の方法を考えた。引数として中に入れてやれば処理できるのではないかと思い書き直してみたらエラーが消えて実行出来た。

試しに入力例を入れてみると出力例と一致した。これはもしやACなのでは？そう思い提出してみたところRE(実行時エラー)だった。詳細を見てみると一部のケースでAC(正解)だったがほとんどがREになっていた。質問欄を見てみると二人はお互いの文字列を把握しているらしく、やはり最適行動にはお互いの文字列を考える必要があったらしい。色々考えている内に時間切れとなった。

2時間半、21時から23時半まで頑張ってみたが1問も解けなかった。とても難しかった。beginners selectionを全問解いたしA問題くらいなら解けるかなーと思っていたが全然解けなかった。そういえば競プロ始めました報告の記事でbeginners selectionを半分解いたら続きを書くと言っていたが、全問解いた翌日にコンテストが始まったのでこちらを優先して書いた。beginners selectionについてはまた今度書く。今回解けなかった問題は他人のコードを読んで勉強することにする。今回はここまで、終わり。