devgenjin77’s blog

ユニークビジョンプログラミングコンテスト2023(AtCoder Beginner Contest 323)参加記

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

2023/10/7に開催された、ユニークビジョンプログラミングコンテスト2023(AtCoder Beginner Contest 323)に参加しました。

先週のABCは、水パフォ真ん中あたりという結果で、レートの方は１回爆死したぐらいでは緑落ちしないぐらいまで伸ばすことが出来ました。

今週も、順調にレートを伸ばしていこうということで、水パフォ目標で挑みます。

Rated参加します。今回も水パフォ目標で頑張ります✊

ユニークビジョンプログラミングコンテスト2023 秋 (AtCoder Beginner Contest 323) - AtCoder https://t.co/xYLQgBkZK2
— devgenjin77 (@devgenjin77) 2023年10月7日

今回の結果

３完で終了です。。

ABC323結果

パフォーマンスは、なんとか緑色を確保。レートは暴落しましたが、なんとか水色で耐えたというところです。

３完で冷え😭😭
devgenjin77さんのユニークビジョンプログラミングコンテスト2023 秋 (AtCoder Beginner Contest 323)での成績：4051位
パフォーマンス：820相当
レーティング：1252→1216 (-36) :(#AtCoder #ユニークビジョンプログラミングコンテスト2023秋(ABC323) https://t.co/M5tR5HfTGs
— devgenjin77 (@devgenjin77) 2023年10月7日

振り返り

D問題で大きくハマってしまいました。。

ABC323提出結果

A問題

$S$ の偶数文字目が全部0かどうかを判定する問題。

愚直にループで判定すれば良いので、やるだけの実装をしました。2分16秒で1完。

提出コード

https://atcoder.jp/contests/abc323/submissions/46281812

B問題

B - Round-Robin Tournament

$N$ 人のプレイヤーについて、勝利数の降順、プレイヤーの番号の昇順で並び替えるだけの問題。

ソートの典型問題みたいなものなので、こちらもやるだけの実装をしました。9分0秒で2完です。

提出コード

https://atcoder.jp/contests/abc323/submissions/46290913

C問題

C - World Tour Finals

各プレイヤーの得点と、全体の最高得点を予め計算しておく。

あとは、各プレイヤーについて、最高得点のプレイヤーは0、それ以外のプレイヤーは、最高得点を超えるには何問解けばいいかを、未解答の問題の点数の降順で見ていけば良い。

という感じで解ければ良かったのですが、初回提出はソートの順番を間違ってしまい、１WAを喰らいました。。

修正して、なんとかAC。21分19秒1ペナで3完です。

提出コード

https://atcoder.jp/contests/abc323/submissions/46304412

D問題

D - Merge Slimes

あまり見たことがないような問題だったので、戸惑いましたが、順位表を見ると大分解かれている問題なので、なんとかACは取っておきたい問題という感じです。

とりあえず、愚直に解いていくなら、スライムのサイズ $S$ とその数 $C$ をMapで管理しておき、サイズの小さい順から見ていけば良いかなあと。

次に、サイズの昇順で見た場合、各サイズについて２匹以上いる場合は合成すれば良い。数が奇数の場合は１匹合成できない個体が余るので、それを答えに足していく。合成できた個体については、サイズ $S$ の２倍になるので、Map上で足し合わせていく。

サイズの小さい順に見ていくためには、優先度付きキューでサイズを管理しておけば良いかという感じでなんとかサンプルが通る実装が出来ました。

が、、これを提出してみると、残念ながらTLE。。。

その後は、処理する順番を入れ替えするなど色々いじってみましたが、結果は出ず。結局この問題は一旦撤退することにしました。

E問題

見た目、確率計算をDPでやるような感じがする問題だが、肝心のDP配列と遷移が思いつかない。。

とりあえず、 $dp \lbrack i \rbrack \lbrack j \rbrack :=$ $i$ 秒の時点で、曲 $j$ が流れている確率、という感じのDPがいけるかと思ったが、実装してみたら全くサンプルすら通らず。

結局、この問題を通せずに時間切れになりましたとさ。

F問題

F - Push and Carry

本番中は目を通していなかったのですが、今見たら本番でもワンチャン解けてたかなあという問題でした。

D、Eで詰まっている状況だったので、Fにも目を通しておいた方がよかったかなあという感じです。

G問題

G - Inversion of Tree

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

これまでの実績

水色安全圏まで上げたつもりが、もう一回爆死を喰らったら緑落ちという状況になってしまいました。

コンテスト実績

総括

今回、改めて見ると、F問題までは高度なアルゴリズムの知識が必要ない感じだったのですが、大負けしたのは、まだまだ実装力が不足しているということかもしれません。

今回通せなかった問題については復習して、理解を深めていこうと思います。

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