ABC313E Duplicate

[tipstar0125]

https://atcoder.jp/contests/abc313/tasks/abc313_e

[tipstar0125]

S = 2 2のときf(S)= 2 2となり、どうやっても減らない。 なので、1以外の数が連続で並んでいる場合は減らないので、このときは-1になりそう。

[tipstar0125]

• 後ろの要素から順に、それを除去できる手数cntを求める。
• SiとSi+1を取得(N >= 2)、初期手数は1とする。
• Si=1, Si+1>0のときは、Siを除去できる手数は、Si+1 * cnt + 1
• Si+1=1のときは、1
• Si>1, Si+1=0のときは、
• Si>1, Si+1>0は-1を出力

[tipstar0125]

S = 2 1 2 1 1 2の場合を考える

2 1 1 1 2 1 1 1 1 2 1 1 1 1 1 2 1 1 1 ...

N=6: cnt=1 N=5: cnt += cnt * 2 + 1 = 3, cnt = 4 N=4: cnt += 1, cnt = 5