CODE FESTIVAL 2015 あさぷろ Hard A - 一次元オセロ

問題原文

atcoder.jp

解法

は奇数 と制約に あるので、 白, 黒, 白, 黒, 白 みたいになっている。
おける黒は両端のどちらかで、どちらかに黒を置いた後、白の選択は一意に定まる。

これで

• 左端に黒を置いた時にひっくり返す枚数（次の白の手番まで考慮）
• 右端に黒を置いた時にひっくり返す枚数（次の白の手番まで考慮）

がわかる。

で、実は次の一手（白の手番まで考えると二手）までで、ひっくり返す枚数がより小さい方に置く貪欲法で解ける。
二手後の選んだ方に出現する白の連続は、当然今見ている白の連続より長くなるのでそれはそうという感じ。
ざっくりいうと、あえて損して次にそのおかげで得するようなことがない。

実装

なんだこのくそこーどはぁ！！！

from collections import deque
N = int(input())
A = list(map(int, input().split()))
que = deque(A)

ans = 0
while len(que) > 1:
    l_cost = 2 * que[0] + que[1] + 1
    r_cost = 2 * que[-1] + que[-2] + 1

    if l_cost < r_cost:
        ans += l_cost
        append_l = que[0] + que[1] + que[2] + 2
        que.popleft()
        que.popleft()
        que.popleft()
        que.appendleft(append_l)
    else:
        ans += r_cost
        append_r = que[-1] + que[-2] + que[-3] + 2
        que.pop()
        que.pop()
        que.pop()
        que.append(append_r)

print(ans)

感想

推定diff1600弱らしい〜
令和ABC-Dに置かれて3000人解きそう。（個人の感想です）