脳log[20231021]

2023年10月21日 (土) [AtCoder] 今日はキーエンスプログラミングコンテスト2023秋（AtCoder Beginner Contest 325）があった。自分のすべての提出。結果は知らないよ。今日の日記には DEF の精進が含まれてるよ。要するにそういうことだよ。■A 問題「Takahashi san」。名前部分をちょん切って 'san' をくっつけます。■B 問題「World Meeting」。いきなり難しいなと思ったけど、入力がすべて整数なので扱う時刻は正時(セイジでなぜか変換できないと思ったらショウジって読むらしい)のみの 24 通りだけだった。なら時間枠に参加人数を加算していくのみ。■C 問題「Sensors」。UnionFind でやった。そうでないなら DFS でやるのがいいと思う。BFS は難しい。友達の友達は友達という関係には再帰構造があるので。センサーがないマス(.)については頂点を１つ追加しておいてそれとグループを作るようにした。そうしたら最後にグループ数から -1 するだけでいい。■D 問題「Printing Machine」。時間内に解けなかったので精進だよ。時刻の幅が鬼門。10 の 18 乗まであるから飛び飛びの時刻を処理するしかない。情報を蓄えておいてあとからシミュレートする。最終的に AC になった提出では、プライオリティキューで現在印字待ちのアイテムについて印字処理のリミット(t+d)を管理し、また、最後に処理した時刻(t0)を記憶しておいた。そして処理開始時刻(t)でソートしたアイテムについてループを回した。区間の端を -1 したりする処理で間違えていた。■E 問題「Our clients, please wait a moment」。D 問題と心中したので E 問題は終了後に読んだ。AC まで 21 分だった。都市１から車で移動した場合の各都市までの所要時間を調べ、都市 N から電車で移動した場合の各都市までの所要時間を調べ、zip して足したものの最小値が答え。最短距離を求めるのに D 問題で使ったプライオリティキューをまた使ってダイクストラ法なのかなと思ったけど、完全グラフなので log を付けるより総当たりの方が良さそう。それは Cosmic Rays (20211031) の経験から。■F 問題「Sensor Optimization Dilemma」。なかなか方針のしっぽが掴めなかった。DP なのか二分探索なのか。制約の攻めどころはどこか、上限が 1000 の K だろうか、高々 100 でしかない N だろうか。結果的には DP だった。区間(D)についてループを回し、センサー１の使用回数に対してセンサー２の使用回数を最小化するような DP をした。NKK≦１億なので Ruby では１桁オーバーで通らないかと思われたけど、112 ms であっけなく通った。謎。■おかしいなあ。これでなんでコンテストは ABC の３完なんだろうなあ。たぶんだけど、今が 25 時をまわってることと関係がある気がするな、たぶんだけど。■AtCoder Problems によると DEF の難易度が順番に 水緑青 だった。D と E が逆転している。そうだろうなあ。もっとも、自分は水 diff は解けていないといけないので、解けたのが ABC でも ABCE でも不出来なのは同じ。点取りムーブに興味はない(負け惜しみ言ってら)。まあまあ、長い目で見て AtCoder さんの評価が自分に追いついてくるのを待っていてあげようじゃありませんか。