−目次

ARC 087
- C - Good Sequence
  - 問題
  - 解法
- D - FT Robot
  - 問題
  - 解法
- E - Prefix-free Game
  - 問題
  - 前提
  - 解法

ARC 087

AtCoder Regular Contest 087 - AtCoder

C - Good Sequence

問題

数列 $a=\{a_1,a_2,...,a_N\}$ から好きなだけ要素を消し、以下の条件の数列にする
条件: 整数 $n$ が数列に含まれている時、 $n$ は丁度 $n$ 個含まれている
最も消す要素数を少なくした場合、いくつ消すことになるか

解法

各整数の数を数える。含まれる各整数につき、

整数 $n$ が $n$ 個未満なら全部消すしかない
整数 $n$ が $n$ 個以上なら、 $n$ 個残して消す

        
              from collections import Counter
 
input()
ac = Counter(map(int, input().split()))
ans = 0
 
for a, c in ac.items():
    if a > c:
        ans += c
    else:
        ans += c - a
 
print(ans)

（なんか前回もC問題はCounter使った気がする）

D - FT Robot

問題

ロボットを、与えられた命令に従って動かした時、指定の座標で移動を終えることが出来るか判定する
ロボットは始め、2次元座標の原点(0,0)に、x軸正の向きで静止
命令は'F'と'T'からなる文字列で、'F'なら向いている方向に1進み、'T'なら右か左好きな方に90度回転する
可能なら'Yes'、不可能なら'No'を出力する

解法

命令を'T'で分割した時、偶数番目(0-index)はx軸方向、奇数番目はy軸方向に独立して考えられる。

連続する'F'の数だけ、正か負の好きな方に進める（ただし最初の移動のみ、正方向限定）

FFFFFTFFTFFFFTTTFFF
↓Tで分割
FFFFF T FF T FFFF T T T FFF
↓連続するFを数える
5 2 4 0 0 3
↓
最初は正方向限定なので、(5,0)からスタート
y軸方向に +2 or -2
x軸方向に +4 or -4
y軸方向に +0 or -0 (動かない)
x軸方向に +0 or -0 (動かない)
y軸方向に +3 or -3
これで移動できる範囲を、動的計画法により求める

        
              def solve(s, x, y):
    def update(move):
        ncx = set()
        cx = cxy[is_x]
        for x in cx:
            ncx.add(x + move)
            ncx.add(x - move)
        cxy[is_x] = ncx
 
    spl = map(len, s.split('T'))
    is_x = 1
    cxy = [{next(spl)}, {0}]
    for l in spl:
        update(l)
        is_x ^= 1
 
    return x in cxy[0] and y in cxy[1]
 
s = input()
x, y = map(int, input().split())
print('Yes' if solve(s, x, y) else 'No')

E - Prefix-free Game

問題

文字列 $s$ と $t$ が「prefix-free」とは、 $s$ が $t$ の接頭辞でなく、 $t$ が $s$ の接頭辞でもないことをいう

たとえば、'0010' は '0010110'の接頭辞である

ある文字列集合 $S$ には、はじめ、以下の条件を満たすいくつかの文字列が入っている
- 各文字列は、長さ1以上 $L$ 以下であり、文字'0'と'1'のみからなる
- 要素はどの2つを取っても、prefix-freeである

AliceとBobは、 $S$ に、条件を守りながら交互に文字列を追加する。Aliceが先攻
追加できなくなったら負け（最後に追加した方が勝ち）
どちらも最適に行動した場合、どちらが勝つ？

前提

いわゆる「定番問題」らしい

競技プログラミングにおいて、この「2人交互に操作して、出来なくなった方が負け」という問題は、「Nim」に帰着させるという解法が当てはまる場合がそこそこある。知っていればピンと来る。逆にこれを知らずに解くのは並大抵の発想では無理な気がする。

ただ、今回の問題は少し適用に工夫、というか知識が必要。

Nim

石取りゲーム参照。

端的に言うと、

石取りゲームにおける石山のように、いくつかの「山」がある。プレイヤーは1度に1つの山しか操作できない
終端状態がある（状態はループせず、どんな状態からでもいつかはそれ以上操作できなくなる状態になる）

という場合、山の「状態」を1つの整数（grundy数）で表すことで、以下の必勝法が成り立つ

全ての山のgrundy数のXORが、初期状態で0なら後手必勝、それ以外なら先手必勝（最後に操作した方が勝ち）

これは、grundy数を適切に設定すると、以下が成立するためである。

XORが0の状態から操作して、0の状態を維持することは出来ない
XORが0でない状態から、0の状態にする操作が必ず存在する
→自分が取った後のXORを0に維持することで、必勝

「適切なgrundy数の設定方法」は、以下である。

終端状態のgrundy数は0である
ある状態のGrundy数は、そこから遷移可能な状態のGrundy数に含まれない最小の非負整数

解法

「状態」とgrundy数を求める

集合に追加できる文字列の候補は、完全二分木で表せる

        ○      ←便宜的なダミーノード
      ／  ＼
    ０      １     ^
   ／＼    ／＼    |
  ０  １  ０  １   L
  /\  /\  /\  /\   |
 ０１０１０１０１  v

ここで、たとえば集合に「10」という文字列があると、追加できない文字列（10とprefix-freeでない文字列）は以下になる

        ○
      ／  ＼
    ０      ×    ●: 「10」を示すノード
   ／＼    ／＼   ×: 「10」により追加できなくなった文字列を示すノード
  ０  １  ●  １
  /\  /\  /\  /\  根から●までの経路と、
 ０１０１××０１ ●を根とした部分木以下のノードが×になる

つまり、この問題は以下に言い換えられる。

高さ $L+1$ の完全二分木がある
はじめからいくつかの頂点が黒く塗られている
交互に、根以外の頂点を1つ選んで黒く塗る。
その際、黒く塗られた頂点 $v$ があると、根から $v$ までの経路上のノードと、 $v$ を根とする部分木上のノードは、選べない
最後に黒く塗った方が勝ち

あるノードを黒く塗ったとき、次に塗ることが可能な範囲はいくつかの部分木に分割される。この部分木は、一度に2つ以上に影響を及ぼす操作ができない。これがどうやらNimの「山」に相当しそうである。

    ０
   ／＼
  ０  １      １
  /\  /\      /\
 ０１０１    ０１

各部分木は、必ず完全二分木の形になる。grundy数は木の高さ $d$ に依存しそうである。（おそらく「どんな部分木でもgrundy数が同じ」ということはないだろうから、何か部分木同士で違いがあるとすれば、それは高さくらいしか無い、という勘）

ここで、高さが $d$ の部分木のgrundy数を $g(d)$ と表す。

$d=0$ は、山がない状態。つまり終端状態なので、 $g(0)=0$ とする
$d=1$ のとき、遷移できるのは山が無い状態(d=0)のみ
- つまり、遷移できる「状態」は $g(0)=0$ のみ
- $g(1)=1$
$d=2$ のとき、遷移できるのは

      追加文字列  1    10    11
 １              ●    ×    ×
 /\              /\    /\    /\
０１            ××  ●１  ０●

d=2からは、d=0 or d=1 の状態に遷移できる
つまり、遷移できる「状態」は、g(0)=0 or g(1)=1
なので、遷移できない最小の数は2、$g(2)=2$ となる

$d=3$ のとき、以下のいずれかに遷移

       追加文字列  0       00      000
    ０            ●       ×       ×
   ／＼          ／＼     ／＼     ／＼
  ０  １        ×  ×   ●  １   ×  １
  /\  /\        /\  /\   /\  /\   /\  /\
 ０１０１      ×××× ××０１ ●１０１

追加文字列	遷移状態
0	全て消える。遷移状態: $g(0)=0$
00	d=2の部分木が残る。遷移状態: $g(2)=2$
000	d=2とd=1の部分木が1つずつ残る。遷移状態: $g(2) \oplus g(1)=2 \oplus 1 =3$

追加文字列の長さが同じなら、残る木の形も同じ
よって、 $d=3$ から遷移できるのは{0,2,3}なので、含まれない最小の数 $=g(3)=1$

一般化して、 $d=d_e$ のときの遷移を考える
$1 \le d_i \lt d_e$ の $g(d_i)$ は既に計算済みとする

追加文字列	遷移状態
0	全て消える。遷移状態: 0
00	$d=d_e-1$ の部分木が残る。遷移状態: $g(d_e-1)$
000	$d=d_e-1$ と $d=d_e-2$ の部分木が1つずつ残る。遷移状態: $g(d_e-1) \oplus g(d_e-2)$
…	…
00…00 ( $d_e$ 個)	$d=d_e-1$ ～ $1$ の部分木が1つずつ残る。遷移状態: $g(d_e-1) \oplus g(d_e-2) \oplus ... \oplus g(1)$

dを途中まで求めると、以下のようになる。

d		0	1	2	3	4	5	6	7	8
grundy数		0	1	2	1	4	1	2	1	8

どうも、「自身を割り切ることの出来る最大の2のべき乗数」のようだ。

grundy数は理論から立式するのは難しいことが多く（答えである以上、証明は出来るのだろうが）、実験してみて予想した方が速い、と解説生放送で言ってた。

実装

さて、grundy数は分かったが、後は初期状態のgrundy数のXORを取るために「山」をどうやって表すかが問題となる。

そのまま二分木で表そうとしても、制約で文字列の長さの上限が $10^5$ のため、最悪の場合indexが $2^{10^5}$ となり、エラー。（多倍長整数をデフォルトでサポートするPythonなら扱えてしまうが）

trie木

トライ木

trie木を作ると、不必要なノードは保持しないので、効率よくindexを割り振れる。

今回、子は多くとも2個なので、各ノードは[0, 0]の要素2個の配列で持つ
trie木全体は、ノードのリスト[[0, 0], [0, 0], ...]で持つ
ノードの数字は、子の、ノードリストでのindexを示す。左が文字'0'、右が文字'1'を示す
子のノードが未生成の場合、-1とする

文字列'101', '11' を追加すると、以下のようになる。

trie = [[-1, -1]]    : まず、ルートノードだけを持つ配列trieを生成
        ○[0]

[[-1, 1], [-1, -1]]  : '101'の先頭の'1'を追加したところ
        ○[0]        : trie[0][1]を、次ノードのindexである"1"に変更
          ＼
            １[1]

[[-1, 1], [2, -1], [-1, 3], [-1, -1]]
                     : '101'を追加したところ
        ○[0]
          ＼
            １[1]
           ／
          ０[2]
           \
            １[3]         

[[-1, 1], [2, 4], [-1, 3], [-1, -1], [-1, -1]]
                     : '11'を追加したところ
        ○[0]
          ＼
            １[1]
           ／＼
       [2]０  １[4]
           \
           １[3]

こうすると、各ノードの状態の数は、

自身が「-1」なら、自身を根とした部分木の高さを $d$ として、 $g(d)$
自身が存在するノードなら、自身の2つの子の状態の数のXOR

で表現できるので、根から再帰的にDFSをするとよい。

文字列のまま処理

処理すべき順序を考えると、文字列のまま処理することもできる。

初期状態で黒く塗られているノードを、階層（部分木の高さ）ごとに分類する

        ○[1]
      ／  ＼
    ０[2]   １[3]  00 と 101 と 11 が初期状態の場合
   ／＼    ／＼    {1: ['101'], 2: ['01', '11']}
  ●  １  ０  ●
  /\  /\  /\  /\
 ０１０１０●０１

この上で、最も深い階層から、上に波及するように処理をすればよい。

変数 xor = 0 を定義
最も深い階層 $d$ から、以下を処理する
- 階層 $d$ に含まれる各文字列 $s$ につき、
  - $s$ の兄弟 $t$ がその階層に含まれていなければ、xor ^= g(d)
  - $s$ の親（ $s$ の末尾文字を1文字削ったもの）を、階層 $d+1$ に登録
- 階層 $d$ のノード情報をメモリから削除
- $d \leftarrow d+1$ として、 $d=L$ まで繰り返す

各階層で記録されている文字列は、その階層で「黒く塗れない文字列」であることを示す。親も「塗れない文字列」になる。その中で兄弟が「塗れる文字列」なら、それは「兄弟を根とした部分木が、独立した『山』として存在する」ということになる。

最終的にxorが、初期状態を表す数となる。

        
          
          
              
              from collections import defaultdict
 
 
def solve(l, ss):
    xor = 0
    for d in range(min(ss), l + 1):
        sl = ss[d]
        sl.sort()
        while sl:
            s = sl.pop()
            ps = s[:-1]
            ss[d + 1].append(ps)
            if s[-1] == '1' and sl and sl[-1][:-1] == ps:
                sl.pop()
            else:
                xor ^= d & -d
        del ss[d]
    return xor
 
 
n, l = map(int, input().split())
ss = defaultdict(list)
for s in (input() for _ in range(n)):
    ss[l - len(s) + 1].append(s)
 
print('Alice' if solve(l, ss) else 'Bob')

            

        
      