AGC045に参加しました - devgenjin77’s blog

先日AtCoder で開催されたAGCコンテストに参加しました。

前回のAGCは無念の0完で終わったので、今回は1完以上を目標に挑戦しました。

今回のAGCからレート1200以上ないとレーティング計算対象にならないみたいですが、ま、その辺は勉強がてらというとこで気軽に参加してみようという感じです。

AtCoder Grand Contest 045 - AtCoder https://t.co/pcoZtImekG
灰色だけど勉強がてら参加します。1完以上が目標。
— devgenjin77 (@devgenjin77) 2020年6月7日

で、終わってみれば今回も0完で終了です。

2人のプレイヤー0、1が、各ラウンドにおいて与えられた数字をXORする、しないを選択する。プレイヤー0は最終的に数字を0にすれば勝ち。プレイヤー1は数字を0以外にすれば勝ちという条件で、互いに最善をつくせばどちらが勝つかを答える問題。

この問題をみて、かつて使った記憶があるミニマックス法のやり方を応用してなんとかできないかと考え、30分弱ほどでなんとか実装にこぎづける。

んで、サンプルのテストが通ったので、こりや1完ワンチャンあるかと思い提出しましたが。。。

他のテストケースは、TLEで通らず。

こころばかりの性能改善をやってみるも、焼け石に水のようでTLEを連発。結局諦めざるをえない状況になりました。

コンテスト後、解答を確認しましたが、結局もっと計算効率の良い解法でないと話にならないようでした。残念。

0、1の文字列のアンバランス度とかいう、定義のよーわからん度数を求める問題。

定義もわからなければ解法もわかるわけがなく、提出なしで時間切れとなりました。

コンテスト中には目を通せませんでした。次回のAGCまでには解いておこう。

前回AGCはノー提出フィニッシュで、累積の参加回数はノーカウントでした。

今回は提出ありの0完フィニッシュでしたが、これもノーカウントになるという知見を得ました。

AGCの問題はレベル高すぎで、高レーティングの人も相当苦戦しているようです。

次回のAGCはなんとか1完はできるよう、上を目指して精進します。