Candies - ioi-jp.org例 このようなおいしさの飴があるとき 1つ選ぶ 7美味い...

Candies 解説坂部

問題内容・長さNの自然数列A[i]がある。

・1<=K<=N/2(切上げ)の全てのKについて、A[i]の中からK個を選んだ和を最大化したい。

・ただし、隣り合う2数を選んではいけない。

例このようなおいしさの飴があるとき

3 5 1 7 6

例このようなおいしさの飴があるとき

1つ選ぶ 7美味い

2つ選ぶ 12美味い

3つ選ぶ 10美味い

3 5 1 7 6

3 5 1 7 6

3 5 1 7 6

3 5 1 7 6

例このようなおいしさの飴があるとき

1つ選ぶ 7美味い

2つ選ぶ 12美味い

3つ選ぶ 10美味い

3 5 1 7 6

3 5 1 7 6

3 5 1 7 6

3 5 1 7 6

これを出力

小課題1(8点)

N <= 2,000

・そんなに大きくない

・O(N2)が通りそう。

小課題1(8点)

DP[i][j] : A[0]～A[i - 1]からj個選ぶ時の最大値

としてDP

小課題1(8点)

◦この中から3個選ぶとき

小課題1(8点)

◦この中から3個選ぶとき

◦赤枠の中から2個と右端 もしくは

◦赤枠の中から3個

× ○

×

小課題1(8点)

DP[i][j] : A[0]～A[i + 1]からj個選ぶ時の最大値

としてDP →O(N2)で解ける

小課題1(8点) 解法2

K個選ぶときの最適解と、K+1個選ぶときの最適解を見比べてみるK = 1K = 2K = 3

3 5 1 7 6

3 5 1 7 6

3 5 1 7 6

小課題1(8点) 解法2K + 1個選ぶときの最適解は、K個選ぶときの選び方と比較して

①両隣がまだ選ばれていない飴を新たに選ぶ

②×○×…○×→ ○×○…×○

のいずれか。

(どちらでもない場合、①で新たに選ばれる飴があるにも関わらず、その他の飴の位置がいくつか変わっており、このときK+1個の選び方の最適性より、K個の選び方の最適性に矛盾。)

小課題1(8点) 解法2このとき、下の形は、

A B C

小課題1(8点) 解法2以降下の2パターンにしかならないので

A B C

A B C

小課題1(8点) 解法2(B点の差はあるが)右の形として考えられる。

=

=

A B C

A B C

A + C - B

A + C - B

小課題1(8点) 解法2また、端の飴を選んだ場合、その部分は以降変更されないので、考えなくて良い。

○ ×

小課題1(8点) 解法2

K = 1 7おいしい

K = 2 12おいしい

K = 3 11おいしい

3 5 1 6 7

3 5 1

-1

小課題1(8点) 解法2

これを愚直に実装して、O(N2) → 解けた

小課題2(累計100点)

N <= 200,000

・大きい。

・O(N2)はTLE

小課題2(累計100点)

さっきの方法は、更新されていない所の価値の大小を何度も比較していて、効率が悪い。

小課題2(累計100点)

priority_queueなどを用いて無駄な計算を省く。

※ただし、priority_queueから出てきた情報が古い可能性があり、区間管理などが必要。

小課題2(累計100点)

一例(区間を管理する配列を持つ)

A[i] A[i + 1] A[i + 2]

i i + 1 i + 2

複雑 -INF -INF

i + 2 i + 1 i

小課題2(累計100点)

O(NlogN) → 解けた

小課題2(累計100点)

※分割統治解など別解あり

得点分布

小課題1

小課題2

面積は、総得点の量を表す。