SRM712 Div1 Easy LR
整数列s, tが与えられる。sの整数列について、次の操作LまたはRを施す。
- 操作L:{..., a[i], a[i+1], a[i+2], ...} -> {..., a[i] + a[i-1], a[i+1] + a[i], a[i+2]+a[i+1], ...}
- 操作R:{..., a[i], a[i+1], a[i+2], ...} -> {..., a[i] + a[i+1], a[i+1] + a[i+2], a[i+2]+a[i+3], ...}
LRの操作を100回以内で繰り返して数列tに変換できるならば、その操作列を求めよ。変換できない場合はNo solutionを返せ。
操作Lと操作Rは可換である。そのためLとRの数がそれぞれ決まればよい。あとは愚直に操作をしてみて、一致したらその数だけLとRを並べて返す。Lの数とRの数を決めたら毎回その分だけ操作をするとTLEするので、ちゃんとDPっぽいことをする。また、数列の中の数値がLong maxを超えたら0以下になるので、最大値になる前に失敗と判定する。