−目次

AtCoder Grand Contest 043 A～D問題メモ
- A - Range Flip Find Route
  - 問題
  - 解法
- B - 123 Triangle
  - 問題
  - 解法
- C - Giant Graph
  - 問題
  - 解法
- D - Merge Triplets
  - 問題
  - 例
  - 解法

AtCoder Grand Contest 043 A～D問題メモ

AtCoder Grand Contest 043

A - Range Flip Find Route

問題

$H \times W$ マスの盤面、各マスは白または黒（配置は与えられる）
以下の操作を何回か繰り返して、以下の条件を満たすようにする
【操作】
- 好きな位置・大きさの矩形範囲を選び、その中の全てのマスの白と黒を反転させる
【条件】
- 左上から右下まで、常に右か下に移動するとき、白マスだけを通ってたどり着ける
必要な操作の最小回数を求めよ

解法

白黒の反転は、「境界を無くす」操作。

1次元配列だったら、ＳからＧまで白黒の境界が4つあれば、そこを反転させる区間の端とすることで、両端で境界を2個ずつ無くせる。

Ｓ□■■■□□■■□□Ｇ
    |------------|
          |--|

2次元でも一緒で、右または下に進むときの白→黒、黒→白の境界を、1つの操作で最大2個、消滅させることができる。

矩形なので境界自体はもっと消滅させられるのだが、最終的なルートで通過しない境界をいじっても意味が無い。 →と↓にしか移動できないので、矩形範囲に入る・出るの2回のタイミングで通過する境界のみ効果がある。

よって、最短経路探索で、色の違うマスに移動するときコスト1、同じならコスト0としてSからGまでのコストを求め、それを2で割ればよい。（切り上げ）

S,Gが初期配置で黒の場合はそれぞれ+1する。

        
          
          
              
              from collections import deque
 
 
def solve(h, w, field):
    s = int(field[0][0] == '#')
    q = deque([(s, s, 0, 0)])
    visited = [[[False] * 2 for _ in range(w)] for _ in range(h)]
    while q:
        cost, state, i, j = q.popleft()
        if visited[i][j][state]:
            continue
        visited[i][j][state] = True
        if i == h - 1 and j == w - 1:
            return cost
 
        for ni, nj in [(i, j + 1), (i + 1, j)]:
            if ni == h or nj == w:
                continue
            nc = int(field[ni][nj] == '#')
            if state == 0 and nc == 1:
                q.append((cost + 1, nc, ni, nj))
            else:
                q.appendleft((cost, nc, ni, nj))
 
 
h, w = list(map(int, input().split()))
field = [input() for _ in range(h)]
print(solve(h, w, field))

            

        
      

B - 123 Triangle

問題

1,2,3のみからなる長さ $N$ の数列が与えられる
隣り合う要素の差の絶対値を取って、次の数列とする（長さは1短くなる）
- つまり、最初の数列を $X_1=\{x_{1,1},x_{1,2},...,x_{1,N}\}$ として、以下のようになる
  - $x_{2,1}=|x_{1,1} - x_{1,2}|$
  - $x_{2,2}=|x_{1,2} - x_{1,3}|$
  - …
$N-1$ 回繰り返し、長さが1になったとき、その値（ $x_{N,1}$ ）を求めよ
$2 \le N \le 10^6$

解法

何はともあれ実験が簡単にできるので、してみる。

まず、 $X_2$ 以降は全て0,1,2となる。この3数から作られる差は2が最大、0が最小であって、それ以上・以下になることはない。

$X_1$ も、1ずつ引いて0,1,2にしてしまっても問題ないのでそうする。

0 0 0 0 0 1 0 0 0 0 0 2 0 0 0 0 1 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0
 0 0 0 0 1 1 0 0 0 0 2 2 0 0 0 1 1 0 0 0 0 0 0 2 2 0 0 0 0 0 0 0 0 0
  0 0 0 1 0 1 0 0 0 2 0 2 0 0 1 0 1 0 0 0 0 0 2 0 2 0 0 0 0 0 0 0 0
   0 0 1 1 1 1 0 0 2 2 2 2 0 1 1 1 1 0 0 0 0 2 2 2 2 0 0 0 0 0 0 0
    0 1 0 0 0 1 0 2 0 0 0 2 1 0 0 0 1 0 0 0 2 0 0 0 2 0 0 0 0 0 0
     1 1 0 0 1 1 2 2 0 0 2 1 1 0 0 1 1 0 0 2 2 0 0 2 2 0 0 0 0 0
      0 1 0 1 0 1 0 2 0 2 1 0 1 0 1 0 1 0 2 0 2 0 2 0 2 0 0 0 0
       1 1 1 1 1 1 2 2 2 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 0 0 0
        0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 2 0 0
         0 0 0 0 1 1 0 1 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 2 2 0
          0 0 0 1 0 1 1 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 2 0 2
           0 0 1 1 1 0 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 2 2 2
            0 1 0 0 1 1 0 0 1 0 0 0 1 0 0 0 1 0 0 0 2 0 0
             1 1 0 1 0 1 0 1 1 0 0 1 1 0 0 1 1 0 0 2 2 0
              0 1 1 1 1 1 1 0 1 0 1 0 1 0 1 0 1 0 2 0 2
               1 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 2 2 2
                1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0
                 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 1 1 0
                  1 0 0 1 0 1 0 0 0 0 0 0 0 0 1 0 1
                   1 0 1 1 1 1 0 0 0 0 0 0 0 1 1 1
                    1 1 0 0 0 1 0 0 0 0 0 0 1 0 0
                     0 1 0 0 1 1 0 0 0 0 0 1 1 0
                      1 1 0 1 0 1 0 0 0 0 1 0 1
                       0 1 1 1 1 1 0 0 0 1 1 1
                        1 0 0 0 0 1 0 0 1 0 0
                         1 0 0 0 1 1 0 1 1 0
                          1 0 0 1 0 1 1 0 1
                           1 0 1 1 1 0 1 1
                            1 1 0 0 1 1 0
                             0 1 0 1 0 1
                              1 1 1 1 1
                               0 0 0 0
                                0 0 0
                                 0 0
                                  0

0多めで実験してみると、1は三角形状に波及していき、シェルピンスキーの三角形が相互に作用しているような形状となる。

2も、隣が0なら同様に波及していくが、1と衝突すると消滅してしまう。これは1から見たとき、0も2も、1との差分は同じ1であることから、1の方が優位性が高いことが分かる。

またよく見ると、1の三角形同士が干渉した後も、一方の三角形で広範囲に0が続く箇所は、もう一方の三角形がそのまま描画されている。

ここから、1同士が干渉する箇所は、XORで考えればよいかも、と思いつく。

2は、1が含まれていればどこかで1と衝突して0と同じように扱われ最終結果に影響しない。よって0で置き換えるとする。

0,1だけに絞って考えると、差の絶対値の計算は、XORと同じ結果となる。

XOR            |A-B|
B\A| 0   1     B\A| 0   1
---+-------    ---+-------
0  | 0   1     0  | 0   1
1  | 1   0     1  | 1   0

なので、 $X_i$ から $X_{i+1}$ を作成するのには差の絶対値の代わりにXORで考えてもよい、とわかる。

それならば、1つずつに分解して考えられる。

初期状態で1である要素が、その位置から波及していって最下段で0になるか1になるかは、段数と位置から $O(1)$ で計算できる。その結果のXORを取ればよい。

ただし、初期状態に1が含まれない場合、2がそのまま影響する。しかしこれは、波及する要素が2になっただけで、1と同じ理論が使える。

        
          
          
              
              def test(a):
    print(*a)
    for i in range(len(a) - 1):
        a = [abs(a1 - a0) for a0, a1 in zip(a, a[1:])]
        print(' ' * i, *a)
        # print(*a)
 
 
# test([2, 3, 1, 1, 3, 1, 2, 3, 1, 2])
# test([2, 3, 1, 1, 3, 2, 2, 3, 1, 2])
# test([2, 3, 1, 1, 3, 3, 2, 3, 1, 2])
# test([1, 2, 0, 1, 2, 2, 2, 0, 0, 2, 1])
# test([1, 0, 0, 1, 1, 1, 1, 0, 1, 1, 0, 0, 0])
# test([0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ])
# test([0] * 21 + [2] + [0] * 21)
# exit()
 
def solve(n, aaa):
    # シェルピンスキーの三角形
    if '2' not in aaa:
        factor = '3'
        effect = 2
    else:
        factor = '2'
        effect = 1
    # print(factor, effect)
 
    try_list = []
    m = n - 1
    while m:
        l = 1 << (m.bit_length() - 1)
        m ^= l
        try_list.append((l, m))
    # print(try_list)
 
    ans = 0
    for i, a in enumerate(aaa):
        if a == factor:
            for l, m in try_list:
                if i >= l:
                    i -= l
                if i == 0:
                    ans ^= effect
                    break
                elif i > m:
                    break
    return ans
 
 
n = int(input())
aaa = input()
print(solve(n, aaa))

            

        
      

C - Giant Graph

問題

$N$ 頂点の単純無向グラフが3つある。 $X,Y,Z$ とする。
いずれも各頂点に $1,2,...,N$ の番号が付いている
それぞれのグラフの形状（辺数 $M_1,M_2,M_3$ およびどの頂点とどの頂点が結ばれているか）は与えられる
ここから、 $N^3$ 頂点のグラフ $W$ を作る
- $W$ の1頂点は「 $X,Y,Z$ から1頂点ずつ選んだ状態」1つと対応する
- $(X_i,Y_j,Z_k)$ を選んだ状態を、 $W_{i,j,k}$ とする
- 頂点 $X_i,X_l$ 間に辺があるとき、全ての $j,k$ で $W_{i,j,k},W_{l,j,k}$ 間に辺がある
- 頂点 $Y_j,Y_l$ 間に辺があるとき、全ての $i,k$ で $W_{i,j,k},W_{i,l,k}$ 間に辺がある
- 頂点 $Z_k,Z_l$ 間に辺があるとき、全ての $i,j$ で $W_{i,j,k},W_{i,j,l}$ 間に辺がある
頂点 $W_{i,j,k}$ の重みを、 $10^{18(i+j+k)}$ とする
$W$ の独立集合、つまりどの2頂点も辺を共有していない頂点群を選ぶとき、重みの最大値を $\mod{998244353}$ で求めよ
$2 \le N \le 10^5$
$1 \le M_1,M_2,M_3 \le 10^5$

解法

なんかスケールが大きすぎてわけわかんなくなる問題。

解法もわりと発想がぶっ飛んでて、どうやったら思いつくのか、次に類題が出ても再現できるか怪しい。

とりあえず、 $W$ は、 $X,Y,Z$ の頂点をそれぞれ $x,y,z$ 軸に1列に並べて、それを立方体状に複製したようなグラフとなる。

頂点の重みの決め方から、 $x,y,z$ 軸にどれか1つ増えるたびに重みは $10^{18}$ 倍になる。

ある頂点を選択したことによって、それより小さな最大 $3(N-1)$ 頂点が選択できなくなったとしても、その1頂点の重みには届かない。よって、 $x+y+z$ の大きい方から貪欲に選んでいってよい。

つまり、番号の大きい頂点から貪欲に以下を繰り返せば、答えは出る。

辺で繋がった自分より番号の大きい頂点の内、採用したものが1つでもあれば、採用できない
採用したものが1つもなければ、採用する

しかし、これは $N^3$ 以上かかる。どうするか。

この貪欲な決め方は、ゲームの勝ち負けを問う問題と非常に似ている。

最終状態を「負け」とする
最終状態に近い方から貪欲に決めていく
ある状態から遷移できる状態の内、「負け」が1つでもあれば、その状態は「勝ち」
全て「勝ち」にしか遷移できないのであれば、「負け」

さらに今回は、グラフは3次元的だが、辺は $x,y,z$ 軸のいずれかと平行にしか引かれていない。つまり、遷移先は $x,y,z$ 軸のうち、いずれか1つに平行な方向しかない。

このような場合、勝ち負け状態の判定にGrundy数を使える。

最終状態のGrundy数を0とする
ある状態のGrundy数は、そこから遷移できる状態のGrundy数に含まれない、最も小さな非負整数とする

これを $X,Y,Z$ でそれぞれ単独に求めておけば、 $G_{Wijk}=G_{Xi} \ xor \ G_{Yj} \ xor \ G_{Zk}$ で求められる。

これが0ならば「負け」、つまり元の問題に立ち返ると「採用できる頂点」となる。

さて、では $G_{Wijk}$ が0になる個数と重みを求めたい。愚直にやればやはり $O(N^3)$ かかる。

次に着目すべきは、 $X,Y,Z$ それぞれの中で、Grundy数が同じものはまとめられないか、という点である。

ある頂点のGrundy数を $k$ にしようと思えば、当然、最低 $k$ 個の遷移先がなければいけないし、その中に $k-1$ が無くてはいけない。再帰的に考えると、合計、最低 $\dfrac{k(k+1)}{2}$ 本の辺が必要となる。つまり、Grundy数の最大値は約 $\sqrt{2M}$ 程度であることが分かる。

ならば、以下のようにまとめてしまえば、高速化できる。

たとえばグラフ $X$ でGrundy数が“1”となる頂点の番号が3,4,7ならば、 $GX[1]=F^3+F^4+F^7$ とする。ただし $F=10^{18}$ とする。

同様に $GY,GZ$ も作り、GX,GYについて二重イテレートする。

$X$ のGrundy数3(011)、 $Y$ のGrundy数5(101) ならば、 $Z$ に求められるGrundy数は6(110)である。

従って、 $GX[3] \times GY[5] \times GZ[6]$ を計算すれば、そのGrundy数の組み合わせによる答えへの寄与が求まる。

このようにして、Grundy数のxorが0となるような組を全て合計したものが答えとなる。

計算量は、最初にそれぞれでGrundy数を求めるのが $O(N+M)$ 、Grundy数ごとにまとめた結果を二重イテレートするのが $O(\sqrt{M}^2)=O(M)$ なので、十分高速である。

        
          
          
              
              import sys
from collections import defaultdict
 
n, *mabs = map(int, sys.stdin.buffer.read().split())
MOD = 998244353
base = 10 ** 18 % MOD
base_costs = [base]
for i in range(n - 1):
    base_costs.append(base_costs[-1] * base % MOD)
graphs = []
i = 0
for _ in range(3):
    m = mabs[i]
    i += 1
    j = i + 2 * m
    parents = [set() for _ in range(n)]
    for a, b in zip(mabs[i:j:2], mabs[i + 1:j:2]):
        a -= 1
        b -= 1
        if a > b:
            a, b = b, a
        parents[a].add(b)
    grundy = [0] * n
    weights = defaultdict(int)
    for v in range(n - 1, -1, -1):
        pgs = {grundy[p] for p in parents[v]}
        for g in range(m + 1):
            if g not in pgs:
                grundy[v] = g
                weights[g] += base_costs[v]
                break
 
    for g in weights:
        weights[g] %= MOD
 
    graphs.append(dict(weights))
    i = j
 
ans = 0
graph_x, graph_y, graph_z = graphs
for gx, cx in graph_x.items():
    for gy, cy in graph_y.items():
        gz = gx ^ gy
        if gz in graph_z:
            ans = (ans + cx * cy * graph_z[gz]) % MOD
print(ans)

            

        
      

D - Merge Triplets

問題

正整数 $N$ が与えられる
以下の操作によって生成される可能性のある数列 $P$ の個数を求めよ
- 空の数列 $P$ を用意する
- $1～3N$ の整数を、3つずつの $N$ 個の数列 $A_1～A_N$ に振り分ける
- 以下を $3N$ 回繰り返す
  - $A_1～A_N$ で空でないものの先頭の要素のうち、最小の要素を $x$ とする
  - $x$ を $A_i$ から削除し、 $P$ の最後尾に追加する
答えは、素数 $M$ で割った値で求めよ（答えが $M$ の倍数となることはない程度に大きい素数が与えられる）
$1 \le N \le 2000$

例

P            A
             [8 1 4]
[]           [2 9 5]  8,2,6のうち、2が最小
             [6 3 7]

             [8 1 4]
[2]          [9 5]    8,9,6のうち、6が最小
             [6 3 7]

             [8 1 4]
[2 6]        [9 5]    8,9,3のうち、3が最小
             [3 7]
...

[2 6 3 7 8 1 4 9 5]   この振り分け方では、←のような数列となった

解法

必要条件を丁寧に探していく。

「出来上がりの形としてあり得るものの個数」を問う問題は、「ある順列 $P$ があったとして、これを問題の条件で作ることは可能か？」という問題を解くのであって、「 $A_1～A_N$ を列挙して再現して数え挙げる」という方針は悪手であることが多い。

道半ばの考察

$N=3$ として、 $1～9$ を並べることを考える。長さ3の、3つの数列に振り分けることになる。

まず、置ける場所の制約がきつそうな、大きい数から考える。

最大の9は先頭付近に来られない。他の数列の先頭要素が何であろうと、9よりは小さいので、そちらが選ばれてしまう。結局、9が数列の先頭にいたとしても、それ以外の2つの数列が全て空になるまでは、選ばれない。つまり、末尾3つのどこかにしか来られない。

                 [9 ? ?]
[? ? ? ? ? ?]    []       自身以外の全てが空になって、初めて選べる
                 []       9が選ばれたら、残りは数列に残っている順番通りに取り出される

じゃあ、次に8。同様に、8も9も含まない数列が空になるまでは選ばれることはない。

9の後ろにあったら9が取り出され次第取り出される
それ以外は、9がせき止めてる要素の個数より、3つ前までにしか来られない

                 [8 ? ?]
[? ? ? ?]        [9 ?]    9が自身を含め2要素せき止めていたら、
                 []       8は末尾から5～3番目にしか来られない

せき止めている、とは、自身の後ろに連続する、自身より小さい数（ただし自身を含む）とする。せき止められている数は、先頭が取り出されると必ず続けて取り出される。上記は、「4つ以上をせき止めている要素があってはいけない」と言い換えられる。

そう考えると、大きい方から置ける場所を確定させていって、ある数 $k$ を置けるのは、 $k+1～3N$ の中で最も左に置いた位置より3つ左までのどこか、という方針で可能か？

正しい考察

上記は、一つ条件を見落としている。

せき止めている1つのまとまりを「ブロック」と呼ぶことにする。

「サイズ2個 or 3個のブロック」は、1つの配列に1つしか置けないので、 $N$ 個以上作れない。

つまり、以下のような順列は作れない。

[1 6 2 7 3 8 4 9 5]    サイズ2のブロックが4個 > N=3
   ~~~ ~~~ ~~~ ~~~
これを作るには、6が選ばれる直前に以下のような状態になってないといけないが、これはあり得ない
          [6 2]
[1]       [7 3]
          [8 4]
          [9 5]

サイズ3のブロックはどっちみち $N$ 個以上作れないが、2のブロックは $N$ より多く作れてしまうので、問題となる。

2個のブロックは1個のブロックと組み合わせないといけないので、1個のブロック数より多くなってはいけない。

よって、必要な条件は、以下の2つである。

ブロックの長さは3以下
2個のブロックの個数は、1個のブロックの個数以下

この条件を踏まえて、どう数え挙げるか。

少ない要素数から、DPを行うことで可能となる。

$DP[i][j]=1～i$ の要素を使って、(1個のブロック数 - 2個のブロック数)が $j$ の場合のパターン数

初期条件
- $DP[0][0]=1$
- $DP[1][1]=1$
- $DP[2][2]=1$
- $DP[2][-1]=1$
求める値
- $j \ge 0$ であるような $DP[N][j]$ の総和

遷移は、ブロックの長さが3以下なので、末尾にそれぞれの長さのブロックを付与する場合を考える。

最後のブロックの先頭要素は必ず $i$ となる。

1個

$DP[i-1]$ から遷移する。最後に $i$ の1個ブロックを加えるしかないので1通り。

$DP[i][j] += DP[i-1][j-1]$

2個

$DP[i-2]$ から遷移する。 $P$ の最後の2個は「 $..., i, x$ 」となるが、 $x$ に来る数は、 $1～i-1$ のどれでもよい。

ここで $DP[i-2]$ は、定義通りだと「 $1～i-2$ までの数を使ってできるパターン数」だが、実際は要素の大小関係にしか意味が無いので、

$1,2,3,...,i-3,i-2$
$1,2,3,...,i-3,i-1$
…
$1,3,4,...,i-2,i-1$
$2,3,4,...,i-2,i-1$

これらの $i-1$ 通りのセットを使ってできるパターン数は、どれも同じ答えとなる。よって、末尾に来る数を決めれば、残りの並べ方はそれぞれが $DP[i-2]$ 通りずつある。

$DP[i][j] += DP[i-2][j+1] \times (i-1)$

3個

2個の場合と同様、末尾に来る2つの数の組み合わせは $(i-1)(i-2)$ 通りあり、残りの並べ方は $DP[i-3]$ 通りずつある。

$DP[i][j] += DP[i-3][j] \times (i-1)(i-2)$

実装

$j$ が負となりうるため、言語によっては適切にオフセットを設定してやる必要がある。

Pythonなら負のindexは末尾からのアクセスとなるため、配列を十分な長さで作っておけば、気にせずそのまま扱える。

また、 $j$ を±1する遷移があるが、numpyを使えば np.roll() で（-1→0 や 0→-1も含めて）簡潔に1つずらした配列を得られる。

        
              import numpy as np
 
n, MOD = map(int, input().split())
n3 = n * 3
dp = np.zeros((n3 + 1, int(n * 4.5) + 1), np.int64)
dp[0][0] = dp[1][1] = dp[2][2] = dp[2][-1] = 1
 
for i in range(3, n3 + 1):
    dp[i] += dp[i - 3] * (i - 2) * (i - 1)
    dp[i] += np.roll(dp[i - 2], -1) * (i - 1)
    dp[i] += np.roll(dp[i - 1], 1)
    dp[i] %= MOD
 
print(dp[-1][:n3 + 1].sum() % MOD)