目次
AtCoder Grand Contest 045 A,B,C,D,E問題メモ
Aはかろうじて解けたものの、ほぼ終了間際&WA多発。
順位的にはほぼ変わらなくても一応1完と0完パフォーマンスはちょっと差があったので、その辺は差別化されてるのかと思ったが、同率は平均順位を採るのね。なるほど。
A - Xor Battle
問題
- 人0と人1がゲームを行う
- 1ゲームは $N$ ラウンドからなる
- 各ラウンドの情報は整数列 $A_1,A_2,...,A_N$ と、'0'と'1'からなる文字列 $S$ で与えられる
- ルール
- はじめ、$x=0$ である
- $i$ ラウンド目では、人 $S_i$ が、$x$ を $x \oplus A_i$ で置き換えるか、何もしないかを選べる
- 最終的に $x=0$ にすることができれば人0の勝ち、それ以外なら人1の勝ち
- お互いに全ての情報が分かって最適に行動するとき、どちらが勝つか求めよ
- ゲームは $T$ 回行われるので、それぞれについて答えよ
- $1 \le T \le 100$
- $1 \le N \le 200$
- $1 \le A_i \le 10^{18}$
解法
操作を逆順に見る。
Round 1 2 3 4 5 6 7
Ai 7 4 7 3 5 5 6
010 100 100 011 101 101 110 (2進数)
S 1 0 1 1 0 0 0
最終7ラウンドの直前に、$x=0$ または $x=6$ にできるなら人0は勝てる。これを、$X=\{0,6\}$ と表すことにする。
そのためには、6ラウンド目の直前には $X=\{0,3,5,6\}$ ならよい。（$\{0,6\}$ に、それぞれ5をXORしたものを加えた集合）
そのためには、5ラウンド目の直前には $X=\{0,3,5,6\}$ ならよい。（それぞれ5をXORしたものを加えた集合だが、新しい要素は増えない）
言い換えると、$X$ の中にある数は、人1が選んできたとしても「打ち消せる」数となる。 一方、$X$ の中に無い数はそれ以降の人0の数字（この場合 $[5,5,6]$）をどう組み合わせても作れない。
ラウンド4は選択権が人1に移るが、$A_4=3$ が $X$ 内にあるので人1がそれを選んできても、人0は打ち消せる。
しかし、ラウンド3の $A_3=7$ は $X$ に無いため、7（の成分）を残すように人1が操作を選ぶと、人0は最終結果を $x=0$ にできなくなるので、この時点で不可能となる。
このケースは不可能と分かったが、説明のためにこのまま考察を続ける。
ラウンド2は人0が $A_2=4$ を選択できるため、$X=\{0,1,2,3,4,5,6,7\}$ となる。
ここで先ほどの敗因である7が含まれるようになるが、人1はラウンド3で選択「するかしないかを選べる」ので、 仮に人0が4を選択してきたら、人1は逆に7を選択しないことで $x=0$ を阻止できる。結果は変わらない。
一方、ラウンド1の7は、人1が選択した後で人0が選択できるので、打ち消すことが可能である。
あくまでその時点での $X$ に含まれるかどうかがポイントとなる。
高速化
さて、逆順に見て、$S_i=0$ なら $X$ を拡張し、$S_i=1$ ならその時点の $X$ の中に $A_i$ が存在しなければ人1の勝ち、最後まで無事なら人0の勝ち、とすることはわかった。
しかし、これを愚直にやると $X$ には $0～2^{60}$ のあらゆる数が入りうる。 $S_i=0$ の時に拡張するのに非現実的な時間がかかるし、何よりメモリが持たない。
ここで、$X$ をスリム化する方法が必要となる。スリム化した $X$ を $X'$ とする。
$X$ は、「それまでに出てきた $S_i=0$ の時の $A_i$ を組み合わせて作れる数」なので、 $A_i$ のまま持っておけば高々200個なのだが、そうすると今度は $S_i=1$ の時に $A_i$ が $X$ に含まれるかの判定時、 どれとどれを組み合わせれば作れるのかが難しい。
ここで、XOR問題での考え方の一つとして、 $\{A_1,A_2,A_3,...\}$ で作れる数の集合と $\{A_1 \oplus A_2, A_2,A_3,...\}$ で作れる数の集合は変わらないというのがある。
行列の掃き出し法と似た要領で、全ての情報を残しつつ「最上位bitが同じ数字は持たない」ようにする。 そうすれば、最大でも60要素しか管理しなくてよいし、上のbitから順に0にしていけば、次に適用すればよい要素が一意に特定できる。
Ai 31 11111 28 11100 7 111 5 101 3 11
これらの $A_i$ からいくつかを選んでXORで作れる要素は、本来 $X=\{0～7,24～31\}$ の16個となる。
最上位bitが最も大きい要素 $a$ を1つ選び、$X'$ に残すことを確定させる。最上位bitが同じ要素を、$a$ とのXORを取った数に置き換える。0になった要素は除外する。
X 確定 3 11 28 11100 * 7 111 5 101 3 11
X 確定 3 11 28 11100 * 2 10 5 101 * 3 11
X 確定 3 11 * 28 11100 * 1 1 5 101 * 0 0 →除外
X 確定 3 11 * 28 11100 * 1 1 * 5 101 *
$X'=\{28,5,3,1\}$ として持っておけば、この4要素から、本来16要素ある $X$ を復元できる。
たとえば $k=30 \equiv 11110_2$ が $X$ に含まれるか判定する。 $X'$ の大きい要素 $a$ から「$a$ の最上位が $k$ で立っていれば、$k←a \oplus k$ とする」ことを繰り返し、$k=0$ にできれば $X$ に含まれると言える。
k a
30 11110 ← 28 11100 最上位bitが立っている 11110 XOR 11100 = 10
2 10 ← 5 101 最上位bitは立っていない
2 10 ← 3 11 最上位bitが立っている 10 XOR 11 = 1
1 1 ← 1 1 最上位bitが立っている 1 XOR 1 = 0
0 0 最終的に k=0 にできた
→ 30はXに含まれる
※上の例では、方法の説明のため既に $A_i$ がいくつかある状態から $X'$ を構築したが、実際には $X'$ は空の状態から1つずつ登録する。
$S_i=0$ の場合、$A_i$ が既存の $X'$ で作れるかを $S_i=1$ の時の存在チェックと同様に判定する。 作れない場合（$k \neq 0$）は、残った $k$ が $X'$ に新しく登録すべき要素となるので、降順を保つように $X'$ に挿入する。
計算量
「$S_i=0$ の時に $A_i$ を $X'$ に登録するかしないか、する場合の値は何にすればよいか」「$S_i=1$ の時に $A_i$ が $X$ に含まれるか」それぞれでチェックが必要となる。これは1回につき $O(\log{A_{max}})$ かかる。
あと、$S_i=0$ の時に $X'$ に降順を保って挿入するのに最大 $O(\log{A_{max}})$ かかるが、この操作は多くとも $\log{A_{max}}$ 回でまた最初の方はあまりかからないため、まぁそんなに重くはないと考えられる。
これを $T$ 個のテストケースで $N$ 要素のそれぞれで処理すると $O(TN\log{A_{max}})$、制約の最大値を代入して約 $100 \times 200 \times 60 = 1.2 \times 10^6$ となり、十分間に合う範囲となる。
実際には様々なテストケースがあるだろうし、不可能な場合は途中で打ち切れるので、もう少し速く処理できる。
from bisect import insort
t = int(input())
buf = []
for _ in range(t):
n = int(input())
aaa = list(map(int, input().split()))
s = input()
is_ok = 0
can = []
for i in range(n - 1, -1, -1):
a = aaa[i]
# canの数字(c)を大きい順に見て、最上位bit(b)が a で立ってるなら a^c を繰り返す
# 最終的にa==0となるかで、can内の数字で a が作れるかどうかを判定できる
for (b, c) in can[::-1]:
if a & b:
a ^= c
# 操作するのがどちらにしろ、a がその後の'0'の操作で作れるなら、何もする必要なし
if a == 0:
continue
if s[i] == '0':
# 残った a を登録
b = 1 << (a.bit_length() - 1)
insort(can, (b, a))
else:
# 最終的なx=0を阻止できる
is_ok = 1
break
buf.append(is_ok)
print('\n'.join(map(str, buf)))
B - 01 Unbalanced
問題
- '0', '1', '?' からなる文字列 $S$ が与えられる
- '0'と'1'からなる文字列 $T$ の「アンバランス度」を、以下で定義する
- $T$ の全ての部分文字列について、「'0' と '1'の個数の差の絶対値」を計算し、その中の最大値
- $S$ の '?' をそれぞれ '0' または '1' に置きかえた時、$S$ のアンバランス度の最小値を求めよ
- $1 \le |S| \le 10^6$
解法
素朴な二分探索解（素朴とは）。解説pdfには、よりスマートな方法が紹介されている。
イメージ化すると、ある変数 $x$ を、'0'のとき+1、'1'のとき-1して推移グラフを描くと、最小値と最大値の差がアンバランス度となる。
00110110 2 x 1 x x x 0 x x x x -1 x
「最大値の最小値」みたいなのは、答えの二分探索が有効な解法となることがある。 ある値 $M$ で可能かの判定処理を $O(|S|)$ などでできれば、全体で $O(|S|\log{|S|})$ でできる。
判定処理は、（ワイルド文字はないが）以下の問題がちょっと似ている。
$x$ が取ることが可能な最大値と最小値を管理して、その間なら上手く調整すればどの値でも取れる、という時、 途中で「間」がなくなる、つまり最大値＜最小値になってしまえば、達成不可能というものである。
最大値は、初期値 $x=M$ とし、'?' を可能な限り '0' に置きかえる。 ただし $M$ を超えるようであればどれかを '1' にする。この場合、$x$ は2減る。 （遷移次第では '1' に置きかえられる '?' が残ってなくても初期値を下げることでも調整できるが、今回の手法上はあまりその2つを区別する必要は無い）
最小値は逆に、初期値 $x=0$ とし、'?' を可能な限り '1' に置きかえる。 0を下回るようであればどれかの '?' を '0' にする。$x$ は2増える。
こうすると、最大値と最小値の間を、'?' の置きかえを調整することで、1個飛ばしで取ることが可能となる。
この「ある時点で $x$ が取れる値は1個飛ばし」というのが厄介で、初期値が奇数か偶数かで、可能不可能が変わり得る。
M=3
????000 ????000
x💀 👼
3 x x 3 x x
2 x x 2 x x x
1 x x 1 x x
0 x 0 x
また、実際は可能なケースでも最小値＞最大値になってしまったりする。
ので、同列に考えられるようにするため、以下のようにする。
- 1回の試行の中では初期値が奇数・偶数を固定する
- 最大値・最小値の初期値の偶奇も合わせる（例えば $M$ が奇数なら、(最小値, 最大値)の初期値を $(0,M-1)$ と $(1,M)$ として行う）
- 初期値を調整するときも、2ずつ動かす
- その上で、両方の場合を試し、どちらかで成功したらOK
- 最大値のみ、$M$ を超えないように調整する
- 最小値のみ、0を下回らないように調整する
こうしておけば、最大値と最小値が一致した状態で範囲を超えたら破綻する。（一致してなければまだ調整に使える '?' が残っている）
例えば最大値・最小値がともに $M$ を超えたら、最大値は調整されるが最小値はされないため、最大値＜最小値 となり終了する。
AGCにありがちだけど、実装してみるとすげーシンプル。（これでいいという証明が難しい）
def check(s, m, parity):
lo = parity
hi = m - (m - parity) % 2
for c in s:
if c == '0':
lo += 1
hi += 1
elif c == '1':
lo -= 1
hi -= 1
else:
lo -= 1
hi += 1
if lo < 0:
lo += 2
if hi > m:
hi -= 2
if lo > hi:
return False
return True
s = input()
l, r = 0, len(s)
while l + 1 < r:
m = (l + r) // 2
if check(s, m, 0) or check(s, m, 1):
r = m
else:
l = m
print(r)
C - Range Set
問題
- 長さ $N$ の数列があり、はじめ、全て0
- 以下の操作を好きなだけ繰り返す
- 長さ $A$ の連続した要素を0に置換
- 長さ $B$ の連続した要素を1に置換
- 最終的な数列の並びとしてあり得るものの個数を、$\mod{10^9+7}$ で求めよ
- $1 \le A,B \le N \le 5000$
解法
とりあえず、$A \gt B$ の場合、はじめ全て'1'で塗りつぶして、0と1を逆転させて考えても答えは変わらないので、$A \le B$ を仮定してよい。
最後の操作を考えると、完成形に $A$ 個以上連続する0か $B$ 個以上連続する1は必須である。
そしてそれさえあれば、端から0,1をずらしつつ確定させていけば、可能なように（パッと見）思える。
A=3, B=6
11001010001110 ←これを作りたい場合
11111100000000 左から1,0,1,0の順に
~~~~~~
11000100000000
~~~
11001111110000
~~~~~~
11001000110000
~~~
11001011111100
~~~~~~
11001111111110 ここで右の分も調整して
~~~~~~
11001010001110 完成！
~~~
なので、「全体から、長さ $A$ 以上の0も、長さ $B$ 以上の1も含まない並びを除けばいいのでは？」と考えるが、実際はもう少し出来ないケースがある。
$A$ より $B$ の方が2以上大きい場合、こんなケースがある。 取っかかりとなる 3個連続した0こそあるものの、仮にそれを全て1に置きかえたとしても1の長さが足りず、「最後から2手目の操作」が行えなくなる。
A=3, B=6 0100010 ↓~~~ 0111110 手詰まり
ただし、この手詰まりとなった状況は、最初に思いついた「長さ $A$ 以上の0も、長さ $B$ 以上の1も含まない並び」となっている。
よって、「長さ $B$ 未満の'1'の中身を、好きなだけ長さ $A$ 以上の0で置きかえたもの」も、含んではいけない、と考える。
DPを2回行う。
- $DP1[i]$:
- 長さ $i$ で、右端が'1'で、はじめ'1'で塗りつぶされていたのを、長さ $A$ 以上の0で好きなだけ上書きすることで実現できる並びの個数
- $DP2[j][i]$:
- 長さ $i$ で、右端が $j=0/1$ で、長さ $A$ 以上の0も、長さ $B$ 以上の1も含まない並びの個数
- ただし、DP1のように、'1' の並びの中には長さ $A$ 以上の0があってもよい
DP1は、「末尾に1を追加する」か、「$A$ 個以上の0と1個の1（00…01）を追加する」かで遷移する。累積和を同時に計算しておけば、$O(N)$ で計算できる。
A=2
1 2 3 4 5
1 11 111 1111 11111
001 0011 00111
0001 00011
1001 10011
00001
10001
11001
これをDP2に用いるのだが、DP1で求めたのが「右端が'1'」だったのに対し、DP2で用いるのは「両端が'1'」である必要がある。
左端が0のも許してしまうと、左隣の'0'と合わさって範囲が延長してしまい、B以上となるかも知れない
...11 000 00011 00...
↓
...11 111 11111 00...
また、重複して数えられてしまう
...11 00 000011 00... 上のと並びは一緒
このような並びは、更に左の連続する1をくっつけたものを1つながりと数えることで、
可能なものは除外され、漏れやかぶり無く、きちんと数えられる
... 1100000011 00...
DP1で数え上げたものの性質上、その並びの左端に'1'を加えても条件は保たれたままなので、長さ $i$ の「両端が'1'」の並びの個数を求めたければ、$DP[i-1]$ を参照すればよい。
DP2[0] は、「DP2[1] の末尾に長さ $A$ 未満の'0'を追加する」ことで遷移する。
- $DP2[0][i] = DP2[1][i-1]+...+DP2[1][i-A+1]$
DP2[1] は、長さ $j$ の'1'を追加する際、そこに $DP1[j-1]$ をかけあわせて遷移する。
- $DP2[1][i] = (DP2[0][i-1] \times DP1[0]) + ... + (DP2[0][i-B+1] \times DP1[B-2])$
最終的に、$DP2[0][N]+DP2[1][N]$ が、不可能なパターン……ではない。
これでは抜け落ちているものがあって、DPで重複無く数え上げる目的で、'1'の連続箇所は両端が'1'であることを仮定していたが、最初と最後だけは、一方の端が'0'であっても重複しない。
A=3 B=6 00011011001 11001010000 ~~~~~ ~~~~~
一方の端が'1'で、もう一方が'0'の長さ $i$ の並びの個数は、$DP[i]-DP[i-1]$ で算出できるので、これを使って追加で数えればよい。
def solve(n, a, b):
MOD = 10 ** 9 + 7
if a > b:
a, b = b, a
if a == 1:
return pow(2, n, MOD)
# 長さ i の区間であり、右端が '1' であり、
# はじめ '1' で塗りつぶされていたのを、
# 長さ a 以上の '0' で0回以上上書きすることで実現できる並びの個数
dp1 = [0] * (b + 1)
dp1_acc = [0] * (b + 1)
dp1[0] = 1
dp1_acc[0] = 1
for i in range(1, b + 1):
tmp = dp1[i - 1] # 末尾に1を付ける
if i - a - 1 >= 0:
tmp = (tmp + dp1_acc[i - a - 1]) % MOD # 末尾に 00..01 を付ける
dp1[i] = tmp
dp1_acc[i] = (dp1_acc[i - 1] + tmp) % MOD
# 派生情報
# dp1[i-1]: 長さ i の区間であり、「両端」が'1'であるものの個数
# dp1[i] - dp1[i-1]: 長さ i の区間であり、左端が'0'、右端が'1'（またはその逆）のものの個数
# dp2x[i]
# 長さ i の区間であり、末尾が x であり、
# 長さa以上の'0'も、長さb以上の'1'も含まない01の並びの個数
# ただし'1'は、dp1で求めたように、その内部をa個以上の'0'で置きかえたものも含む
dp20 = [0] * (n + 1)
dp21 = [0] * (n + 1)
dp21_acc = [0] * (n + 1)
dp20[0] = dp21[0] = dp21_acc[0] = 1
for i in range(1, n + 1):
t0 = dp21_acc[i - 1]
if i >= a:
t0 -= dp21_acc[i - a]
dp20[i] = t0 % MOD
t1 = 0
for j in range(1, min(i + 1, b)):
t1 += dp20[i - j] * dp1[j - 1]
if i < b:
# 左端が長さb未満の '111...' で、さらに'0'で置きかえられた結果、最左端が'0'のもの
t1 += dp1[i] - dp1[i - 1]
t1 %= MOD
dp21[i] = t1
dp21_acc[i] = (dp21_acc[i - 1] + t1) % MOD
disable = dp20[n] + dp21[n]
# 右端が長さb未満の '111..' で、さらに'0'で置きかえられた結果、最右端が'0'のもの
for i in range(1, b):
disable += dp20[n - i] * (dp1[i] - dp1[i - 1])
return (pow(2, n, MOD) - disable) % MOD
n, a, b = map(int, input().split())
print(solve(n, a, b))
D - Lamps and Buttons
問題
- $N$ 個のランプとボタンがあり、最初、ランプ $1～A$ は点灯、他は消灯している
- 以下のルールでゲームをする
- 開始時、$1～N$ の順列 $\{p_1,p_2,...,p_N\}$ が一様ランダムで選ばれるが、プレイヤーには明かされない
- プレイヤーは、以下の操作を繰り返し行える
- 点灯しているランプの中から好きなランプ $i$ を選び、ボタン $i$ を押す
- ランプ $p_i$ の状態が反転する（付いていれば消え、消えていれば付く）
- 全てのランプが点灯している状態に出来れば勝ち
- 不可能とわかれば負け
- 勝率を $w$ とする。$w \times N!$ は整数になるので、これを $\mod 10^9+7$ で求めよ
- $2 \le N \le 10^7$
- $1 \le A \le \min(N-1,5000)$
解法
最適な操作方針自体は比較的すぐわかるが、その数え上げがなかなか難しい。（例によって、わかれば実装は難しくない）
順列を $i→p_i→p_{p_i}→p_{p_{p_i}}→...$ と追っていくと、いずれ $i$ に戻ってくる。この並びをサイクルと呼ぶことにする。
操作方針
サイクルが長さ2以上で、はじめから点灯しているものが1つあれば、連鎖的にサイクルに属する全てのランプは付けることができる。
$i$ が点灯していたら、$p_i$ を付けた状態にできる。もともと付いていて消えたら、もう一度操作すればよい。 さらに $p_i$ を操作することで、$p_{p_i}$ を付けた状態にでき、以降連鎖的に $i$ に戻るまで繰り返せる。
i 123456
p 265134
oooxxx o .. 点灯
| v x .. 消灯
oooxxo | .. そのボタンを操作
v | v .. そのランプが切替
ooooxo
v |
xoooxo
v |
ooooxo
|v
oxooxo
|v
ooooxo
2→6→4→1→2 のサイクルに含まれるランプは全て付けられた
付けられないのは以下の2パターン。
- サイクルの中に先頭の $A$ 個が1つも含まれないものは、起点が無いので付けられない
- $A$ 個の中に $i=p_i$ であるランプがあったら、操作した瞬間、自身が消えてしまう
- 再び操作することができなくなり、もう付けられない。お前のせいです。あ～あ
- ただし、それより前に全てのランプを付けることができればセーフ
つまり、渡された順列がまず不可能というパターンがあり、可能性があっても手順次第で不可能になってしまうパターンがある。
勝敗を順列に紐付ける
問題文でふと不思議に思う。 順列の決め方が $N!$ 通り。1つの順列を固定した時の勝敗はプレイヤーの操作次第で変わるので、勝率は小数となる。 仮に $\dfrac{p}{q}$ とした場合、全体の勝率への寄与は $\dfrac{p}{qN!}$ となるはず。
しかしこれを足し合わせた数は、$N!$ をかけたら必ず整数になるらしい。 実際は上手く打ち消し合うのだろうが、まるで、順列を固定した時点で必勝か必敗かが定まっていると仮定して計算できるかのようである。
これは、実はその通りで、勝率を求める上では「ランプは左から順に選択するとしてよい」。次のように考えられる。
- 順列とともに、最初の $A$ 個に付き、選択順も固定する
- 選択順も固定したら、勝敗は一意に決定する
- 勝てるなら、その（順列・選択順）の組は $\dfrac{1}{N!A!}$ だけ勝率に寄与する
- 順列の最初 $A$ 個を、選択順に従って左から並び替える（順列 $Q$ とする）
- 元の順列・選択順における勝敗は、$Q$ を左から選択した場合の勝敗と等しい
- 並べ替えると $Q$ になるような（順列・選択順）の組は、$Q$ を調べることでまとめて判定できる
- 選択順は $A!$ 通りあるので、勝てるなら $\dfrac{1}{N!}$ だけ勝率に寄与する
ただ、ちょっと不安な部分もあって、上記では最初に一括で選択順を固定したが、 実際のプレイをイメージすると、操作を進めて他と同じサイクルとわかったランプは、次の選択時に候補から除かれる。 この逐次的な部分をちゃんと考慮できているのか、という部分まで納得できる説明を思いつかなかった。
ともかく、これで「左から選択した結果、勝てるような順列は何通りありますか」という問題になった。
数え上げ
順列のサイクルにまつわる数え上げは、スターリング数が代表的であり、 $n$ 個の要素を $k$ 個のサイクルに分類する場合の数、という意味を持つ。 スターリング数の計算は動的計画法を用いて行え、 「$N-1$ 個の場合が計算済みで、新規の1個を、既存のサイクルに加えるのか、単独の新しいサイクルを作るのか」で $N$ 個の場合を求められる。 今回の場合、完全に同じではないが、第1種スターリング数の構成方法が参考となる。
先頭 $A$ 個の中に自己ループがある場合、それより左のボタンだけで全てが点灯できなければならない。
まず、先頭 $A$ 個の中に自己ループがあるのかどうかで場合分けをする。
無い場合
先頭 $A$ 個が自己ループを含まない場合、後ろの $N-A$ 個が全て、先頭 $A$ 個が作るサイクルのどれかに属すればよい。
$A$ 個の順列は $A!$ 通りある。この順列を、以下のようにサイクルを列挙することで表現する。
[順列]
A|
i 123456 789 ※ここでの p は最終的なものでなく、初期状態を表す
p 345412 （サイクルへの追加に伴い書き換えられていく）
[サイクル表現]
1→3→5→(1)
2→6→(2)
4→(4)
(1→3→5→)と(3→5→1→)のようにサイクル内でスライドさせたものは同一と見做すと、順列とサイクル表現は1対1対応する。
さて、はじめ消灯していた、$A+1$ 以降の数をサイクルに加えていく。 スターリング数の数え上げでは “新しい単独のサイクルを作る” という選択肢があったが、この場合は許されない。 図中の「→」の好きな箇所に挿入できる。 挿入した数からも「→」は生えるので挿入毎に1つずつ増えていき、1個目は $A$ 通り、2個目は $A+1$ 通り、…となる。
合わせて、$A! \times A(A+1) ... (N-1)=(N-1)! \times A$ 通りとなる。
しかし、上図で仮に「4」のサイクルに7～9のいずれも入らなかったら、4は自己ループとなり、「$A$ 個中に自己ループはない」という最初の前提と矛盾する。
このようなケースを除くため、ここで包除原理を用いる。
$S(l)=$ 自己ループを明示的に $l$ 個含む場合の数、として $S(0)-S(1)+S(2)-... S(A-1)$ が求める数となる。
$S(l)$ は、以下を掛け合わせた数となる。
- まずどの数が自己ループになるかで ${}_AC_l$ 通り
- その時の場合の数: 自己ループになった数ははじめから無かったと考えればよい。$(N-l-1)! \times (A-l)$
ある場合
左から最初の自己ループが $k+1$ 番目に出てくる、として $k$ を固定すると上手くダブりを回避できる。
- 位置による制約条件
- $1～k$: 自己ループがあってはいけない
- $k+1$: 自己ループ固定
- $k+2～A$: 特に制約は無い
- $A+1～N$: 先頭 $k$ 個のサイクル中にないといけない
ここでも、最初の $k$ 個中に自己ループがあってはいけないので後に包除原理を用いるが、まずは気にしないで進める。
先頭 $k$ 個の順列の決め方は $k!$ 通り。その後、先ほどと同様に、初期で消灯していた $A+1$ 個目以降を挿入していく。
k| A| i 1234 567 8910 p 3241 1→3→4→(1) 2→(2)
初期の消灯数を $B=N-A$ とすると、挿入の仕方は、$k(k+1)(k+2)...(k+B-1)$ 通りとなる。
挿入例 1→10→3→4→8→(1) 2→9→(2)
$k+1$ 個目は固定なので1通り。
最後に、$k+2$ 以上 $A$ 以下の数を挿入する。 この場合は、既存のサイクルへの追加に加え、新しいサイクルを作ってもよい。 上図の「→」の個数+1 の選択肢がある。
よって、1個目の挿入候補は $k+B+1$ 個あり、1ずつ増えていく。$(k+B+1)(k+B+2)...(N-1)$
以上を全て掛け合わせると、ほぼ $N!$ と似た式であり、一部のみ微妙に重複や抜けがあることがわかる。
$k! \times k(k+1)(k+2)...(k+B-1) \times (k+B+1)(k+B+2)...(N-1) = (N-1)! \dfrac{k}{k+B}$
これは、事前計算しておけばすぐに求められる。
後は、包除原理を適用して先頭 $k$ 個中の自己ループを除く。
- 明示的な自己ループ $l$ 個の選び方: ${}_kC_l$
- その時の場合の数: $(N-l-1)! \dfrac{k-l}{k-l+B}$
これで、計算に必要な情報が揃った。
計算量
$N!$ とその逆数などの事前計算が $O(N)$。
数え上げでは、$k$ を $1～A-1$ まで走査し、その中で $l$ を $0～k-1$ まで走査する。 1回の計算は単なる四則演算なので $O(1)$、計 $O(A^2)$ で求められる。
あわせて、$O(N+A^2)$ となる。
from numba import njit
import numpy as np
@njit('i8(i8, i8, i8)', cache=True)
def mod_pow(x, a, MOD):
# Numbaではmod付き累乗が使えなかった...
ret = 1
cur = x
while a:
if a & 1:
ret = ret * cur % MOD
cur = cur * cur % MOD
a >>= 1
return ret
@njit('UniTuple(i8[:], 2)(i8, i8)', cache=True)
def prepare(n, MOD):
factorials = np.ones(n + 1, dtype=np.int64)
for i in range(2, n + 1):
factorials[i] = factorials[i - 1] * i % MOD
finvs = np.ones(n + 1, dtype=np.int64)
finvs[n] = mod_pow(factorials[n], MOD - 2, MOD)
for i in range(n, 1, -1):
finvs[i - 1] = finvs[i] * i % MOD
return factorials, finvs
@njit('i8(i8, i8)', cache=True)
def solve(n, a):
MOD = 10 ** 9 + 7
facts, finvs = prepare(n, MOD)
invs = [facts[i - 1] * finvs[i] % MOD for i in range(n + 1)] # invs[0]: undefined
r = n - a
ans = 0
# a個がいずれも自己ループを持たないパターン
for l in range(a):
tmp1 = facts[a] * finvs[l] % MOD * finvs[a - l] % MOD
tmp2 = facts[n - l - 1] * (a - l) % MOD
ans = (ans + (-1) ** (l & 1) * tmp1 * tmp2) % MOD
# a個中k+1個目ではじめて自己ループを持つが、それまでのk個で全点灯できるパターン
for k in range(1, a):
for l in range(k):
tmp1 = facts[k] * finvs[l] % MOD * finvs[k - l] % MOD
tmp2 = facts[n - l - 1] * (k - l) % MOD * invs[r + k - l] % MOD
ans = (ans + (-1) ** (l & 1) * tmp1 * tmp2) % MOD
return ans
n, a = map(int, input().split())
print(solve(n, a))
E - Fragile Balls
問題
- $N$ 個の箱と $M$ 個のボール
- ボール $i$ ははじめ $A_i$ に入っていて、$B_i$ に移動させたい
- ボールの移動には以下の条件がある
- 1個のボールを箱から箱へ移す操作を1回とし、前の操作が完了してから次を行う
- ボールを取り出せる（移動元となる）のはボールが2個以上入った箱のみ
- ボール $i$ は $C_i$ 回をこえて移動させることはできない
- 全てのボールを希望通り移動させられるか判定し、可能なら最小の移動回数を求めよ
- $1 \le N,M \le 10^5$
- $1 \le C_i \le 10^5$
- 全ての箱が少なくとも1回は $B_i$ として指定されている
解法
何となくどう動かせばよいかは分かっても、詰めの段階で注意深い場合分けが必要。
いかにも意味ありげな最後の制約は、最初どう使うかわからないが、頭の片隅に置いておく。
グラフへの置き換え
箱を頂点として、箱 $a$ から $b$ に移動させたいボールに
対して $a→b$ に有向辺を張ったグラフを考えると、性質を考えやすい。
このグラフは自己ループ辺や多重辺があり得ることに注意する。
すると、問題の条件は以下のように言い換えられる。
- ボールが2個以上入ってないと移動できない
- →出次数が2以上の頂点しか起点にならない
- 全ての箱が $B_i$ として1度は指定されている
- →全ての頂点の入次数は1以上
また、この辺に従ってボールを移動させることは、ボールを希望の箱に1回で移動させることに相当する。
出次数2が必要なのはあくまで動かし始める起点であって、 そこからボールを移すと連鎖的に移動できるようになる。
○→○→○→○ ↓...
連結成分の分類
出次数が2以上の頂点が1個あれば、そこから繋がる連結成分内の箱のボールは、1回で希望の箱に持って行けそう。
ここで連結成分とは、辺の向きは関係なく、1つに繋がっている頂点群を指すとする。
ちゃんと証明するには、強連結成分分解する。（実装する必要は無い）
強連結成分とは、辺の向きを考慮して、その中ならどの頂点からどの頂点へも移動できるような頂点群を指す。
強連結 |-成分-| |--| |------| |--| |------| ○→○ → ○ → ○←○ ⊂○ ○→○ ↓↖↓ ↓↗ ↑ ↓ ○→○ ○ ○←○
まず、強連結成分内では、起点さえあれば全てのボールを希望の箱に1回で移せる。
起点からどれかのボール（$i$ とする）を希望の箱 $B_i$ に移すと、 それ以降 $B_i$ からは、他に未移動のボールがあっても $i$ が存在することで 箱に2個以上入っていることが保証されるので必ず移動させられる。
すると $B_i$ を移動元とするボール（$j$ とする）について $B_j$ でも同様のことが言え、 連鎖的に移動できるボールは増える。
よって、「起点から全ての頂点を訪れることができるか？」に帰着できる。 これは、強連結成分なので必ず達成できる。
唯一、起点にたとえばボールが2個しか無い場合などに 1個を動かし始めたら残る1個が一時的に動かせなくなるのが気になるが、 強連結成分なので必ず戻ってくるサイクルがあり、戻ってきたときに移せるようになる。
次に、連結成分全体に話を進める。
強連結成分で2個以上に分解できる連結成分は、トポロジカル順で最上位の成分に、必ず起点が存在する。
何故かというと、下位の成分に辺が伸びる頂点は、「連結成分内の1点」「下位の成分の1点」の2つに辺が伸びているはずである。
最上位が1点のみの場合もあるが、それも必ず入次数が1以上なので、「自己辺」と「下位成分への辺」があるはずである。
なのでまず最上位成分は全て1回で移動できる。
さらにそこから下位成分の1頂点にボールを移すと、今度はその頂点が起点として扱える。
これを繰り返すと、連結成分内の全ボールは1回で移動できることがわかる。
よって、「連結成分内に出次数2の頂点があるかどうか」が重要となる。
あれば、そのうち1つは必ず最上位に存在し、そこから全頂点を辿ることができる。 （＝全てのボールを1回で移動させられる）
なければ、その連結成分は強連結成分でも1つであるとともに、その中でボールを動かすには他のボールの助けが必要となる。
連結成分を以下に分類する。
- 出次数2の頂点が存在する（起点がある）
- 全て出次数1以下であり、1頂点のみからなる
- 全て出次数1以下であり、複数頂点からなる
①起点あり
$A_i$ の出現回数を数えておけば判別できる。
その中では全てのボールを1回で移動させることができる。
②起点無し、1頂点
起点は無いが、そもそも移動させる必要は無い。
③起点無し、複数頂点
こいつが、助けが必要。
出次数1以下、入次数1以上という制約を考えると、分岐のないサイクルになっているはずである。
どっかから耐久性 $C_i$ に余裕のあるボールをもってきてやると、
そこが起点となり、全体が流れるようになる。
その後、持ってきたボールは本来の狙いの場所に帰っていける。
↘↗ ○→○ ↑ ↓ ○←○
この時に持ってくるボールを「触媒」と呼ぶことにする。
触媒
基本的に触媒は $C_i \ge 2$ のボールであり、$C_i-1$ 個の③を救える。
触媒には3種類あって、それぞれで、それを触媒として使った際の移動回数の増分が異なる。
これら3つの触媒を、それぞれ触媒 $P,Q,R$ とする。
$P$: $A_i \neq B_i$
①に含まれる、もともと移動の必要のあるボール。また、他の触媒によって助けられた③に含まれるものもこれに該当する。
Ai→Bi を Ai→③→...→③→Bi に置き換える ※図中の③は、タイプ③の連結成分の任意の1頂点を表す
移動回数は、救う③の個数だけ増える
$Q$: $A_i = B_i$ で連結成分内に起点あり
①に含まれる自己辺。また、他の触媒によって助けられた③に含まれる自己辺もこれに該当する。
Ai を Ai→③→..→③ に置き換える
↑__________|
移動回数は、元々移動の必要の無いものを移動させるので、救う③の個数+1だけ増える。
$R$: $A_i = B_i$ で連結成分内に起点無し
②が該当する。こいつを触媒として使うこと自体に、触媒が必要となる。
●→● を ●→Ai→● に置き換える（●は他の触媒）
Ai ↙ ↖
③→..→③
移動回数は、救う③の個数+2だけ増え、 さらにこれを採用することで救える③の数も、他の触媒を1消費するので差し引き $C_i-2$ となる。
③を救え
まず、③が存在しないなら、全てを1回移動で実現できる。
$A_i \neq B_i$ であるボールの個数が答えである。（以下、この個数を $T$ とする）
存在する場合、①に触媒が1個は必要である。
無いと不可能となる。
①に触媒が1個でもあると、今度は③上にあるボールも触媒とできる。
触媒は、$P$ から使うのがよい。
どの触媒を使うにしろ③の個数分は必ず増えるが、
$P$ はそこからの追加無しで利用できるので、実質コスト0である。
$P$ の個数 ≧ ③の個数なら、答えは「$T$ + ③の個数」である。
足りないなら、不足分を $Q,R$ から補う。$Q,R$ を全て使っても足りなければ不可能。
$Q$ がコスト1、$R$ がコスト2だが、$C_i$ の大きい $R$ があるならそちらを使った方がいい。
いずれにしろ、コストが同じなら増やすことのできる触媒数が多い方から使うべきなので、 まず $Q,R$ それぞれで $C_i$ を基準にソートする。
$Q$ を何個使うかを決め打つと、残りを $R$ 何個使えばよいかは、累積和と二分探索で求められる。 $(Qの個数)+2(Rの個数)$ が移動回数の増分となるので、この最小値を探す。
$Q$ の個数は、通常は0個を含めてよいが、 唯一 $P$ が存在しない場合のみ、最初の起点として必ず使うので、1個からとなる点に注意。
感想
過去問として解いた時点ではテストケースが公開されていたので、 WAの原因を探りつつ見落としている条件を発見できたが、 この分類を、本番中にフィードバック無しでやるのはなかなかに厳しそう。
import sys
from bisect import bisect_left
from collections import defaultdict
from itertools import accumulate
class UnionFind:
def __init__(self, n):
self.table = [-1] * n
def _root(self, x):
stack = []
tbl = self.table
while tbl[x] >= 0:
stack.append(x)
x = tbl[x]
for y in stack:
tbl[y] = x
return x
def find(self, x, y):
return self._root(x) == self._root(y)
def unite(self, x, y):
r1 = self._root(x)
r2 = self._root(y)
if r1 == r2:
return
d1 = self.table[r1]
d2 = self.table[r2]
if d1 <= d2:
self.table[r2] = r1
self.table[r1] += d2
else:
self.table[r1] = r2
self.table[r2] += d1
def get_size(self, x):
return -self.table[self._root(x)]
def solve():
n, m = map(int, sys.stdin.buffer.readline().split())
extra_durabilities = [0] * n
self_loop_durabilities = [[] for _ in range(n)]
outdegrees = [0] * n
base_operation_count = 0
uft = UnionFind(n)
mp = map(int, sys.stdin.buffer.read().split())
for a, b, c in zip(mp, mp, mp):
a -= 1
b -= 1
outdegrees[a] += 1
if a == b:
if c >= 2:
self_loop_durabilities[a].append(c)
continue
uft.unite(a, b)
extra_durabilities[a] += c - 1
base_operation_count += 1
# components[root] = [size, max_outdegree, durability(non-self-loop), self-loop-durability]
components = defaultdict(lambda: [0, 0, 0, []])
for i in range(n):
r = uft._root(i)
item = components[r]
item[0] += 1
item[1] = max(item[1], outdegrees[i])
item[2] += extra_durabilities[i]
item[3].extend(self_loop_durabilities[i])
exists_initial_catalyst_on_moving_path = False
exists_initial_catalyst_at_self_loop = False
supplied_catalyst = 0
demanded_catalyst = 0
self_loop_catalysts_cost1 = []
self_loop_catalysts_cost2 = []
for i, (cnt, deg, dur, sel) in components.items():
if cnt == 1:
if deg == 1:
self_loop_catalysts_cost2.extend(c - 2 for c in sel)
else:
if len(sel) >= 1:
self_loop_catalysts_cost1.extend(c - 1 for c in sel)
exists_initial_catalyst_at_self_loop = True
continue
if deg == 1:
supplied_catalyst += dur
demanded_catalyst += 1
else:
supplied_catalyst += dur
if dur >= 1:
exists_initial_catalyst_on_moving_path = True
elif len(sel) >= 1:
exists_initial_catalyst_at_self_loop = True
self_loop_catalysts_cost1.extend(c - 1 for c in sel)
if demanded_catalyst == 0:
return base_operation_count
if not exists_initial_catalyst_on_moving_path and not exists_initial_catalyst_at_self_loop:
return -1
if supplied_catalyst >= demanded_catalyst:
if exists_initial_catalyst_on_moving_path:
return base_operation_count + demanded_catalyst
else:
return base_operation_count + demanded_catalyst + 1
self_loop_catalysts_cost1.sort(reverse=True)
self_loop_catalysts_cost2.sort(reverse=True)
acc1 = [0] + list(accumulate(self_loop_catalysts_cost1))
acc2 = [0] + list(accumulate(self_loop_catalysts_cost2))
shortage = demanded_catalyst - supplied_catalyst
if acc1[-1] + acc2[-1] < shortage:
return -1
cost = 10 ** 18
for use1 in range(0 if exists_initial_catalyst_on_moving_path else 1, len(acc1)):
cat = acc1[use1]
remaining = shortage - cat
if remaining <= 0:
cost = min(cost, use1)
break
if remaining > acc2[-1]:
continue
use2 = bisect_left(acc2, remaining)
cost = min(cost, use1 + 2 * use2)
return base_operation_count + demanded_catalyst + cost
print(solve())
