パナソニックグループプログラミングコンテスト2023(AtCoder Beginner Contest 326)参加記

2023/10/28に開催された、パナソニックグループプログラミングコンテスト2023(AtCoder Beginner Contest 326)に参加しました。

先週のABCで再度の入水を果たしたものの、現状ギリギリ水色コーダーという身分のため、なんとかレートを水色安全圏まで持っていきたいところ。

今回も水色パフォを取って、レートを上げていこうという感じで挑んでいきます。

Rated参加します。今回も水パフォ取って、水レート維持を目指します✊

パナソニックグループプログラミングコンテスト2023（AtCoder Beginner Contest 326） - AtCoder https://t.co/RZhB6z0gUl
— devgenjin77 (@devgenjin77) 2023年10月28日

今回の結果

終了３分前で、なんとかD問題を突破し、５完を確保することができました。

パフォーマンスの方は、水色の上の方まで出てくれて、なんとか直近のHighest付近までレートを戻すことができました。

５完水パフォ！
先週に続き、３桁順位を達成しました😂😂

devgenjin77さんのパナソニックグループプログラミングコンテスト2023（AtCoder Beginner Contest 326）での成績：984位
パフォーマンス：1534相当
レーティング：1204→1242 (+38) :)#AtCoder #ABC326 https://t.co/hULv17onWk
— devgenjin77 (@devgenjin77) 2023年10月28日

振り返り

結構ミスが重なってしまい、反省点の多かった回でした。

A問題

A - 2UP3DOWN

シンプルに条件分岐を組めそうな感じもするが、ハマったりする可能性もあるので、 $X \lt Y$ の場合と、 $X \gt Y$ の場合とで愚直に場合分けすることにしました。

少し実装に時間がかかったものの、問題なくAC。2分51秒で1完。

提出コード

https://atcoder.jp/contests/abc326/submissions/46994139

B問題

B - 326-like Numbers

$N$ からスタートして、326-like numberが見つかるまで $1$ づつインクリメントしながら試していけば良い。

これは、やるだけの実装でACが取れました。5分6秒で2完。

提出コード

https://atcoder.jp/contests/abc326/submissions/46998662

C問題

C - Peak

実数 $x$ を、数列 $A$ のすべての値について試してみて、実際に獲得できたプレゼントが一番多かったものを採用する方針で良いはず。

で、ここで当初取れる範囲を、 $x + M - 1$ で二分探索して、同値のものが見つかった場合プラス $1$ 補正するという実装をしたので、初回提出ではWAを喰らってしまいました。。

じゃあ、同じ値が見つかるまでプラス方向に補正し続けるのはどうかと試してみたら、TLEを喰らってしまう始末。

結局、普通に半開区間として、 $x + M$ を二分探索すれば、実装もシンプルだったというオチでした。

17分57秒2ペナで3完。ややこしく考えてしまい、変なとこでつまづいてしまいました。

提出コード

https://atcoder.jp/contests/abc326/submissions/47012495

D問題

D - ABC Puzzle

問題を一読した感じ、どうも実装の重い全探索系の問題のような気がする。

C問題を通した時点で順位表を見たところ、少しばかりE問題の方がAC数が多いようで、D問題でハマるリスクを考えれば、先にE問題を見てみた方が良いかという感じがしました。

ということで、一旦D問題をスキップすることに。

で、E問題を通したので、D問題に取り組むことに。

とりあえず、全行について、順列全探索的なことができるかと実装してみましたが、これはTLE。。

ということは、ある程度枝刈りしていくとなんとか解ける感じになるかなということで、列で同じ文字が２回以上出るケースをスキップするようにしました。が、、なぜかこれはWA。。

多分、どこかバグってるんだろうと思いながら色々調べているうちに、時間切れ間際まで追い込まれてしまいましたが、なんとか文字の重複チェックでバグっている箇所を突き止めて終了３分前にACを取り切ることができましたとさ。

97分21秒5ペナで5完。内容はボロボロでしたが、なんとか５完確保できてよかったです。

提出コード

https://atcoder.jp/contests/abc326/submissions/47041680

E問題

E - Revenge of "The Salary of AtCoder Inc."

まさしく、期待値DPのような形をした問題という印象でした。

具体的には、 $dp \lbrack i \rbrack :=$ 変数 $x = i$ の時にダイスを振って追加でもらえる給料の期待値と定義し、 $i = N$ から始めて $i = 0$ に向かってデクリメントしながら計算していけば、最後 $dp \lbrack 0 \rbrack$ に答えが入るという感じになるかと。

$dp\lbrack i \rbrack$ の具体的な値は、 $j \gt i$ となる $A_j$ の合計と、 $dp \lbrack j \rbrack$ の合計を $N$ で割れば計算できるかなという感じで実装したら、一応サンプルが通ったので提出。なんと一発でACを取り切ることができましたとさ。