2021/3/6に開催されたAtCoder Beginner Contest 194に参加しました。
ここ数回のABCは不調で3完止まりの結果が続いていたので、今回は最低でもそれ以上を目指そうという気持ちで臨みました。
AtCoder Beginner Contest 194 - AtCoder https://t.co/zBEsV6oYhJ
— devgenjin77 (@devgenjin77) 2021年3月6日
参加します。なにはともかく前回の3完以上の成績を目指します。
今回の結果
で、今回の結果ですが、個人的には上出来の5完達成となりました!
かなり久々に水色パフォーマンスを叩き出し、余裕の緑復帰を果たせました!
5完で久々の水パフォを達成。緑に復帰しました😃
— devgenjin77 (@devgenjin77) 2021年3月6日
これからも精進に励みます。
devgenjin77さんのAtCoder Beginner Contest 194での成績:1240位
パフォーマンス:1368相当
レーティング:779→854 (+75) :)#AtCoder #ABC194 https://t.co/S8xMsMFx25
振り返り
小さいミスが結構ありましたが、なんとかギリギリ5完まで辿り着けました。
A問題
4種類の場合分けをIF文で実装する問題。下記のとおり、愚直に実装してAC。
gist7b0c5b54ad3d51d018e3f7a4a8d765ec
問題文を読み解くのに多少手間取り、提出まで5分以上かかりました。
B問題
こちらは、うまい解法がないか結構悩みましたが、結局愚直で解くことにしました。
まず、全てのについての最小値を求める。その後、全てのの場合について、の最小値を取得し、小さい方を解答として出力すればOK。少し手間取りましたがAC。
C問題
多分、愚直にやるとTLEが出るやつだという印象の問題。
とりあえず、問題にある式を展開すると、以下の要素を全て足すことになる。
- 全てのについて、
- 全てのとなる組について、
まずは、これらを全て計算すればいいんじゃね、ってことで提出したら、結局計算量が減ってないらしく、TLEを喰らいました。。
これじゃいかんということで、突っ込んで検討したところ、各についてを計算するところは、全てのについてを計算すればよく、累積和を使えば計算量を減らすことができました。
あとは、なんとかこれを実装してAC。
D問題
期待値がどうこうという、いわば数学系の問題で解ける自信がなかったですが、なんとか以下の考察で解法の目処がつきました。
連結していない残りの頂点が1つの場合、この頂点が選ばれるまでの回数の期待値は、となる。残りの頂点が2つの場合、この2つのいずれかが選ばれるまでの回数の期待値は、となる。この要領で、のこりの頂点が個の時の期待値から、のこり頂点が1つとなるまでの期待値の総和を出せば良い。
この問題の似た形として、6面サイコロの全ての目を出すまでの回数の期待値がある。これをググると14.7回とあり、実装したプログラムをでテストしてみると13.7との解を得たので、多分これで行けるだろう。
ということで提出してACが取れました。
E問題
とりあえず問題文にヒントがあろうかと、「mex min 競技プログラミング」とかで検索した。すると、セグ木で解くとよいとかいう記事を漁って行く先に、Setを使っても解けるという趣旨の内容があったので、これをヒントにして検討すると、上限が1,500,000となっているので、以下の要領で解けるんじゃね?と考えました。
- HashSetに0から1,500,000を突っ込む
- 配列を個先読みして、出現回数を管理。でてきた数字をSetから消し、この時点でのMex(HashSetの先頭要素)を求める。
- 個のレンジを右に1つずつシフトする要領で、レンジの一つ右の要素を出現回数に足した後Setから消す。レンジの左端の要素は、出現回数から引いて、出現回数が0になったら、SetにMexの候補として要素を追加する。この時点でHashSetの先頭要素をみると、この時点のMexがわかる。
- これをレンジが右端に到達するまで繰り返し、Mexの最小値を求める。
これを実装してローカルで流したところ、各ケースで500msぐらい処理時間がかかったので、TLEにならないか大分不安でしたが、実際投げてみるとなんとか最大2200msの時間で耐えてくれてACが取れました。これで久々の5完達成!
コンテスト後、解説をみたら、どうもより効率的な解法があったようです。
いわば今回はたまたま時間制約が4secと長かったのに救われた感じだというところでしょうか。
F問題
F - Digits Paradise in Hexadecimal
残り10分でF問題まで到達。
しかし順位表でFのAC数が200程度で、そもそも今の自分に解ける気はせず、問題は読んだがさっぱり解法も思いつかないので、あとはコンテスト終了までひたすらボケっとしておりました。
これまでの実績
ここ数回で下げた分を一気に取り戻しました。
総括
今回久々の5完が取れたのも、E問題までが全て緑Diff以下の問題だったということが要因としてあると思います。水色、青色Diffの問題も解けるようになっておかないと、また3〜4完止まりの結果が続くと予想されるので、今回の結果で満足することなく、日々の精進に励もうと思います。
また、次回も頑張ります。