%w[...] リテラルに加工したけどな。■ C 問題「Attraction on Rainy Day」。配点は ABC-D。30 分かかった。KN≦2000万だから O(KN) が通らない可能性があって、余分に考えてしまった。DP なんだけど何をキーにして何を記録するのかひと目ではわからない。変数は「現在時刻」「濡れた量の総和」「アトラクションに乗った回数」。時刻ごと乗った回数ごとに濡れた量の総和を最小化する DP をする。スタートとゴールに近いときは考えるべき乗った回数が制約されるので、そこでループの回数をケチった。提出 #57009112 (AC / 1387 ms)。■ D 問題「Attend Many Events」。450 点。難しかった。30 分プラス２ペナ。頂点と辺とイベントの数がいずれも 1000 以下なので、いずれか２つの組み合わせが 100 万のオーダーで許される制約。イベントに参加するしないを総当たりはできないけど、イベントを時系列順に並べることで考えるべき対象が限定できる。つまり、あるイベントに参加するというとき、人の位置と時刻がそのイベントによって固定される。そのイベントに参加できるかどうかは、最後に参加したイベントもしくはスタート地点との距離によって決まる。過去のイベントを見て参加可能かどうか、それまでにいくつのイベントに参加しているかを見て最大のものを選んで現在のイベントに第３のパラメータとして記録する。O(KK) で許された。２地点間の距離は予め求めておく。２乗のアルゴリズムが許されるのでダイクストラ法を使わないで BFS/DFS でもたぶん大丈夫。提出 #57009717 (AC / 274 ms)。一度 WA を出した原因は、過去のイベントの中にはどうやっても参加不可能なものがあるということを適切に取り扱えていなかったこと。イベントに参加できていなかったのなら、その時刻その地点に居たという事実が存在しない、ということをきちんと反映させる。ところで、２乗のアルゴリズムを全頂点で実行したら３乗になってやばいのでは？ なんで全点間距離を愚直に求めて許された？ だからこその 1000 以下という、次の E 問題より小さい、２乗掛ける log が許されるやや小さめの制約か。■ E 問題「AtCoder Hotel」。どの制約も 5000 以下ということで、２乗の DP が許されたり TLE になったりしそう。何をキーにして何を記録する DP をしようか。結論を書くと C4B という変数名がすべて。つまり、B 人分の定員を確保するために C 円払ったということを記録する。B がキーで C が値。C を最小化する。ランクはどうなった？ これは人をランク要求で、客室をランクでソートすることで暗黙的に処理できる。客室ランクは大が小を兼ねるので、最もランク要求が厳しい人を満足させられる部屋だけで DP を行ったなら、その結果は次の人に対しても通用する。ただし、前の人が収まっているのでキャパシティが１減っている。提出 #57010115 (AC / 657 ms)。収容可能な人数として考慮すべき最大が徐々に減っていくのを考慮することでループの回数をケチった。C 問題と似たことを書いてるけど、こちらは 20 分しかかけていないので、C より E の方が簡単か。■ F 問題「Divide the Cake」。求められている答えから、更新しながら順番に判定をして最初の答えを見つけるんだと思うけど、どういう形式で記録すると高速に判定と更新ができるのかわからない。