キーエンスプログラミングコンテスト2023秋(AtCoder Beginner Contest 325)参加記

2023/10/21に開催された、キーエンスプログラミングコンテスト2023秋(AtCoder Beginner Contest 325)に参加しました。

今週は長期AHCの開催期間だったので、アルゴリズムの精進は程々にAHCの考察と実装に取り組んでいたのですが、ABCにはきちんと参加することに。

とりあえず、再入水に向けて、水パフォ目標で挑むこととしました。

AHCの途中ですが、Rated参加します。
再入水に向けて、水パフォ目標で頑張ります✊

キーエンスプログラミングコンテスト2023秋（AtCoder Beginner Contest 325） - AtCoder https://t.co/glOZTxgIGf
— devgenjin77 (@devgenjin77) 2023年10月21日

今回の結果

なんとか、５完を確保しました。

久しぶりの３桁順位ということで、青パフォもあるかなという期待もありましたが、結果は少し及ばすで水パフォ。

それでも、レートは大幅に回復して、なんとかギリギリで再入水を果たすことが出来ました。

５完水パフォで再入水！😂😂
devgenjin77さんのキーエンスプログラミングコンテスト2023秋（AtCoder Beginner Contest 325）での成績：857位
パフォーマンス：1529相当
レーティング：1162→1204 (+42) :)#AtCoder #キーエンスプログラミングコンテスト2023秋（ABC325） https://t.co/AOG8buQ2P3
— devgenjin77 (@devgenjin77) 2023年10月21日

振り返り

Dで多少詰まったことを除けば、概ね良い内容でした。

A問題

A - Takahashi san

文字列 $S$ の後ろにsanを付けるだけ。

今までやってきたA問題の中でも、最も簡単な部類に入る問題という感じだったので、テストもせずに投げました。51秒で1完。

提出コード

https://atcoder.jp/contests/abc325/submissions/46790739

B問題

B - World Meeting

世界標準時で $0$ 時開始から $1$ 時間刻みに $23$ 時開始までの $24$ パターンについて、それぞれ参加できる拠点の人数を足し合わせた合計の最大を答えれば良い。

これもやるだけの実装でACでした。5分58秒で2完です。

提出コード

https://atcoder.jp/contests/abc325/submissions/46797528

C問題

C - Sensors

見た目の感じ、Union-Findを使うやつかなあと思ったので、素直に連結をUnion-Findで管理する方針としました。

まずは、それぞれのマス目について、#のマスの上下左右斜めのマスが#だった場合、Union-Findで連結させる。

あとは#の連結成分が何個かが分かれば良い。#のマスについてUnion-Find上のleader関数の値をSetに格納して、最後にサイズを出力する実装としました。

こちらも問題なくAC。16分43秒で3完です。

提出コード

https://atcoder.jp/contests/abc325/submissions/46803592

D問題

D - Printing Machine

最初、区間スケジューリング問題の変形みたいな感じだと思ったので、とりあえず後ろから印字する方向で考えてみました。

考え方としては、印刷範囲から出るのが遅い順、次に印刷範囲に入るのが遅い順から優先して印字していけば良いだろうという感じ。

まず、印刷範囲から出る順の降順の優先度付きキューに全商品を入れておき、次に印刷範囲に入る順の降順の優先度付きキューを空で用意する。

次に後者のキューが空の場合、前者のキューの先頭の終了時刻と同じ終了時刻の商品を後者のキューに入れる。

最後に、後者のキューの先頭から見て、前回印字した時刻より前の時刻で印字可能であれば可能な限り最大の時刻で印字する。出来ない場合はキューから捨てる。

この要領で、前者のキューが空になるまで処理を行い、最終的に印字できた商品数を出力すればOKという感じです。

考察と実装にやたら時間が取られましたが、なんとかACを確保。63分36秒で4完です。

提出コード

https://atcoder.jp/contests/abc325/submissions/46820361

E問題

E - Our clients, please wait a moment

車から電車に乗り換えるのが１回だけということで、都市 $1$ から各都市に車だけで移動した時の最短距離と、都市 $N$ から各都市に電車だけで移動した時の最短距離をそれぞれダイクストラで求めておき、あとはどこで乗り換えるのかを全探索すれば良いかという感じの問題でした。

実装も問題なく完了し、なんとかACを確保。80分30秒で5完。

とりあえず、この時点で順位は８００台あたりというところで、勝ちは確定したという状況でした。

提出コード

https://atcoder.jp/contests/abc325/submissions/46824850

F問題

F - Sensor Optimization Dilemma

２０分弱という残り時間ながらも、とりあえず挑戦してみることに。

見た目上、とりあえず難し目のDPという感じ。制約から察するに、 $dp\lbrack i \rbrack \lbrack j \rbrack \lbrack k \rbrack :=$ $i$ 個目の区間まで見て、センサー１が $j$ 個かつ、センサー２が $k$ 個の場合の最小コストというのを考えてみましたが、これだと全然計算量が抑えられてないということ気付いたところで時間切れとなりました。