ARC 085

Atcoder Regular Contest 085

（姉貴は関係）ないです

C - HSI

• プログラミングコンテストを確率で通そうとしている
• 1900msかかって1/2で正解する$M$ケースと、100msかかって必ず正解する$N-M$ケースがある
• 通す（Mケースが同時に正解になる）のにかかる時間の期待値はいくつ？

• 各試行は独立
• 1回の試行は$1900M+100(N-M)$ms
• 1/2のランダムがM個同時に正解する確率は$1/2^M$
• 通すまでにかかる回数の期待値はその逆数で、$2^M$
• よって、$(1900M+100(N-M))2^M$

D - ABS

• X さんと Y さんが2人であるゲームをして、最終的にスコアを出す
• X さんはスコアを最大化、Y さんはスコアを最小化するようにゲームをプレイ
• スコアはいくつになる？

ゲームのルールは問題参照

（同じ数字が何回も出てくるので色を付けた）

• 二人零和有限確定完全情報ゲーム
  • ランダム要素は無く互いに情報は全て知っていて、一方の得が一方の損になる
  • 三目並べ、オセロ、将棋など
  • 完全な先読みが可能であり、最善手はゲーム開始時点で一意に決まっている（現実的に計算できるかはともかく）

• 相手に選択肢を与えない（予想）
  • オセロでもそうだけど、こういうのって「相手に選択肢を与えない（少なくする）」と有利に進むことが多い気がする
  • Yさんに選択の余地を与えない方法は、2通りある
    • 初手で$a_{N-1}$まで取ると、相手は$a_N$を取るしか無い
    • 初手で$a_N$まで取ると、相手は何もせずゲームが終わる
  • この場合のスコアは、$abs(a_{N-1}-a_N)$か、$abs(a_N-W)$なので、Xさんは大きい方を選ぶ
  • つまり、少なくとも$abs(a_{N-1}-a_N)$以上にはなる
• この戦略が正しいか、確かめる

• 仮にこの戦略が間違いで、Xさんが$a_i(i<N-1)$まで取るのが最善手だったとする
• Yさんが、なるべくXさんに選択させないと考えたとすると、
  • $a_{N-1}$まで取ると、スコアは$abs(a_N-a_{N-1})$
  • $a_N$まで取ると、スコアは$abs(a_i-a_N)$
• Yさんはこの小さい方を選ぶ
• もしYさんにとってこの2つより良い戦略があったとすると、それはスコアがいずれよりも小さくなる戦略である
• よって、Yさんに手番が回った時点で、スコアは$abs(a_N-a_{N-1})$より大きくなることは無い

• 最初の予想通り、$\max(abs(a_{N-1}-a_N), abs(a_N-W))$でよい

E - MUL

• 宝石が $N$ 個並ぶ
• それぞれに価値 $a_i$ がついている。負の場合もある
• 「正整数 $x$ を選び、$x$ の倍数番目の宝石を全てたたき割る」ことを好きなだけ行える
• 残った宝石の価値を最大化せよ

■$x$ を $N..1$ までデクリメントして、その数でたたき割ることになる宝石の価値合計が負ならたたき割る？

次のような場合で上手くいかない。

1 -50 -49 1 1 50

これをシミュレートすると、$x=6..2$までは割られず、$x=1$で全て割られてしまう。（価値は0）

実際は、$x=2,3$で割ると、価値は2になる。6番目の宝石が、2と3で共通して犠牲になるため、2つ分の働きをする(?)ことを、貪欲法では発見できない。

■燃やす埋める問題に帰結できる。

• 宝石を「割る」「割らない」に分ける
• 「割る」と0円、「割らない」と $a_i$ 円もらえる
• 宝石 $x \ \ (1 \le x \le N/2)$ を割るとき、$2x, 3x, ...$ が割られていないと、罰金∞円

辺に負辺ができるため、最初にもらえる最大の利益をもらった上で、そこからの差分をコストで表現し、コストを最小化する。

↓ 10+20+30=60 を最初にもらったと仮定、そこからの差分で表現

コードは長いけど、最大流を解くDinicは自分でライブラリとして持っておけば、実際に書くのは残りの部分。最大流に置き換える発想に行き着けるかどうかが鍵。

from collections import deque
 
 
class Dinic:
    def __init__(self, n):
        self.n = n
        self.links = [[] for _ in range(n)]
        self.depth = None
        self.progress = None
 
    def add_link(self, _from, to, cap):
        self.links[_from].append([cap, to, len(self.links[to])])
        self.links[to].append([0, _from, len(self.links[_from]) - 1])
 
    def bfs(self, s):
        depth = [-1] * self.n
        depth[s] = 0
        q = deque([s])
        while q:
            v = q.popleft()
            for cap, to, rev in self.links[v]:
                if cap > 0 and depth[to] < 0:
                    depth[to] = depth[v] + 1
                    q.append(to)
        self.depth = depth
 
    def dfs(self, v, t, flow):
        if v == t:
            return flow
        for i, link in enumerate(self.links[v]):
            if i < self.progress[v]:
                continue
            self.progress[v] = i
            cap, to, rev = link
            if cap == 0 or self.depth[v] >= self.depth[to]:
                continue
            d = self.dfs(to, t, min(flow, cap))
            if d == 0:
                continue
            link[0] -= d
            self.links[to][rev][0] += d
            return d
        return 0
 
    def max_flow(self, s, t):
        flow = 0
        while True:
            self.bfs(s)
            if self.depth[t] < 0:
                return flow
            self.progress = [0] * self.n
            current_flow = self.dfs(s, t, float('inf'))
            while current_flow > 0:
                flow += current_flow
                current_flow = self.dfs(s, t, float('inf'))
 
 
n = int(input())
an = list(map(int, input().split()))
mf = Dinic(n + 2)
max_value = 0
for i, a in enumerate(an):
    i += 1
    if a > 0:
        max_value += a
        mf.add_link(i, n + 1, a)
    else:
        mf.add_link(0, i, -a)
    for j in range(2 * i, n + 1, i):
        mf.add_link(i, j, float('inf'))
print(max_value - mf.max_flow(0, n + 1))