AtCoder Beginner Contest 194 参加記

2021/3/6に開催されたAtCoder Beginner Contest 194に参加しました。

atcoder.jp

ここ数回のABCは不調で3完止まりの結果が続いていたので、今回は最低でもそれ以上を目指そうという気持ちで臨みました。

今回の結果

で、今回の結果ですが、個人的には上出来の5完達成となりました!

ABC194提出結果

ABC194提出結果

かなり久々に水色パフォーマンスを叩き出し、余裕の緑復帰を果たせました!

振り返り

小さいミスが結構ありましたが、なんとかギリギリ5完まで辿り着けました。

ABC194提出結果

ABC194提出結果

A問題

A - I Scream

4種類の場合分けをIF文で実装する問題。下記のとおり、愚直に実装してAC。

gist7b0c5b54ad3d51d018e3f7a4a8d765ec

問題文を読み解くのに多少手間取り、提出まで5分以上かかりました。

B問題

B - Job Assignment

こちらは、うまい解法がないか結構悩みましたが、結局愚直で解くことにしました。

まず、全てのiについてA_i + B_iの最小値を求める。その後、全ての i \ne jの場合について、min(max(A_j, B_i),max(A_i, B_j))の最小値を取得し、小さい方を解答として出力すればOK。少し手間取りましたがAC。

C問題

C - Squared Error

多分、愚直にやるとTLEが出るやつだという印象の問題。

とりあえず、問題にある式を展開すると、以下の要素を全て足すことになる。

  • 全てのi \le Nについて、{(N - 1)} \times {A_i}^2
  • 全てのi \ne jとなる組について、-2 \times (A_i \times A_j)

まずは、これらを全て計算すればいいんじゃね、ってことで提出したら、結局計算量が減ってないらしく、TLEを喰らいました。。

これじゃいかんということで、突っ込んで検討したところ、各i,jについて-2 \times (A_i \times A_j)を計算するところは、全てのi \lt NについてA_i \times (A_{i + 1} + A_{i + 2} + ... + A_N)を計算すればよく、累積和を使えば計算量を減らすことができました。

あとは、なんとかこれを実装してAC。

D問題

D - Journey

期待値がどうこうという、いわば数学系の問題で解ける自信がなかったですが、なんとか以下の考察で解法の目処がつきました。

連結していない残りの頂点が1つの場合、この頂点が選ばれるまでの回数の期待値は、Nとなる。残りの頂点が2つの場合、この2つのいずれかが選ばれるまでの回数の期待値は、\frac{N}{2}となる。この要領で、のこりの頂点がN - 1個の時の期待値から、のこり頂点が1つとなるまでの期待値の総和を出せば良い。

この問題の似た形として、6面サイコロの全ての目を出すまでの回数の期待値がある。これをググると14.7回とあり、実装したプログラムをN=6でテストしてみると13.7との解を得たので、多分これで行けるだろう。

ということで提出してACが取れました。

E問題

E - Mex Min

とりあえず問題文にヒントがあろうかと、「mex min 競技プログラミング」とかで検索した。すると、セグ木で解くとよいとかいう記事を漁って行く先に、Setを使っても解けるという趣旨の内容があったので、これをヒントにして検討すると、上限が1,500,000となっているので、以下の要領で解けるんじゃね?と考えました。

  • HashSetに0から1,500,000を突っ込む
  • 配列をM個先読みして、出現回数を管理。でてきた数字をSetから消し、この時点でのMex(HashSetの先頭要素)を求める。
  • M個のレンジを右に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完止まりの結果が続くと予想されるので、今回の結果で満足することなく、日々の精進に励もうと思います。

また、次回も頑張ります。