−目次

AtCoder Grand Contest 035 A～D問題メモ
- A - XOR Circle
  - 問題
  - 解法
- B - Even Degrees
  - 問題
  - 解法
- C - Skolem XOR Tree
  - 問題
  - 解法
- D - Add and Remove
  - 問題
  - 解法

AtCoder Grand Contest 035 A～D問題メモ

AtCoder Grand Contest 035

AtCoder Grand Contest 035 解説放送 - YouTube

A - XOR Circle

問題

$N$ 個の整数 $a_1,a_2,...,a_N$ を、好きな順に円環状に並べる
どの整数についても、「両隣の整数のXORが、自身と等しい」という条件を満たすように並べられるか判定せよ
$3 \le N \le 10^5$
$0 \le a_i \le 10^9$

解法

実験すれば容易に法則は見つかる。後は注意力勝負。例外的なケースをきちんと考慮できるか。

配置の自由度があまり無さそうなので、最初の2つを適当に決めて並べて置いてみる。（2進数表記）

001  101

すると、101を中心と考えると、001とのXORが101になる数字は100しかない。

001  101  100

さらに100を中心と考えると、、、と順に一意に決まっていき、3つの整数の繰り返しになることが分かる。

001  101  100  001  101  100  ...

出てくる整数の数を数えて、 $a \ XOR \ b = c$ となる3つの整数が、同じ数だけ出現していればよい。必然的に $N$ は3の倍数となる。

ただし、0を含む場合は、以下のケースも考えられる。

$a \ XOR \ a = 0$ なので、0以外の数 $a$ が、0の2倍存在してもよい
全てが0の場合、0 0 0 … は条件を満たす。この場合は $N$ が3の倍数で無くてもよい

        
              from collections import Counter
 
def solve(n, aaa):
    if all(a == 0 for a in aaa):
        return True
 
    if n % 3 != 0:
        return False
 
    cnt = Counter(aaa)
    if len(cnt) == 2:
        (a1, c1), (a2, c2) = cnt.most_common()
        if c1 != n * 2 // 3 or c2 != n // 3:
            return False
        return a2 == 0
 
    if len(cnt) == 3:
        if any(c != n // 3 for c in cnt.values()):
            return False
        a1, a2, a3 = cnt.keys()
        return a1 ^ a2 == a3
 
    return False
 
n = int(input())
aaa = list(map(int, input().split()))
print('Yes' if solve(n, aaa) else 'No')

B - Even Degrees

問題

$N$ 頂点 $M$ 辺の単純連結無向グラフが与えられる
$i$ 番目の辺は頂点 $A_i$ と頂点 $B_i$ を結ぶ
この無向辺のそれぞれに、どちらかの向きを与えて有向グラフを作る
「どの頂点から出る辺の本数も偶数になる」ような有向グラフを作ることが可能かどうか判定し、可能なら例をひとつ構成せよ
$2 \le N \le 10^5$
$N−1 \le M \le 10^5$

解法

辺の数が奇数なら無理。以下偶数の場合を考える。

全辺の向きを適当に決めれば、「頂点から出る辺の本数が奇数」である頂点が偶数個できる。

●→○→●      ○: 偶数
↑  ↓  ↓      ●: 奇数
○→●→○←●

奇数の頂点を適当に2つずつのペアにし、（無向グラフでの）経路を1つ見つける。

●➡○➡●      ◎: 奇数頂点のペア
⬆  ↓  ⬇      太矢印: ◎を結ぶ経路の1つ
○➡◎→○⬅◎

その経路上の辺の向きを全て逆転させると、通過する頂点の偶奇は変わらず、両端の頂点の偶奇のみが反転する。

●←○←●      ◎は偶数頂点に変化
↓  ↓  ↑
○←◎→○→◎

これは、最初の辺の向きをどう決めようが、奇数頂点のペアをどう作ろうが、経路をどう取ろうが、必ず成立する。

◎→○→◎      完成！
↓  ↓  ↑
○←○→○→○

後はこれをどう実装するか。頂点ペアを適当に決めていいとは言っても、以下のようなペアを拾ってしまうと、パスの探索にも時間がかかるし何度も同じ辺を反転させてしまう。

※同じ数字 = 同じペア
❶─❷─❸─ ... (たくさんの頂点) ... ─❸─❷─❶

ここでは、グラフから適当な辺を削ぎ落として、全域木を1つ作ってしまえばよい。

●→○→●
↑  ↓  ↓
○→●→○←●

↓

根→○→●
↑  ↓
○  ●→○←●

ペア同士を結ぶ経路はどれを使ってもよいので、全域木上の辺だけを使うと決め打って問題ない。

深さ優先探索で葉から探索するなどして、「自分と自分以下の頂点で、奇数頂点が奇数個なら、親へ繋がる辺を反転させる」。

根→○→●      ❶以下の頂点（❶のみ）で、
↑  ↓          奇数頂点は1個なので、反転
○  ●→○⬅❶

根→○→●      ②以下の頂点で、
↑  ↓          奇数頂点は1個なので、反転
○  ●➡②→❶

根→○→●      ❸以下の頂点で、
↑  ↓          奇数頂点は2個なので、反転しない
○  ❸←②→❶  （❶と❸がペアになり、その間の経路が反転されている）

一番近い親とペアになるため、各辺についてたかだか1回のみの反転で済む。

「最初に頂点の偶奇を決めるため、適当に辺の向きを決めた有向グラフを作る」と同時に「経路探索用に辺を限定した全域木を作る」という、2つのグラフを同時に構築しなければいけない点に気付くのに、時間がかかった。

        
          
          
              
              import sys
from collections import deque
 
sys.setrecursionlimit(10 ** 5)
 
 
def solve(n, m, links):
    if m % 2 == 1:
        print(-1)
        return
 
    tree = [set() for _ in range(n)]
    parents = [-1] * n
    q = deque([0])
    while q:
        v = q.popleft()
        for u in links[v]:
            if parents[u] == -1:
                tree[v].add(u)
                parents[u] = v
                q.append(u)
            links[u].remove(v)
 
    parities = [len(l) % 2 for l in links]
 
    def dfs(v):
        b = parities[v]
        for u in tree[v]:
            c = dfs(u)
            b ^= c
        if b:
            p = parents[v]
            links[p].remove(v)
            links[v].add(p)
        return b
 
    dfs(0)
 
    ans = ['{} {}'.format(v + 1, u + 1) for v in range(n) for u in links[v]]
    print('\n'.join(ans))
 
 
n, m = list(map(int, input().split()))
 
links = [set() for _ in range(n)]
for line in sys.stdin:
    a, b = map(int, line.split())
    a -= 1
    b -= 1
    links[a].add(b)
    links[b].add(a)
 
solve(n, m, links)

            

        
      

C - Skolem XOR Tree

問題

整数 $N$ が与えられる
$1～2N$ までの番号がついた $2N$ 個の頂点を持つ木のうち、次の条件を満たすものが存在するか判定し、存在するならその一例を示せ
条件
- 各頂点には、頂点1から順番に整数 $1,2,3,...,N,1,2,3,...,N$ が書かれている
- $1～N$ の全ての整数について、同じ整数が書かれた頂点同士のパス上にある頂点（両端含む）の整数のXORを取ると、その整数と等しくなる
$1 \le N \le 10^5$

解法

解説PDFの方は2頂点毎のグループを作っていて、シンプルだし実装も楽なので、普通にそちらの方がよい。自分の取った方法をメモ。

サンプルを見ると、 $N=3$ のとき、以下のようにすればよいらしい。

1 - 2 - 3 - 1 - 2 - 3

XORの性質として、(0,1,2,3),(4,5,6,7),… と4で割った商が同じグループでXORをとると0になる、というのがあり、今回も4つのグループ単位で考えてみる。

頂点0が無いので (1,2,3) だけ例外的だが、これはサンプルのまま使う。

他は4つの数を繰り返してそのまま並べれば、条件を満たしている。最終的に各グループのどれかの頂点を他の木のどこでもよいのでくっつけて全体を連結にすればよい。

100 - 101 - 110 - 111 - 100 - 101 - 110 - 111

これで、4で割った余りが3となる $N$ については作れた。

後は、それ以外で端数が出る場合の $N$ を考える。

2のべき乗のパターン

$N=4$ の時、2進数では 100 だが、他の数で3桁目が立っているものは存在しない。よって3桁目を立たせる手段が無いため、不可能である。

100の間の頂点をどう組み合わせても、3桁目は1にできない
100  001 ?  100
     010 ?
     011 ?

このような $N$ というのは、2進数で桁が上がった直後の数、つまり 4, 8, 16, 32, … という2のべき乗数である。

では、 $N=5,6$ など、4で割った余りが1,2である $N$ についてはどうか。

これは、解説PDFなどのように、頂点1と2を使って配置することで可能となる。

101 -- 100 -- 001 -- 101 -- 100
               |      |
       110 -- 010    110

（本当は同様にすれば任意の隣り合う2整数でこの方法が採れて、4つずつのグループとか必要なかったが、やっているときは気付かないものである）

それ以外のパターン

2の冪乗（またはその+1,+2）以外は、余っている頂点番号の2進数での3桁目より上に'1'が2つ以上存在する。

たとえば2進数で 110010110 とかを考える。110010011 までは4つずつのグループが作れていて、110010100, 110010101, 110010110 の3つが余っている状態となる。（以下、L,L+1,L+2 とする）

ここで、各グループは、連結させるために他の頂点に繋ぐとき、好きな頂点に繋いでよいことを利用する。

Lの最下位ビットとそれ以外とを分けると、110010000, 000000100 になる。この2つは、 $N$ 以下なのでグループの一員として存在する。

よってこの2頂点を繋ぎ、それをかぶせるように結んだら、パス上のXORはLになる。

L - 110010000 - 000000100 - L
        |           |
     (group)     (group)

さらに (1,2,3) グループと結ぶことで L+1 も作れる。また、L+2も、最下位ビット（ここでは100）グループ中にある3番目の要素（110）と結ぶと実現できる。

                       L
                       |
L+1 -- 000000001 - 110010000 - 000000100 -- L
L+2 -'     |           |           |     `- L+1
        (group)     (group)    000000101
                                   |
                               000000110 -- L+2
                                   |...

他のグループは、適当に1にでも繋ぐとよい。

        
          
          
              
              # 以下の実装は、最下位ビットとそれ以外という2分割では無く、Lで立っているビットごとに頂点を対応させて分割している
 
def solve(n):
    if n < 3:
        print('No')
        return
    d, m = divmod(n, 4)
    l = d * 4
    if m == 3:
        d += 1
        l += 4
    ans = ['{} {}'.format(x, y) for x, y in ((1, 2), (2, 3), (3, 1 + n), (1 + n, 2 + n), (2 + n, 3 + n))]
 
    if bin(l).count('1') == 1:
        if m == 0:
            print('No')
            return
        if m < 3:
            ans.extend('{} {}'.format(x, y) for x, y in ((1, l), (l, l + 1), (1, l + n + 1), (l + n + 1, l + n)))
            if m == 2:
                ans.extend('{} {}'.format(x, y) for x, y in ((2, l + 2), (l + n + 1, l + n + 2)))
            m = 3
 
    for i in range(4, l, 4):
        ans.extend('{} {}'.format(x, y) for x, y in (
            (i, i + 1), (i + 1, i + 2), (i + 2, i + 3), (i + 3, i + n),
            (i + n, i + n + 1), (i + n + 1, i + n + 2), (i + n + 2, i + n + 3)))
 
    if m == 3:
        for i in range(4, l, 4):
            ans.append('{} {}'.format(1, i))
        print('Yes')
        print('\n'.join(ans))
        return
 
    min_k = k = l & -l
    prev = 1
    connected = set()
    while k < l:
        if k & l:
            ans.append('{} {}'.format(prev, k))
            connected.add(k)
            prev = k
        k <<= 1
 
    for i in range(4, l, 4):
        if i in connected:
            continue
        ans.append('{} {}'.format(1, i))
 
    # print(*ans, sep='\n')
    # print('--')
 
    ans.append('{} {}'.format(l, min_k))
    ans.append('{} {}'.format(l + n, prev))
 
    if m >= 1:
        ans.append('{} {}'.format(l + 1, 1))
        ans.append('{} {}'.format(l + 1 + n, prev))
    if m >= 2:
        ans.append('{} {}'.format(l + 2, 1))
        ans.append('{} {}'.format(l + 2 + n, prev + 2))
 
    assert len(ans) == 2 * n - 1
 
    print('Yes')
    print('\n'.join(ans))
 
 
n = int(input())
solve(n)

            

        
      

D - Add and Remove

問題

$N$ 要素の非負整数列 $A_1,A_2,...,A_N$
以下の操作を、数列の要素が2個になるまで繰り返す
- 連続する3要素 $A_{i-1},A_i,A_{i+1}$ を選ぶ
- 真ん中の要素を数列から取り除き、両隣 $A_{i-1},A_{i+1}$ の要素は、 $A_i$ を加算した値に置き換える
最終的に残った数の和の最小値を求めよ
$2 \le N \le 18$
$0 \le A_i \le 10^9$

解法

メモ化再帰。

$N$ の制約が小さいので全探索っぽいことをするのだろうとは思うが、本当に愚直な全探索は $N=18$ の時、最初の選び方が16通り、以下階乗となり、 $16! = 2 \times 10^{13}$ くらいになるので無理。

ただ、離れた2箇所などはどちらを先にやっても変わらないので、メモ化である程度は減らせる。とはいえ、配列を切ったり貼ったりをそのまま実装するのはコストも重く、メモ化の際の状態も表現しにくく、通らない。

機械的に計算しやすい・メモ化しやすい計算方法を見つけてやる。

足される回数

各局面での数を分解すると、もともとの数列にあった数が何回か足された数となっている。

5   2   4   1   6   9
    ~
  7   6   1   6   9  ←ここの左の6は、元を辿ると 2+4
          ~
    7   7   7   9
        ~
     14  14   9      ←ここの中央の14は、元は 2+4+1+1+6
         ~~
       28  23

数を選んで両隣に足すと、その数が総計において2倍に増える。

以下のように辺を引いて、選ばれた数は二股に分かれることで表現すると、その数が最終的に何回足されるかは、上から辺を辿って最下段まで行く時の経路数となる。

5   2   4   1   6   9
 \ / \ /   /   /   /
  7   6   1   6   9
   \   \ / \ /   /
    7   7   7   9
     \ / \ /   /
     14  14   9
       \ / \ /
       28  23 → 51

足される回数（経路数）
5   2   4   1   6   9
1   4   3   5   2   1  →  5*1 + 2*4 + 4*3 + 1*5 + 6*2 + 9*1 = 51

選ばれた数が2倍になるならなるべく小さい数字を選ぶのが良さそうだが、真ん中あたりの数を先に選ぶと何回も分裂して足されてしまう。

1  10   9  10   1    1  10   9  10   1
 \   \ / \ /   /      \ / \ /   /   /
  1  19  19   1       11  19  10   1
   \ / \ /   /          \   \ / \ /
   20  38   1           11  29  11
     \ / \ /              \ / \ /
     58  39 → 97         40  40 → 80

最初に最小の9を選ぶより、10を選んだ方が小さくなる
最終的に足された回数を数えると、最初に9を選んだ方は9が足される回数が多くなっている

1  10   9  10   1     1  10   9  10   1
1   3   5   2   1     1   3   2   3   1

逆方向に見る

各数が足される回数がわかれば、後は $A_1,A_2,...$ のそれぞれに乗じて足し合わせれば、答えが求まる。

しかし、これを直接求めるのはなかなか難しい。その数を選んだ後、隣接する要素をいつ選ぶかなどでも変わってくる。

ところが、操作を逆順に見ると、「現時点で最後に選んだ数が何回足されるか」は即座に確定できる。

これは、「上から辺を辿るとき、最初に選ばれるまでは経路数が1」であることから言える。逆順に見たときは、選ばれた地点より上ではもう経路数は変化しない。

⑥の経路数は、⑥をベースとした要素である⑭が選ばれるまでは、1通り
→逆順に見たとき、⑭より上では経路数はもう変化しない

5   2   4   1  ⑥   9
 \ / \ /   /   /   /
  7   6   1   6   9
   \   \ / \ /   /
    7   7   7   9
     \ / \ /   /
     14  ⑭   9
       \ / \ /
       28  23

具体的な経路数はどう計算するかというと、左右に分割する時の「左の経路数」＋「右の経路数」で求められる。

Ai    ... 5  2  4  1  6  9 ...
係数      7              3

5と9がこれより後で選ばれることが確定していて、その経路数がそれぞれ7回、3回であることが分かっているとする。

その間の数の中で、次に（本来の順では最も後に）選ばれる要素を仮に4とする。

その場合、他の2,1,6などは、4が選ばれる時点では既に5,4,9などに吸収されているため存在していない。 4の両隣は5と9（をベースとした要素）であるという状況だったことになる。

4は選ばれることで5,9に吸収されるが、その後の経路数は、それぞれ5,9が辿る経路数と同一となる。

よって、4の経路数は、5の経路数+9の経路数=7+3=10と確定する。

Ai    ... 5  2  4  1  6  9 ...
係数      7    10        3

このようにすると、今度は左右端が「5と4」である問題と「4と9」である問題に分割できる。

今回は4で分割したが、これを他の2,1,6でも試し、最小となる分割位置を再帰的に求める。

必要な情報は、「左端のindex」「右端のindex」「左端の係数」「右端の係数」であり、これらが同じであるケースは、この間の数の最適な係数の振り方は一意に求まる。

よってこれら4数をキーにメモ化すると、探索が間に合うようになる。

Pythonでは、関数のメモ化は自力実装せずとも lru_cache デコレータで実現できる。lru_cacheをかぶせる関数は、引数がdictで管理されるので、Hashableな値で無くてはならない。要はListなどを引数には出来ない点に注意。

また、ちょっと実行時間的に厳しい場合は、左右端の間隔が2とか3とか小さいときは採れる選択肢が限定されるので、再帰を呼び出すのでは無くその場で計算してやると、少し高速になる。

        
              from functools import lru_cache
 
def solve(n, aaa):
    @lru_cache(maxsize=None)
    def search_min(li, ri, lc, rc):
        w = ri - li
        if w == 1:
            return 0
        lrc = lc + rc
        if w == 2:
            return aaa[li + 1] * lrc
        if w == 3:
            a1, a2 = aaa[li + 1], aaa[li + 2]
            return (a1 + a2) * lrc + min(a1 * lc, a2 * rc)
        ret = min(aaa[i] * lrc + search_min(li, i, lc, lrc) + search_min(i, ri, lrc, rc) for i in range(li + 1, ri))
        return ret
 
    return search_min(0, n - 1, 1, 1) + aaa[0] + aaa[-1]
 
n = int(input())
aaa = list(map(int, input().split()))
print(solve(n, aaa))