devgenjin77’s blog

CodeQUEEN 2023 予選(AtCoder Beginner Contest 308)参加記

AtCoder 競プロ ABC 企業主催コンテスト

2023/7/1に開催された、CodeQUEEN 2023 予選(AtCoder Beginner Contest 308)に参加しました。

先週のABCは所用のため不参加。２週前のARCでは、０完爆死を喰らってしまい、レートが暴落したので、なんとかこの負け分を取り戻そうという気持ちで臨みます。

Rated参加します。
２週前のARCで暴落したレートを少しでも取り戻せるよう頑張ります✊

CodeQUEEN 2023 予選 (AtCoder Beginner Contest 308) - AtCoder https://t.co/DB0UogJrFJ
— devgenjin77 (@devgenjin77) 2023年7月1日

今回の結果

今回は、A-Eの５完で終了です。。

ABC308結果

なんとか緑パフォを獲得して、レートの方は微増で終了。まあ、負けるよりはマシという結果になりました。

５完緑パフォで、レートは微増😅😅
Fが解ききれずでした。
devgenjin77さんのCodeQUEEN 2023 予選 (AtCoder Beginner Contest 308)での成績：1922位
パフォーマンス：1168相当
レーティング：1111→1117 (+6) :)#AtCoder #CodeQUEEN2023予選(ABC308) https://t.co/jrk0gpyLUu
— devgenjin77 (@devgenjin77) 2023年7月1日

振り返り

C問題で大分やらかしてしまいました。

ABC308提出結果

A問題

なんか、色々な条件判定をしていくという問題。とりあえず、問題に書いてある条件を愚直に実装して、ACが取れましたとさ。

2分53秒で1完。

提出コード

https://atcoder.jp/contests/abc308/submissions/43089975

B問題

B - Default Price

各色の文字列をキー、対応する寿司の価格を値とするMapを作って計算していく。Mapに存在しない場合は、 $P_0$ 円で計算することに気をつける。

7分18秒で2完。

提出コード

https://atcoder.jp/contests/abc308/submissions/43096087

C問題

小数の誤差の問題でだいぶやらかしてしまいました。。

当初、分数の値で比較するので、誤差とか大丈夫かな？という考えがチラつきましたが、まあとりあえずいいやろという安直な考えでdoubleの比較で実装。で、案の定、WAを喰らってしまいました。。

じゃあ、BigDecimalで比較すればいいのかと思って、実装したら、これが何故かサンプルケースでエラーになってしまう。。

で、ちゃんと落ち着いて考えた結果、 $\frac{A_i}{A_i + B_i}$ と $\frac{A_j}{A_j + B_j}$ を比較する場合は、両辺に $(A_i + B_i) + (A_j + B_j)$ を掛けてやればいいんだということにやっと気が付く。

しかし、Cで時間を掛け過ぎということで焦った結果、バグらせた提出を繰り返し。都合３ペナ喰らった挙句、やっとのことでACが取れましたとさ。

35分49秒3ペナで3完です。

提出コード

https://atcoder.jp/contests/abc308/submissions/43120085

D問題

とりあえず、Cでやらかした分をなんとか取り戻そうという気持ちで取り組みました。

この問題は、単純なBFSの問題。s->n->u->k->eという順番で、スタートから、マス $(H,W)$ に辿り着けるかを判定すれば良い。

実装の方も、なんとかこなしてACを取ることが出来ましたとさ。

50分24秒3ペナで4完。

提出コード

https://atcoder.jp/contests/abc308/submissions/43128276

E問題

なんか、昔似たような問題で本番解ききれなかった苦い記憶があったので、なんとか解法を思いつくことが出来ました。

文字列 $S$ を先頭から見て、Eの位置に来た時に、その位置より前のMの位置に対する $(0,1,2)$ それぞれの数、およびとその後ろのXの位置に対する $(0,1,2)$ それぞれの数が分かれば、計算量 $O(N)$ ぐらいで行けるはず。

後は、MおよびXの位置に対する $(0,1,2)$ の数を予め累積和で求めておけばOK。

ということで、後は実装して提出。１回MEXの取り方が悪かったのかWAを喰らいましたが、修正して、なんとかACを取り切ることができました。

71分35秒4ペナで5完。難し目の問題かと思ってましたが、今日日これぐらいの問題でも、今は2000AC以上は行くんだなあと。

提出コード

https://atcoder.jp/contests/abc308/submissions/43137941

F問題

残り30分弱という時間があるので、なんとか解き切りたかったF問題だが、解法が思い付かず。。

順位表を見てると、だいぶAC数が伸びてる感じなので、なんかの貪欲で解けるのか、またまた典型のアルゴリズムなのか。。

時間いっぱいまで、いろいろ考察をしてみましたが、結局何もわからずのまま、時間切れになってしまいましたとさ。

G問題

G - Minimum Xor Pair Query

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

Ex問題

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

これまでの実績

一応、レートはちょい上がりましたが、入水への道はまだまだ遠いです。

コンテスト実績

総括

今回、C問題でやらかしすぎたのは大きな反省点。５完でもペナがなければ水パフォは行けたかなあというところなので、このミスは痛かったです。

またまた、自分の実力不足を痛感させられた回でした。最近の精進不足で実力が落ちてるかもしれません。精進時間を増やして次に備えることにします。

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