第21回日本情報オリンピック　二次予選

2022年2月5日
情報オリンピック日本委員会

解説

解説担当：大佐 健人

小課題 1

N が小さいので，食べる飴の集合 2^N 通りを全探索し，条件を満たす食べ方の中から美味しさの和の最大値を求めればよい．これは2進数または再帰関数で実装することができる．

小課題 2

飴 1 から順に飴を食べるかどうかを決める動的計画法を行うことを考える．直前 K 個のうち食べる飴の集合が分かっていれば，次の飴を食べてもよいかが分かる．そのため，

dp[i][S] : 飴 1 から飴 i までの食べ方を決め，直前の K 個のうち食べる飴の集合が S の時の美味しさの合計の最大値

という DP を行うことで，O(NK2^K) で解くことができる．

小課題 3

小課題 2 の DP について，直前 K 個のうち 3 個以上食べる状態は無視してよい．そのため，直前に食べた 2 個のみを保存する DP を考える．

dp[i][j] : 最後に食べたのが飴 i，最後から 2 番目に食べたのが飴 j の時の，美味しさの合計の最大値

という DP を行い，すべての (i,j) についての dp[i][j] の最大値を答えとすればよい．ここで，制約から，常に 2 個以上食べる解が最適になることに注意する．

遷移は，dp[i][j] ← A_i + A_j で初期化したうえで，

dp[i][j] ← max{ dp[j][k] | k ≦ min(j-1, i-K) } + A_i

となる．この DP は O(N³) で動くので，この小課題を解くことができる．

小課題 4

小課題 3 の DP を高速化することで解ける． M[i][j] = max{ dp[i][k] | k ≦ j } という配列を作り，DP しながらこの配列も更新することで，DP の遷移が

dp[i][j] ← M[j][min(j-1, i-K)] + A_i

と，O(1) でできるようになる．これで全体計算量が O(N²) となったため，この問題の満点が取れる．