Eまで五完でさらにレートを落とす。
コンテスト後のツイート
F - Bomb Game 2
三乗DPはまあまあすぐ分かったけど、遷移の式を見て高速化できない気がして、「別の方針で二乗になるのかな？」と思ってしまった。
でも自分は三乗しか思いつけなそうだから埋め込みを試みよう、と思ったが思ったより埋め込む個数が多くなりそうで困り、C++へ書き換えたりとかしているうちに時間切れ。
落ち着いて自分の書いた式を見返せば、確かに二乗に落とせた。
埋め込みしようとか考えず計算量を落とすことに集中していれば解けた気がしないでもない。
Unratedで出ているときと違い、Ratedだと雑念も混じってしまうしね……。
G - Nearest Fraction
解説AC。
Stern–Brocot木を使って小数を既約分数で近似する問題。知識問題という感じですね。Pythonではライブラリでも解けたようだけど、実装もそれほど難しくない。
まずleft=[0,1],right=[1,1]としておき（第一要素が分子、第二要素が分母）、mid=[left[0]+right[0],left[1]+right[1]]とrの大小を比較する。
そして、たとえばmid<xならばleftを更新したいのだが、その際、[left[0]+k*right[0],left[1]+k*right[1]]が条件を満たすような最大のkを求め、それで更新すれば良い。