白黒の反転は、「境界を無くす」操作。
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))
何はともあれ実験が簡単にできるので、してみる。
まず、$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))
なんかスケールが大きすぎてわけわかんなくなる問題。
解法もわりと発想がぶっ飛んでて、どうやったら思いつくのか、次に類題が出ても再現できるか怪しい。
とりあえず、$W$ は、$X,Y,Z$ の頂点をそれぞれ $x,y,z$ 軸に1列に並べて、それを立方体状に複製したようなグラフとなる。
頂点の重みの決め方から、$x,y,z$ 軸にどれか1つ増えるたびに重みは $10^{18}$ 倍になる。
ある頂点を選択したことによって、それより小さな最大 $3(N-1)$ 頂点が選択できなくなったとしても、その1頂点の重みには届かない。 よって、$x+y+z$ の大きい方から貪欲に選んでいってよい。
つまり、番号の大きい頂点から貪欲に以下を繰り返せば、答えは出る。
しかし、これは $N^3$ 以上かかる。どうするか。
この貪欲な決め方は、ゲームの勝ち負けを問う問題と非常に似ている。
さらに今回は、グラフは3次元的だが、辺は $x,y,z$ 軸のいずれかと平行にしか引かれていない。 つまり、遷移先は $x,y,z$ 軸のうち、いずれか1つに平行な方向しかない。
このような場合、勝ち負け状態の判定に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)
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も含まない数列が空になるまでは選ばれることはない。
[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つである。
この条件を踏まえて、どう数え挙げるか。
少ない要素数から、DPを行うことで可能となる。
遷移は、ブロックの長さが3以下なので、末尾にそれぞれの長さのブロックを付与する場合を考える。
最後のブロックの先頭要素は必ず $i$ となる。
$DP[i-1]$ から遷移する。最後に $i$ の1個ブロックを加えるしかないので1通り。
$DP[i-2]$ から遷移する。$P$ の最後の2個は「$..., i, x$」となるが、$x$ に来る数は、$1~i-1$ のどれでもよい。
ここで $DP[i-2]$ は、定義通りだと「$1~i-2$ までの数を使ってできるパターン数」だが、実際は要素の大小関係にしか意味が無いので、
これらの $i-1$ 通りのセットを使ってできるパターン数は、どれも同じ答えとなる。よって、末尾に来る数を決めれば、残りの並べ方はそれぞれが $DP[i-2]$ 通りずつある。
2個の場合と同様、末尾に来る2つの数の組み合わせは $(i-1)(i-2)$ 通りあり、残りの並べ方は $DP[i-3]$ 通りずつある。
$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)