トヨタ自動車プログラミングコンテスト2023#8（AtCoder Beginner Contest 333）

 　Eまで五完でさらにレートを落とす。

コンテストへのリンク

コンテスト後のツイート

トヨタ自動車プログラミングコンテスト2023#8（AtCoder Beginner Contest 333） Fで三乗DPしか思いつかずひどいことに。
C 全部列挙
D 木DP
E 後ろから見る。
F N-1での答えに、x=2^N-1として、1/x,2/x,4/x,...みたいなのを掛けて足すとNでの答になる。高速化が思いつかず埋め込みしようとかして破滅。

— titia (@titia_til) December 16, 2023

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を求め、それで更新すれば良い。