キーエンスプログラミングコンテスト 2021 E - Greedy Ant に関する記事です．

問題へのリンク

https://atcoder.jp/contests/keyence2021/tasks/keyence2021

解法

公式解説 の通りではありますが，若干表現を変えます．

すぬけ君が，蟻から遠い飴を取っても，蟻の行動には直ちには影響を与えません． そういう状況ではすぬけ君は「スキップ」することにして，後から蟻がその飴に近づいてきたとき (左右いずれかで蟻の最も近い飴になったとき) に取ることにしても，ゲームの意味が変わりません． つまり，次のようにゲームを言い変えることができます． (両端などの扱いはサボっています)

初期化:              // 蟻の初期位置を 2n + 1 とする．
    l := n           // 蟻に最も近い左の飴の位置が 2l
    r := n + 1       // 蟻に最も近い右の飴の位置が 2r
    k := 0           // すぬけ君の「スキップ」回数
ループ:
    k += 1
    while k > 0:
        match すぬけ君の選択():
            case なし: break
            case 左: すぬけ君が 2l の飴を取る; l -= 1
            case 右: すぬけ君が 2r の飴を取る; r += 1
        k -= 1
    蟻が，2l, 2r の飴のおいしい方を取る
    取った方に応じて l -= 1 または r += 1

そこで， f(l,r,k) を，「上記 while の先頭位置で，l,r,k がこの値である時に，すぬけ君がこのあと取る得点の最大値」として 定義します． 次の漸化式が書けます．

f(l, r, k) = max( none(l, r, k)
                , a[l] + f(l - 1, r, k - 1)
                , a[r] + f(l, r + 1, k - 1)
                )
ただし，a[l] > a[r] のとき，none(l, r, k) = f(l - 1, r, k + 1)
そうでないとき，            none(l, r, k) = f(l, r + 1, k + 1)

f(n, n + 1, 1) が求める答です． fは，メモ化再帰で計算でき，時間計算量は O(N^3)です．

経緯

コンテスト中も解けず，復習でも答を思い出せませんでした．blogに書くことで覚えられるか???