AtCoder Grand Contest 057 参加記

2022/5/7に開催されたAtCoder Grand Contest 057に参加しました。

atcoder.jp

まだまだ緑コーダーの立場なので、ここ最近のAGCは基本的にスルーしていたのですが、今回は練習がてら参加することにしました。とりあえず、目標は1完というところです。

今回の結果

で、、、今回はギリギリの滑り込みで1完を達成することができましたー。

AGC057結果
AGC057結果

UnRatedなので、パフォは出ませんでしたが、近辺のレートをみると水色ぐらいは出ていた模様。とにかく、1完できたことが嬉しいです。

振り返り

3時間丸々使ってA問題と格闘していました。

AGC057提出結果
AGC057提出結果

A問題

A - Antichain of Integer Strings

一見して、なかなか手強そうな問題という印象だが、とりあえず考察してみる。

で、まず思いついた所として、「良い集合」に含まれる数字は、連続した範囲の整数の数となり、最小値がrの桁数のマイナス1になりそう。何故なら、rの桁数マイナス2の任意の数字より、それを含む桁数マイナス1の数字の方が明らかに多いから。

上記から、lrの桁数が同じの場合、答えはl以上r以下の全ての整数の数が答えとなる。

あとは、rの桁数マイナス1の数字で「良い集合」に含まれる数字を数え上げることを考える。

ちなみにrの桁数マイナス1の数字を数え上げるのは、rの先頭が1の場合のみを考えれば良い。あとはどの辺が集合の最小値になるかを考えるが、ここがうまく思いつかない。

とりあえず、あれこれ試行錯誤してると、サンプルが通るそれっぽい実装ができたので出してみたが、なんとサンプルしか通らず。。

その後もあれこれ弄っていくうちに、ゆうにコンテスト開始から2時間以上経過。0完終了が現実味を帯びてきた。。

とりあえず、コンテスト終了10分前ぐらいに投げてみた実装がWAを喰らい、ほとんど諦め掛けていた時に、やっと正解っぽいアイデアが降って来た。

集合の最小値として適切なのは、(r \div 10) + 1lのうちMaxをとれば良かったのだ。

ということで、残り3分を切ったあたりでなんとか提出。なんとかギリギリでACが取れましたとさ。

177分25秒2ペナで1完。最後まで諦めなくてよかったです。

提出コード

https://atcoder.jp/contests/agc057/submissions/31497239

B問題

B - 2A + x

一応、問題をチラ見しましたが何も思いつかずです。

C問題

C - Increment or Xor

問題すら見ておりません。

D問題

D - Sum Avoidance

問題すら見ておりません。

E問題

E - RowCol/ColRow Sort

問題すら見ておりません。

F問題

F - Reflection

問題すら見ておりません。

これまでの実績

前述のとおり、UnRatedなのでレート変化はありません。

コンテスト実績
コンテスト実績

総括

今回久々のAGC参加でした。0完終了も覚悟してましたが、なんとか1完取れたのは、成長の証かもしれません。レートとしては何も変わらずですが、良い経験になったと思います。

次回のAGCまでには、なんとか水色になってRated参加したいところ。次はいつ開催か不明ですが、目標を達成できるように精進を積み重ねていきたいと思います。

ということで、また次回も頑張ります。