SRM487 Div2 500

問題

かうぁいこちゃんがコンテストの練習をする。コンピュータを使って問題を解くときは以下の順序で解く。

1. 1単位時間コンピュータを使う
2. k単位時間は手計算で計算する
3. 1単位時間コンピュータを使う

複数のかうぁいこちゃんが同時にコンピュータを使うことはできない。
一日の各単位時間にはpreferenceが割り当てられており、なるべくそれの合計が大きくなるようにしたい。合計が最大になるように使った場合のpreferenceの合計値を返す。

考え方

dfsで普通に回すと、50個k=1の時にTLEする。
合計値は一意にきまるので、まとめた({3,1,4,1,5,9,2,6},k=2なら{4,6,13,3,11}のように)。
このとき、i番目で使うと、他の人はi+k+1番目では使えない。すなわち、{i,i+k+1,i+2k+2,...}の順番を適切に選んでその合計が最大になる値を合計する(j番目を使ったらj+1番目は使えない、j番目を使うかどうかで全探索した)。この値は、最大でも48個で、j番目を使う場合、次はj+2番目をチェックすることになるので、探索区間はそんなに大きくならず、dfs回探しても間に合った。

想定解法は、i番目を基準にk個飛ばしにある値の数が偶数ならすべてうまく使うことができて、奇数なら奇数番目にある一番小さい値を消せばその値をうまく選ぶことができるので、その合計値は最大となる。なので、それぞれに対し、計算した合計値が答えになる。らしい。

反省

いい問題だった。サクっと解けるようになりたい。