読者です 読者をやめる 読者になる 読者になる

アルゴリズム忘備録

競技プログラミングとかデータ分析とか

SRM712 Div1 Easy LR

整数列s, tが与えられる。sの整数列について、次の操作LまたはRを施す。

  1. 操作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], ...}
  2. 操作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以下になるので、最大値になる前に失敗と判定する。