2022/5/7に開催されたAtCoder Grand Contest 057に参加しました。
まだまだ緑コーダーの立場なので、ここ最近のAGCは基本的にスルーしていたのですが、今回は練習がてら参加することにしました。とりあえず、目標は1完というところです。
緑コーダーだけど、AGC参加します。
— devgenjin77 (@devgenjin77) 2022年5月7日
1完以上目指します!
AtCoder Grand Contest 057 - AtCoder https://t.co/jMc5Vwgzyr
今回の結果
で、、、今回はギリギリの滑り込みで1完を達成することができましたー。
UnRatedなので、パフォは出ませんでしたが、近辺のレートをみると水色ぐらいは出ていた模様。とにかく、1完できたことが嬉しいです。
終了ギリギリで1完を取ることができました😆
— devgenjin77 (@devgenjin77) 2022年5月8日
次のAGCまでには水色になれるよう頑張ります✊
devgenjin77さんのAtCoder Grand Contest 057での成績:935位#AtCoder #AGC057 https://t.co/fxL4Cvn1pc
振り返り
3時間丸々使ってA問題と格闘していました。
A問題
A - Antichain of Integer Strings
一見して、なかなか手強そうな問題という印象だが、とりあえず考察してみる。
で、まず思いついた所として、「良い集合」に含まれる数字は、連続した範囲の整数の数となり、最小値がの桁数のマイナス1になりそう。何故なら、の桁数マイナス2の任意の数字より、それを含む桁数マイナス1の数字の方が明らかに多いから。
上記から、との桁数が同じの場合、答えは以上以下の全ての整数の数が答えとなる。
あとは、の桁数マイナス1の数字で「良い集合」に含まれる数字を数え上げることを考える。
ちなみにの桁数マイナス1の数字を数え上げるのは、の先頭が1の場合のみを考えれば良い。あとはどの辺が集合の最小値になるかを考えるが、ここがうまく思いつかない。
とりあえず、あれこれ試行錯誤してると、サンプルが通るそれっぽい実装ができたので出してみたが、なんとサンプルしか通らず。。
その後もあれこれ弄っていくうちに、ゆうにコンテスト開始から2時間以上経過。0完終了が現実味を帯びてきた。。
とりあえず、コンテスト終了10分前ぐらいに投げてみた実装がWAを喰らい、ほとんど諦め掛けていた時に、やっと正解っぽいアイデアが降って来た。
集合の最小値として適切なのは、とのうちMaxをとれば良かったのだ。
ということで、残り3分を切ったあたりでなんとか提出。なんとかギリギリでACが取れましたとさ。
177分25秒2ペナで1完。最後まで諦めなくてよかったです。
提出コード
https://atcoder.jp/contests/agc057/submissions/31497239
B問題
一応、問題をチラ見しましたが何も思いつかずです。
C問題
問題すら見ておりません。
D問題
問題すら見ておりません。
E問題
問題すら見ておりません。
F問題
問題すら見ておりません。
これまでの実績
前述のとおり、UnRatedなのでレート変化はありません。
総括
今回久々のAGC参加でした。0完終了も覚悟してましたが、なんとか1完取れたのは、成長の証かもしれません。レートとしては何も変わらずですが、良い経験になったと思います。
次回のAGCまでには、なんとか水色になってRated参加したいところ。次はいつ開催か不明ですが、目標を達成できるように精進を積み重ねていきたいと思います。
ということで、また次回も頑張ります。