AtCoder Grand Contest 043 A~D問題メモ

A - Range Flip Find Route

問題

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

解法

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

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

S□■■■□□■■□□G
    |------------|
          |--|

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},\ldots,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,\ldots,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個は「$\ldots, i, x$」となるが、$x$ に来る数は、$1~i-1$ のどれでもよい。

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

  • $1,2,3,\ldots,i-3,i-2$
  • $1,2,3,\ldots,i-3,i-1$
  • $1,3,4,\ldots,i-2,i-1$
  • $2,3,4,\ldots,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)

本WebサイトはcookieをPHPのセッション識別および左欄目次の開閉状況記憶のために使用しています。同意できる方のみご覧ください。More information about cookies
programming_algorithm/contest_history/atcoder/2020/0321_agc043.txt · 最終更新: 2020/05/16 by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0