ARC027

組み合わせ回。

A.門限

時刻が与えられる。18:00まであと何分か？

やるだけ。

B.大事な数なのでZ回書きまLた。

二つの同じ長さの文字列が与えられる。本来は、同じ数列だったが、アルファベットの場合、未知の数になってしまっている。
数列は、Leading zeroは許されず、アルファベットが同じなら同じ数字を表すとき、可能な数列の数を返す。

片方がアルファベットで片方が数字ならそのアルファベットが確定するので、確定するアルファベットを数字にすべて直す。(置換できなくなるまでちゃんと置き換えること)
先頭からなめて、どちらもアルファベットの場合、そのどちらのアルファベットもそれまでに使われていなければ、10通り(先頭の時は9通り)あるので、掛け合わせる。

C.最高のトッピングにしような

2種類のチケットを組み合わせてトッピングを付けることができる。
スペシャルチケットがX枚、通常チケットがY枚あり、あるトッピングを付ける時はスペシャルチケットが最低1枚使って、そのトッピングを付けるために必要なチケット枚数を満たさなければならない。
各トッピングの必要なチケット枚数とそのトッピングを付けたときの満足度が与えらえる。
満足度を最大化する。

dp[i][j][k]:=トッピングiまで処理して、スペシャルチケットをj枚、通常チケットをk枚使った時の最大満足度
としてしまうと、スペシャルチケットを使う枚数が1枚〜X枚まで可能性があるため、4重ループになってしまい、TLEになってしまう。
(ここまでしかできなかった)

http://www.slideshare.net/chokudai/arc027
スペシャルチケットのループがよくない。スペシャルチケットを何枚使うかを考えなくてもよい方法は？
スペシャルチケットは最低1枚使うことから、つけられるトッピングの最大数はスペシャルチケットの枚数と一致することがわかる。
すると、トッピングの最大数の制限を満たしていれば、スペシャルチケットと通常チケットを区別せずに扱えることがわかる。(チケットの組み合わせ方の情報はいらない)
dp[i][j][k]:=トッピングiまで処理して、トッピングj個使った＆チケットを合わせてk枚使った場合の最大満足度
とすると、3重ループに落とせる。