CODE FESTIVAL 2018 qual A C - 半分
解法
動的計画法で答えを求めていくことを考えていきます。
まずは特徴についてです。
この問題では、0がとても重要なものになっています。
数列に0が存在していた場合、0は何回2で割っても0になるので、この部分を利用して与えられたの調整が可能になります。
また、であった場合でも、60回程度2で割ることで0になります。
ということで、いかなる数字も、たかだか60回の操作を行うことで0になるので、その部分を利用して回数の調整が行えます。
ということで、すでに数列に0が存在しているかどうか、が重要になっていることがわかります。
あとは、
番目までの数字を合計
回操作したときの数列の組み合わせの個数(ただし
0のときは数列に0が存在せず、1のときは存在する)
として、答えを求めたくなります。
が、このままだと、与えられるKはまでありうるので、このままだと一見間に合わないように見えます。
ですが、先ほども述べたように、はたかだか60回割ることですべて0になってしまうので、
の場合でも、
ほどあれば十分であることになります。
ということで、先ほどのdpを利用して答えを求めていくことにします。
答え自体は、
となっています。右の項については、
で全探索をすることになります。
重複組み合わせのの解法で間に合うので、そちらを利用します。
基本的には、は0でも1でも同様の処理が行えます。
を、2で割って行って0にするために必要な回数を
とします。
となります。
加えて、であったときのみ、
という操作が加わります。
あとは、この操作をもとにDPを繰り返していけば、答えが求まります。
