AtCoder Grand Contest 063 参加記

2023/7/31に開催されたAtCoder Grand Contest 063に参加しました。

まだ入水できていない状況ゆえ、今回もRated参加はできませんでしたが、経験を積むために参加するという感じです。

とりあえず、今回も１完以上が目標です。

緑コーダーですが、参加します。
今回も１完目標で頑張ります✊

AtCoder Grand Contest 063 - AtCoder https://t.co/yRpVEiPRp1
— devgenjin77 (@devgenjin77) 2023年7月30日

今回の結果

なんとか１完確保しました。

Unrated参加につき、もちろんレートの変化はなし。

仮にRatedだったら水パフォはあったようで、少し勿体無い気もしますが、まあこれも仕方なしです。

とりあえず今回１完確保しました。
次はRated参加できるように頑張ります。
devgenjin77さんのAtCoder Grand Contest 063での成績：758位#AtCoder #AGC063 https://t.co/dhEXTSh6C6
— devgenjin77 (@devgenjin77) 2023年7月30日

振り返り

Bは惜しいところまで行きましたが、解き切ることができませんでした。

A問題

A - Mex Game

プレーヤーが取れる戦略としては、相手が勝ちとなる数を小さい順から指定していくことで相手の勝ちを減らしていくというのが最適なように思える。

サンプルで試しても確かにその通りになるということで、早速実装に着手。

Aliceの手番の場合、 $S$ 内にあるBの位置で、まだ $X$ に設定されていない数を $x$ として指定（無い場合は何も指定しない）。逆にBobの手番では、 $S$ 内にあるAの位置で、まだ $X$ に設定されていない数を $x$ として指定する処理を行い、各ターンごとのmexにある文字で勝者を出力するという実装で提出。これが、なんともあっさりと通ってくれました。

12分40秒で1完。とりあえず０完が回避できて、良かったです。

提出コード

https://atcoder.jp/contests/agc063/submissions/44111024

B問題

B - Insert 1, 2, 3, ...

$1$ から始まる列でないと、生成可能にならないと思われるので、 $L$ の候補としては、 $A_i = 1$ となる $i$ に限定される。

また、 $L$ を固定して $R$ を右に伸ばした場合、途中で生成不可能な列になったら、それ以降は生成可能にならないと思われる。

よって、 $A_i = 1$ となる $i$ 全てに対して、それぞれを $L$ と設定した時に、どこまで生成可能な列として右に伸ばせるかが計算できれば答えは求まるかと。

が、、それを実際に形にするのは中々難しい。。

まずは、各列に対してどこまで右に生成可能な列として取りうるかを管理する配列 $B$ を管理することを試してみる。これで、 $A$ を後ろから見ていき、[tex:A_i + 1 = A{i + 1}]の場合に[tex:B_i = B{i + 1}]とすれば、繋がり管理できるのではと思いましたが、微妙に上手くいかず。。