AtCoder Regular Contest 164 C,E,F問題メモ

AtCoder Regular Contest 164

C - Reversible Card Game

• $N$ 枚のカードがあり、初期状態で表になっている面には $A_i$、裏面には $B_i$ の数字が書かれている
• AliceとBobは、カードがなくなるまで、以下の操作を順に繰り返す
  • Aliceは好きなカードを1枚裏返す
  • Bobは好きなカードを1枚取り、その時点で表になっている数字の得点を得る
• 最終的な得点を、Aliceは最小化、Bobは最大化するように行動するとき、得点はいくつになるか
• $1 \le N \le 2 \times 10^5$

両者とも「表 - 裏が大きいカード」が｛取られたくない/取りたい｝カードなので、 それが最大のカードから｛裏返す/取る｝のがよさそうではある。

で、実際にその通りシミュレートすると通る。

ただ、その方針が最適なのかの証明はちょっと悩ましい。

公式解説による。

Bobが「取りたい向き」をはじめに決めてしまって、その実現可能性を考える。
この時、以下の法則が成り立つ。

• Bobが取りたい向きで取り続ける限り、「取りたい向きが表になっている枚数の偶奇」が保存される。

つまり、初期状態で取りたい向きのものが偶数個だと、

• Aliceが裏返して奇数個（1個以上）→Bobはそれを取って偶数個に戻る

が繰り返され、Bobは全てを取りたい向きで取れる。

奇数個の場合も同様に奇数個の状態が保存される。
Aliceが裏返した後、どこかで0個になってしまう時が訪れる。
その時は取りたくない向きで1枚取るしかないが、 それによって偶奇がずれ偶数個の状態になるので、残りは全て取りたい向きで取れる。

よってBobは、基本は大きい方の数字を取りたい向きとしつつ、 初期状態で奇数個の場合は一番損害（大きい数-小さい数）が少ないカード1枚を、 仕方なく小さい方で「取りたい向き」にしてしまえば、全て取りたい向きで取れる。

貪欲解法の場合も、大きい方が表になっている間は（大-小）が大きい方から取り続け、 どこかで小さい数のみになったら（小-大）が最も大きいものを選ぶようになっているので、 結果的に正しい。

が、ここまで証明できているならもっと効率的な解法があるので、まぁ、ラッキーだったね。

Python3

E - Segment-Tree Optimization

• 長さ $N$ の数列に対する区間クエリに答える二分木を作成する
• 二分木とは、以下の状態を満たすものである
  • 各ノードには $[l,r]$ の区間が定義される
  • 根の区間は $[1,N]$
  • 葉の区間は $[i,i]$（長さが1）
  • 葉以外のノードは必ず2個の子を持ち、ノードの区間が $[l,r]$ なら、子の区間は $[l,m],[m+1,r]$
• $Q$ 個の区間クエリ $[L_i,R_i]$ に答える
  • 各クエリは、根を始点として以下のように探索される
  • 今調べているノードの区間 $[l,r]$ とクエリ区間 $[L,R]$ の関係性が……
    • 共通部分を持たなければ、探索をやめる
    • $[l,r]$ が $[L,R]$ に完全に内包されていれば、探索をやめる
    • それ以外の場合、再帰的に2つの子を調べる
• 二分木を上手く構成することで、「$Q$ 回のクエリで探索されるノードの最大深さ $d$」を最小にしたい
• また、$d$ が同じ中では、深さ $d$ のノードが探索される回数 $c$ を最小にしたい
• 最適な $d,c$ の値を求めよ
• $1 \le N \le 4000$
• $1 \le Q \le 10^5$

問題文は定義を書いているためちょっと長いが、よくある二分木の条件であり、理解はしやすい。

問題設定からは想像つかないような解法になり面白い。

クエリ $[L_i,R_i]$ が来ると、左右の境界 $(L_i-1,L_i)$ と $(R_i,R_i+1)$ は、 探索で木を下っていく過程のどこかで、 「ノードの親子関係 $[l,r]→[l,m],[m+1,r]$ における $(m,m+1)$」として分割されないといけない。
（$L_i=1$ または $R_i=N$ の場合除く）

L  R
2  4   1と2の境界を②、4と5の境界を③で分割
3  3   2と3の境界を④、3と4の境界を①で分割
1  4                   4と5の境界を③で分割

         ①[1, 6]
        ／        ＼
 ②[1, 3]        ③[4, 6]
   /    \           /  \
[1,1] ④[2,3]  [4,4] ⑤[5,6]
         / \            / \
     [2,2] [3,3]    [5,5] [6,6]

境界以外の探索ノードは境界より深くなることはない。最大深さを考える上では境界の深さを考えればよい。

全クエリの中で1度でも現れた境界が、分割必要箇所となる。
⑤は、分割できるノードではあるが、クエリでそこを分割するものが無かったので、分割必要箇所では無い。

葉以外のノード1つにつき1つ分割できるので、高さ $d$ の完全二分木には $2^d-1$ 個の分割を収められる。
よって、分割必要箇所数を $k$ として、$k \le 2^d-1$ を満たす最小の $d$ が、必要な高さの最小値となる。

上記の例でも分かるとおり、分割必要箇所の中でも分割回数に違いがある。

分割必要箇所  ① ② ③ ④
分割回数     [ 1  1  2  1]

このような時、③を表すノードを最大深さの位置に置いてしまうと、回数がかさみそう。
最大深さ以外のノードは何回探索されようと関係ないので、多く分割される境界はなるべく最深以外に配置したい。

高さ $d-1$ の完全二分木から余る個数を $l = k - (2^{d-1}-1)$ とする。
この完全二分木の葉から上手く $l$ 個を選んで、そこだけ深さ $d$ の頂点を作るのがよい。

たとえば9個の分割が必要な場合、深さ3では7個しか分割できないので、残り2個を深さ4とする。分割する葉は好きに選べる。

       ●                    ●
     ／  ＼                ／  ＼
   ●      ●     →     ●      ●
   /\      /\            /\      /\
 ●  ●  ●  ●        ●  ●  ●  ●
 /\  /\  /\  /\        /\  /\  /\  /\
○○○○○○○○      ○○●○○●○○
                          /\    /\
                         ○○  ○○

このとき、新しく作られた $l$ 個の●に対する分割回数の総和×2が、$c$ となる。
（2倍になるのは、分割する箇所は●だが、答えとして数える対象はその下の2つの○なので）

で、小さい方から $l$ 個を貪欲に取ればよいかというと、それはできない。

最深の●の2つの子は即座に“葉”でなければならないので、分割前はあと1回の分割を残すのみの状態にしておく必要がある。
つまり、「隣接する2つの箇所を同時に採用できない」という制約がある。
逆にそれさえ満たしていれば、適切に上位の分割箇所を決めていけば実現できる。

よって、

• $DP[i,j,k]=i$ 個目の分割箇所まで見て、採用したのが $j$ 個で、直前に $k:採用した/してない$

のDPで $O(N^2+Q)$ で求められる。

Python3

import numpy as np

n, q = map(int, input().split())

separators = [0] * (n - 1)
for _ in range(q):
    l, r = map(int, input().split())
    if l > 1:
        separators[l - 2] += 1
    if r < n:
        separators[r - 1] += 1

separators = [s for s in separators if s > 0]
l = len(separators)

if l == 0:
    print(0, q)
    exit()

d = l.bit_length()
m = l - ((1 << (d - 1)) - 1)

INF = 1 << 60
dp = np.full((2, m + 1), INF, np.int64)
dp[0, 0] = 0
for c in separators:
    ndp = dp.copy()
    ndp[0] = np.minimum(dp[0], dp[1])
    ndp[1, 1:] = dp[0, :-1] + c
    dp = ndp

ans = dp[:, m].min() * 2
print(d, ans)

F - Subtree Reversi

• $N$ 頂点の、頂点1を根とする根付き木が与えられる
• この上でAliceとBobがゲームをする
• ルール
  • Aliceから交互に、頂点を1つ選んでオセロの石をAliceは白、Bobは黒を上にして置いていく
  • 置き方
    • 各手番で石を置く頂点は、「自身にはまだ石が置かれておらず、自身の子孫には全て石が置かれている」頂点から任意に1つ選ぶ
    • 頂点 $v$ に石を置いたとき、$v$ の子孫（$v$ 自身を除く）に置かれた石を、全てひっくり返す
  • 全頂点に石を置き終えるとゲーム終了
• ゲーム終了時、Aliceは白の枚数、Bobは黒の枚数をできるだけ多くしようとする
• 両者が最善を尽くしたときの、白の枚数を求めよ
• $2 \le N \le 2 \times 10^5$

結果的に貪欲で解けるのだが、貪欲する「1単位」の発想が難しい。
天啓によって解法がひらめいた後、その正しさを証明するような感じになる。

基本的には公式Editorialを読んだ上で自分なりに解釈したメモとなる。

深さによって、その石が置かれた後、ゲーム終了までに何回ひっくり返されることになるかは決まっている。
（根を深さ0として）深さ偶数の頂点は偶数回ひっくり返されるため、ゲーム終了時には置いた時の色となっている。 奇数は逆の色になる。

よって、両者とも、なるべく偶数の頂点に置きたいし、奇数を相手に押しつけたい。

以下、公式Editorialにならい、深さ偶数の頂点を「赤頂点」、奇数の頂点を「青頂点」とする。
「自身が赤頂点に置く」か「相手が青頂点に置く」たびに、終了時の「自身が多くしたい色の枚数」は+1される。

置いた時点でスコアが決定するので、以下、頂点を交互に「取る」ゲームだと考える。

とりあえず「赤頂点が選べるなら選ぶ」という行動方針を仮定する。
（ひょっとしたら後回しにした方が総合的に見て得する可能性もあるが、そうならないことは後で証明する）

まずは初期状態で葉である赤頂点を取り合うことになるが、いずれ、青頂点しか選べなくなる。
みすみす相手に1枚捧げてしまうこの状況は不利である。“攻守交代”して脱却を図りたい。

   A      B       C
    ：     ：      ：
青  ○     ○      ⑤
    ｜     ｜      /\
赤  ②     ②     ②④
    ｜     /\     ｜｜
青  ①    ①○    ①③

仮に、取ろうとしている青頂点に兄弟が居ない（図A）場合、自分が青頂点①を取ったら、 即座に相手は赤頂点②を取り、自分が「青頂点しか選べない」という状況から脱却できない。

一方、兄弟が居る（図B）場合、自身が①を取ってもまだ②は取れず、「青頂点しか選べない」状況を相手に回すことができる。

ただ、祖先に兄弟が居ればよいというわけではなく、図Cの場合はやはり①→②→③→④→… と、自身が青頂点、相手が赤頂点を取る状況から脱却できない。あくまで、「青頂点」に兄弟が居るのが重要となる。

攻守交代（「青頂点しか選べない」状況を自分から相手に渡す）までに置いた石は、 終了時は全て相手の石になってしまう。

相手の石になってしまう個数を「コスト」と捉えると、 なるべく少ないコストで攻守交代できる青頂点（を含むグループ）を選ぶのが良さそうということになる。

グループのコストは、雑に言うと「その頂点または祖先のうち、最も近い、兄弟の居る青頂点の部分木の頂点数」となる。

赤          ○        ○       グループの例
            /\       ／＼      同じグループは同じ数字（数字は頂点数）
青         ③①    ⑤    ⑨
           ｜      /\   /｜\
赤   ○    ③     ⑤⑤ ⑨⑨⑨  例えば⑨は、⑨内のどれから取っても
     /\    ｜     ｜｜ ｜｜｜  ⑨の根を最後に取るまでは、攻守交代できない
青  ①①   ③     ⑤⑤ ⑨⑨⑨
                           ｜
                           ⑨
                           ｜
                           ⑨

なので、コスト最小のグループの青頂点を選べば、近視眼的には最も相手に渡る枚数が少なく攻守交代できる。

ただ、ややこしいことに、コストはゲームを進めていって、兄弟の中の最後の1つになると変化する。

      ：
赤    ④     開始時点は、①②③は全て"兄弟"が居る頂点だが、
     /｜\    ①、②に石が置かれると、③に置いたら④にも置けるようになってしまうので、
青  ①②③   実質"兄弟"がいない、③の箇所では攻守交代できないことになる

      ：     その場合、③はもっと浅い頂点を根とする部分木の一部として扱う必要がある
      ④
      ｜
      ③

ここでも1つの仮定を置いて、「青頂点しか選べない場合は、攻守交代までのコストが最小のグループ」から取るとする。
すると、兄弟のうち、残るのは最もコストが大きい兄弟となる。

残る兄弟が分かっているなら、その枝だけ親に繋げて同一グループを継続させることで、コストは計算できる。

赤           ◎
        ,---' '---,      同じ記号は同じグループ
青     ◎         ○
     ／  ＼      /｜\    青頂点の兄弟の内、
赤  ◎    ◎    ○☆○   コスト最大のみ親と同一グループになる（同率は適当に1つ）
    /\   /｜\   /\  /\
青 ●◎ ■○◎ ○▲○△  赤頂点は、初期状態で葉の場合を除き、
     ｜   ｜             全て親と同一グループになる
赤   ◎   ★
     ｜                  初期状態で赤頂点かつ葉の場合、
青   ◎                  最初に取るので単独で1グループ

全てのグループのコストを昇順にソートし、 $1,3,5,...$ 番目がAliceが支払うコスト、$2,4,6,...$ 番目がBobが支払うコストとなる。

Bobが支払うコストがそのままAliceのスコア（白の枚数）となる。

ただし、「初期状態で赤頂点かつ葉」の頂点はちょっと特殊処理をして、1頂点で1グループ、コストを「-1」とする。
そのような頂点の個数を $R$ とすると、答えに予め $R$ を足しておくと、つじつまが合う。

「いやいや、単純にコストを昇順にソートするだけで大丈夫なの？ グループ間には取れる順番に依存関係があるけど、まだ取れないはずのグループを先に取ってしまうことは無いの？」
という点が気になるが、実際は「最も重たい頂点を親に残す」という方針である以上、依存関係で後になるグループを取るときは、必ず前になるグループは全て取られていることが保証される。

グループのコストは木DPで求められる。
葉から各頂点に付き「その頂点が含まれるグループ かつ 自身を根とする部分木」の頂点集合のサイズを計算し、親に伝えていく。

子を統合するとき、
赤頂点の場合は「最も重い子だけ残す。他の子がある場合はそこで1グループとして確定させる」、
青頂点の場合は、全ての子を合計する、というように遷移する。

コスト最小のグループから取っていく方針（＝解説の方針）が最適であることを証明する。
（赤頂点もコスト-1の1つのグループとして扱うため、赤頂点から選ぶという仮定の証明も含まれている）

ゲームの進行を固定して、最後に解説の方針に違反した手順を考える。
（その時点の）先手が、最小でないコスト $k$ のグループから1頂点、取ったとする。
「最後に」違反した手順なので、残りの手順は解説の方針に従っているとする。

その時点で残るグループのコストを昇順に $a→b→...→z$ とする。
違反した手順を、昇順に取る手順に変更して、損しないことをパターン分けして示す。

コストの決め方の関係上、末尾の $z$ は最後に取られる1を含む頂点でコストは偶数。他は全て奇数となる。

グループのコストとして取り得る最小値のため、これを取って「方針に違反」することはない。

$k=1$ で方針に違反するということは、コスト $-1$ の赤頂点が残っているのに青頂点を取ったことになる。

この時、残りの並び順は以下のように変化するが、個数の関係上、「はじめて $k$ 以外で-1でなくなるコスト $x$」以降をどちらが取るかは変化しない。
$x$ より前は-1と $k=1$ しかないので、$k$ をもともと後手が取るはずだったなら先手にとって損だし、先手が取るはずだったなら変化しない。

• 違反方針： $(k=1)→-1→...→-1→x→...$
• 解説方針： $-1→...→-1→(k=1)→x→...$

よって先手にとって得になることはない。

先手にとっては、1のコストとなる。
後手にとっては、$k$ のグループが“分割”され、赤頂点の葉が1つ、$k-2$ のグループが1つ増えたことになる。

よって、先手を含めて考えると、

• 違反方針： $1→-1→a→b→c→...→k-2→...$
  • 赤の葉が1つ増えた扱いなので、枚数を求める場合は答えに+1
• 解説方針： $a→b→c→...→k→...$

ここで、末尾以外のコストは全て奇数であること、同一コストなら適当に順番を入れ替えてもよいことを利用すると、
$k-2$ の出現位置は、元の方針の $k$ の位置から変化しないと見なすことができる。

k-2 k-2 k   k k   ←どのkを、k-2にしてどこに挿入しようとも、
        ↓
k-2 k-2 k-2 k k   ←違反方針の並びはこのようになり、
        ~~~         このkだけが変化したと見なすことができる

$a$ 以降の部分をどちらが取るかは元の方針と変わらないので、純粋に $k$ と $k-2$ のみが異なると見なせる。

• $k$ をもともと先手が取るはずだったなら、スコア（後手だけの合計）は変化しない
• $k$ をもともと後手が取るはずだったなら、2だけ損してしまう

ので、いずれにしても先手は得しないことが示せる。

同様に、$k$ は $1,-1,k-2$ のグループに分割されたと見なせる。

$k$ の1つ手前のコスト $j$ が、

$j+1 \lt k$ のとき、$k$ が末尾グループでない時と同様の議論により、$k$ だけが $k-2$ になったとみなせ、得しないことが示せる。

$j+1=k$ のとき、コストの並び順が入れ替わってしまう。

• 元の方針： $a→b→...→j→k$
• 違反方針： $1→-1→a→b→...→k-2→j$

しかし、$j$ のグループは最後に $k$ から剥がされるグループであることを考慮すると、 $j$ の枝と $k$ の枝は根で分岐しておりそこまでは同一サイズだった場合しか無いことがわかる。
頂点1が含まれることで $k$ が1つだけ多くなっていたことになる。

   ○
   /\
  △○
  △○
j △○ k

よって、その時は頂点1を $j$ の側に組み替えることで、

• 元の方針： $a→b→...→j→k$
• 違反方針： $1→-1→a→b→...→k-2-1→j+1$
• つまり…： $1→-1→a→b→...→j-2→k$

このように、末尾以外から取った場合と同様の議論に帰着できる。

よって、違反した部分は、解説の方針に変更して損しないことが示せる。
最初に固定したゲームの進行を、末尾から、違反している箇所を解説の方針に変更していっても損しないので、 解説の方針が最適であると言える。

Python3

n = int(input())
ppp = list(map(int, input().split()))
ppp = [-1] + [p - 1 for p in ppp]

depth = [0] * n
children = [[] for _ in range(n)]
for i in range(1, n):
    p = ppp[i]
    depth[i] = depth[p] ^ 1
    children[p].append(i)

ans = 0
groups = []
subtree_size = [0] * n
for u in range(n - 1, -1, -1):
    if depth[u] == 0:
        if not children[u]:
            ans += 1
            groups.append(-1)
        else:
            heaviest_child_size = -1
            for v in children[u]:
                ssv = subtree_size[v]
                if ssv > heaviest_child_size:
                    if heaviest_child_size != -1:
                        groups.append(heaviest_child_size)
                    heaviest_child_size = ssv
                else:
                    groups.append(ssv)
            subtree_size[u] = heaviest_child_size + 1
    else:
        ssu = 1
        for v in children[u]:
            ssu += subtree_size[v]
        subtree_size[u] = ssu

groups.append(subtree_size[0])
groups.sort()

ans += sum(groups[1::2])

print(ans)