問題 arc060.contest.atcoder.jp 解法 n = |w| とします。全て同じ文字で構成されている場合答えが n 1 となること, および w が良い文字列である場合答えが 1 1 になることは明らかです。その他の場合は最良表現が 2 になることが分かるようです。よって, …

問題 arc060.contest.atcoder.jp 解法 本番はよくわからない解法で通したのですが, そちらも紹介したいと思います。ある数 n に対して b を決めると, 次のような規則性があることに気付きます。n/2+1 から n までは f(n/2+1, n) から始まって 1 ずつ f(b, n)…

なんだかんだ 3 完できてうれぴー。 問題 arc060.contest.atcoder.jp 解法 クエリでは a 戦略としては, 「その日にたどり着けるところまでなるべく遠くへ行く」というのが明らかに最適です。ということで, nxt[0][i] = (頂点 i からなるべく遠くへ行こうとし…