2024年10月19日 (土)[AtCoder] 今日は ABC376（Promotion of AtCoder Career Design DAY）があった。自分のすべての提出。配点からは ABC が上ぶれで DEF はそれなりで、G が難しいと予想される。では A から E まで。■A 問題「Candy Button」。入力が時刻の列だということで前後の時間差に変換する必要があるのかな嫌らしいなあと反射的に考えたけど、まったくそんなことはなかった。最後にあめをもらった時刻を記録して数える。■B 問題「Hands on Ring (Easy)」。数えるだけ。他方の手が邪魔をするので時計回り反時計回りのどちらで数えるかが必ず決まっている。■C 問題「Prepare Another Box」。気持ち的には大きいおもちゃから優先して大きい箱をあてがいたい。あぶれるおもちゃを記録してそれが１つだけならその大きさが答え。それで良さそうに思えるけどやや自信が持てなかった。気持ちを強く持って提出！(これはダメなやつ)■D 問題「Cycle」。１から BFS をして１に着くまで。自分が BFS を書いていると知らなくて Array#pop を使ってしまい(Array をスタックとして使ってしまい)、１ペナ。キュー(Array#shift)でもスタック(Array#pop)でもどちらでもいいと思ったときは短い方(pop)を使うため。■E 問題「Max × Sum」。A 数列から選ぶ最大値も、B 数列から選ぶ K 個の和も、小さい方が良い(ここで制約が１以上であることを確認)。まずは A 数列から選ぶ最大値を固定しましょう。ソートして K 番目以降が最大値としてありうる値。最大値を決めたら、A 数列のうちそれ以下の値を持つ要素の添字が自由に使えるので、B 数列から選ぶ K 個の和が最低になるように添字を選ぶ。プライオリティキューを使った。補足。「以下の値を持つ要素の添字が自由に使える」は文字通りの意味で、未満の値の添字のみで B 数列から選ぶ K 要素が最小になるなら、A の最大値をより小さく固定した別のターンが答えを出すので心配ない。これは ABC116-D「Various Sushi」からの学び (「難しいなこれ。ある時点のループにおいてベストを求めなくていいし不正確でもいいということを見極めて受け入れるのは」)。■F 問題「Hands on Ring (Hard)」。案外状態数は少ないのかなと思った。LR がこの並びで隣接している場合と、RL の並びで隣接している場合と、離れた位置にある場合の３通り。でもこれは WA だった。離れた位置にある場合の元になる状態が LR、RL、離れの３通りあるのだから、すぐに３通りでおさまらなくなる。しかし一方の手が直前のクエリにより固定され他方の手としてありうる位置が 2999 通りまでなので、高が知れているとも言える。しかししかし、点から点への遷移は大変な苦労をして書いたけど、線から線への遷移は書けなかった。