問題 1からNまでの数字をすべて書き出したとき、「1」は何回書いたか？ 1 考え方 愚直に数えると、O(N*桁数)かかってしまって間に合わない。 以下、1からではなく、0から考えても問題ない。 桁DP 最大桁から考える。 ここで、Nが3桁「xyz」であると仮定する…

問題 N種の料理からM種を順番に選んで食べる。 このとき、各料理自体の満足度の他に、料理iの直後に料理jを食べた場合の追加満足度もある。 満足度の最大値を求める。 1 0 0 考え方 N種からM種選んで、その順番を列挙する方法だと、O(2^18 * 18!)で間に合わ…