Codeforces 580D. Kefa and Diches

こどふぉす

N種の料理からM種を順番に選んで食べる。
このとき、各料理自体の満足度の他に、料理iの直後に料理jを食べた場合の追加満足度もある。
満足度の最大値を求める。

1<=m<=n<=18
0<=k<=n*(n-1)
0<=満足度<=10^9

N種からM種選んで、その順番を列挙する方法だと、O(2^18 * 18!)で間に合わない。
選ばれたM種から最大となるような順序を効率的に求めることを考える。

これは、今まで食べた料理の情報と最後に食べた料理のbitDPで考えられるので、
dp[今まで食べた料理][最後に食べた料理]:=満足度の最大値
で更新すればよい。

さらに、NからMを選ぶ組み合わせとbitDPを分けて考える必要はなく、全部の料理でのbitDPでM個以下のものだけを使えばよいので、O(2^18 * 18 * 18)で済む。

ABC029 D. 1

その他

1からNまでの数字をすべて書き出したとき、「1」は何回書いたか？

1<=N<10^9

愚直に数えると、O(N*桁数)かかってしまって間に合わない。
以下、1からではなく、0から考えても問題ない。

最大桁から考える。
ここで、Nが3桁「xyz」であると仮定する。
100の位は0〜xまであり得るが、0〜x-1までは、10の位以下は00〜99までの1の出現数、xの場合は00〜yzまでの出現数を使ってDPで求められる。

1の位は01234567890123456・・・を繰り返しており、10の位は00000000001111111111・・・・というパターンを繰り返している。
1の出る回数はそれぞれの桁でO(1)で求められるので、全体でO(桁数)しかかからない。