yukicoder contest 184

No.651 E869120 and Driving

10km進むのに6分かかる、ということに気づく(?)のが大変だった。そのぶんの時間を足して、繰り上げていく。出力はprintf。

No.652 E869120 and TimeZone

1問目のコードを流用できる。doubleへ変換するのが慣れなくて、ググってatofを使ったが、俺が使いたかったのはstodだった。9時間を引くのは、代わりに24-9時間を足す。現地時間に直すときもマイナスになり得るのを忘れて1WA。
(追記)落ちてた(doubleで0.1は表現できない)。あとから「大丈夫なんだな」と思った記憶はあるが、大丈夫じゃなかった。

No.653 E869120 and Lucky Numbers

一の位から順に見ていく。キャリーフラグを持ちながら見ていく。最上位の1を確認してなかったのと、0桁の数は使えないのを忘れたので2WA。頭が澄んでないとしんどい問題(しんどかった)。

No.654 Air E869120

「あちらを立てればこちらが立たぬ、これはフローか!?」「N*Mサイズ(頂点数も辺の数も)のグラフで表現できる」というアイデアはしばらく考えて出ていた。ただ、辺数100万だとフローは無理。1000なら行けるかもしれないが、そこまで減らせるだろうか。
O(N*M)の時間をかけて前準備ができないかをかなり長く考えていたが、街を頂点とするとどうしても表現力が足りない気がする。そこで、最初から考えにあった座標圧縮を、各街について行うことを考えた。よく考えたら「街と発着の時刻の組合せ」を頂点にしても頂点数はO(M)にしかならない(ある街の頂点数が増えれば他の街のが減る)。
あとは実装だが、これがめちゃくちゃ重い。座標圧縮を理解していないことがよくわかった。対処が必要なコーナーケースが頭に浮かんでも、一度に実装できるのは1個だけなのでほんと大変。少しずつ書いて、終了直前になって意外にも完成した。しかし、ライブラリのDinicの容量がintであること(そしてそれでは足りないこと)にはとっくに気づいていた。提出したが、当然のWA。終了後、int64_tにしたらACしたので、まあよかった。見返すと苦労したわりにコードがきれいで、正しいコードを書けるときはこんなもんなんだなと思った。