20時開始。5完。普通。苦手セットばっかりってことは実力が低いんだよな。はあ、つまんない人生だ。
A - box
引いて足すだけに見える。ボールは0個以上だろうけど問題文のどこにそれがあるだろうと探して、制約でNが100以上なのを見つける。
B - Various distances
xが小さいけどintではオーバーフローするからいじわるだと思ってたけど、今気づいた。自分の解法はxが10^9とかになるとオーバーフローする。はー嘘考察してたのか。基本的に整数で処理して最後にsqrtを使う。なんだかんだ時間かかった。
C - Cream puff
約数を小さい順に出力するだけ。簡単だ。しかしどう書くのが速くて間違いにくいか。√N以下を出力して次に√Nより大きいのを出力するのは高速だがN=1とかコーナーケースが心配。約数をダブりがあってもいいから全部生成してsort, uniqueというのは面倒だけど思考停止で書けてしかも確実。こっちにした。このくらい瞬殺できないものかとも思うが。
D - Takahashi Unevolved
これもよく見ると簡単。増える量が少ないほうをやっていけばよくて、A倍するほうは悪化する一方でBを足すほうは変わらないので、B足すよりいい間だけA倍して（この回数はO(log(Y))）その後何回Bできるかは割り算で求める。簡単な問題は素早く書かなければいけない。が、やはりD問題だけあって難しいところがあった。増える量を普通に計算するとオーバーフローしてしまう。また、A倍したほうがいい場合でもそもそもA倍するとY以上になってしまうという場合はやっちゃダメだ。ピッタリYになってもダメなのが忘れやすい。見た目の簡単さに反してかなりキツい展開。オーバーフローしないようXの上限を雑に設定する。割り算でY/Aとかしたいけど、整数に丸めるからちゃんと考えないといけない。Y/A+1であればいいか？(Y/A+1)*A（除算は切り捨て）は、Yより大きいよね。で、1じゃなくて10を足して提出しちゃった。
E - Traveling Salesman among Aerial Cities
下がるときだけノーコストなのね。17なので3^17がなんとかいける、2^17*17^2も大丈夫。問題特有の性質は使わずdp[N][2^N]でやっちゃうか。書いてて気づいたけど同じ都市を何度も通る展開があるなら訪問済み都市の集合が同じものからも遷移する。計算量が増えて危うくなりそう。とりあえずサンプルだけ少しの試行錯誤で通して、少し考える。しばらくして、このコストは「距離」なんじゃないかと気づく（今気づいたけど行きと帰りで違うから距離ではない）。三角不等式を満たしていそうなので、つまり同じ都市を2回通るケースは考えなくていい。都市1を2回訪れるのがややこしいが、初手がN-1通りしかないのでそれをDPテーブルに入れてしまう。今回は全体的に、どう実装するのがいいかよくわからないままになってしまっていた。
F - Unbranched
300^3っぽいのでメモ化再帰を考える。木の数え方もわからんし、それがわかったとして辺を増やしたら合流しちゃうし。一番大きい塊を除くと考えても一番大きいのが複数あるかもしれないし。さすがにむずい。
