答えが 64 bit整数型に収まらないこともあることに注意してください」と書いてあるのだけど、これをよくある 32 bit整数型に収まらない場合の警告だと思って、でも上限がどこかに定めてあるんでしょうと問題文をさらったけど見つからなくて、Ruby だからと深く取り合わずに提出したら TLE になった。答えを文字列で持つのが正解。■F 問題「Teleporter Setting」。これも最初は問題文が読めていなかった。求めるのは 1 から N までの最短距離。それに不定なテレポーターがどう寄与するか。不定なテレポーターが寄与しないなら普通に町 1 から BFS した距離表(D1)でもって D1[N] が答えだし、寄与するときに考えるパターンは２通りしかない。つまり、1 から i を目指すより 1 から 0 を目指した方が近いパターンと、N から i を目指すより N から 0 を目指した方が近いパターン。それだけではない気がしたとしても、それだけ。■コンテスト時間中に 4 WA と自分より先を行っていた提出 #32743897 をデバッグしようとして 30 分以上考えている。予想だけど、町 1 と町 N が不定なテレポーター(0)を介して連結な場合が抜けていると思う。たとえば 1-2-0-9-N というグラフ構造のとき、i の値によらず
min_a+min_b+2 が答えの候補としてある。Di の最小値は多くの場合 d1,2 に一致します。」 和の「最小値」が「多くの場合」答えに一致するとか、そんなざっくりした掴まえ方は出て来んで。結果として自分と同じ考え方の提出が全然見つからないのはとても嬉しい(そういうタイプの人間)。
1 日に複数本の道を使うことはできないことに注意してください」の一文を念頭に置いて考えれば、むしろどうしてこれが問題になるのかわからなくなった。パスとか何日目に訪れたとか関係なく、街の集合を一日一日拡大していくことを考えるだけ。とはいえ制約が厳しい。新しく訪問した街があればそこから移動できる未訪問の街を最初に訪問可能になるのが何日後かをセグメント木で管理した。■提出 #32487113 (AC / 995 Byte / 1952 ms)。2183 ms で TLE になったので 200 ms をミクロなチューニングで稼いでの AC。「Ruby によるすべての提出」を見ると他３つの AC はプライオリティキューを使用していて時間も 1216 ms から 1804 ms と余裕があるようだった。たぶん
W[X] (X 日目に訪問可能になる街の集合を記憶する配列)に相当する役割を担っているんだろう。■提出 #32487597 (AC / 1027 Byte / 1210 ms)。自分でもプライオリティキューで書いてみた。ずいぶんシンプルに書けた気がしたけど、セグメント木とプライオリティキューのコード量の差により実際にはサイズが増えている。こちらの方が簡単に書けて簡単に読めるけどね。それにも関わらずプライオリティキューを使うんだというヒントをもらうまでは思いつきやしなかったけどね。■■■精進２。第６回PAST-K「共通クーポン」。DP ができなくて解けていなかった問題。■提出 #32492522 (AC / 480 Byte / 340 ms)。N の上限が 10 万だけど、N=10000 で TLE になる明らかにまずい DP をしている。ケースが弱い。■提出 #32492799 (AC / 431 Byte / 215 ms)。こちらが正しい DP。これなら前処理を省いても十分に時間が足りたと思う。この問題の入力は DP よりも前処理の方が効果的であるようなものだけど。1 日に複数本の道を使うことはできないことに注意してください」に阻まれている。それを言われてしまうと厳しい制約の三重苦のもとでどういう状態管理が許されるのかわからなくなるんよ。