2/3 日記
眠すぎる
応用情報の締め切りは来週までか～
詰め切るのが難しかった。
メニューの周期はDであることと、好みの料理を食べる回数⇔食堂の利用回数の関係を利用したいので、ダブリングが有効であると考えられる（i日目とj日目のメニューがCi=Cjであり、i ~ j の間にそのようなメニューが無いとき、L日間がiとjの間にいくつ入るかは( i - j -1 ) / Lで求めることができる。これから、
sum[now][j]=sum[now][j-1]+sum[nxt][j-1]の要領で、2^k回好みの料理を食べたとき、好みの料理以外を食べた回数が高速に求められる）。
i 番目の人につき、FiからスタートしてメニューがKiである日まで移動する（これは二分探索等を使う）。そこからは桁DPのようにやればいい（具体的には、
Ti≧2^p + sum[now][p]のときに、Ti-=2^p+sum[now][p], now=pos[now][p]
といった更新を行えばいい。
ところでこれ、Wavelet Matrixで解けないかな。
括弧が絡む問題は、スタックに見立てると上手くいくことが多いのかな。
今回はそれで上手くいく。( が来たらscoreを+1, )が来たらscoreを-1することを考える。dp[i][score]:=i番目までみて合計がscoreであるときにかかる費用の最小値 とすると解ける。scoreが負にならないようにし、i 番目の文字に対する操作をもとに遷移を考えればいい。
考え中。
