目次
AtCoder Grand Contest 038 A～D問題メモ
A - 01 Matrix
問題
- $H \times W$ のマスがある
- 各マスに'0'と'1'のいずれかを書き込む
- 以下の条件を満たすような書き込み方ができるか判定し、できる場合は例を1つ構築せよ
- 条件は2つの整数 $A,B$ によって与えられる
- 全ての行について、「0と1のうち、少ない方は $A$ 個」である
- 全ての列について、「0と1のうち、少ない方は $B$ 個」である
- $1 \le H,W \le 1000$
- $0 \le A \le W/2$
- $0 \le B \le H/2$
解法
問題読解力＆ひらめき勝負。
条件を満たす0,1の並びから、2つの行、または2つの列を入れ替えても、条件を満たしたままである。
0 0 1 0 0 1 0 1 0 → 1 0 0 ┐ 1 0 0 0 1 0 ┘
なので、0をなるべく左上に寄せることを考えれば、こんな感じで条件を満たすものを作れることを思いつく。
┌ A個 ┐┌ W-A個 ┐ 0 0 ... 0 1 1 ... 1 ┐ ... B個 0 0 ... 0 1 1 ... 1 ┘ 1 1 ... 1 0 0 ... 0 ┐ ... H-B個 1 1 ... 1 0 0 ... 0 ┘
H, W, A, B = list(map(int, input().split()))
for _ in range(B):
print('0' * A + '1' * (W - A))
for _ in range(H - B):
print('1' * A + '0' * (W - A))
B - Sorting a Segment
問題
- $0～N-1$ の順列 $P_0,P_1,...,P_{N-1}$ がある
- 連続する $K$ 個を選び昇順にソートする、という操作をちょうど1回行う
- 操作後の列の並びとしてあり得るものの個数を求めよ
- $2 \le N \le 2 \times 10^5$
- $2 \le K \le N$
解法
基本的に、連続する $K$ 個は $N-K+1$ 箇所でとれるので、これが最大値。ここからどれだけダブるかを調べる。
範囲がかぶる場合
N=7 K=4
1 0 2 4 3 5 6 → 1 0 2 3 4 5 6
~~~~~~~
~~~~~~~ 左記の3箇所の操作では全てこうなる
~~~~~~~
区間を1つずつずらしながら確認していく。
1つ右にずらした時、以下の2つを満たせば、直前の区間の操作後と変わらない。
- 左端で区間から除かれる数字は、区間内の数字のどれより小さい
- 右端で新たに区間に入った数字は、区間内の数字の最大値
heapqで区間内の最大値・最小値を管理しながら、結果が変わらない区間を列挙していく。
範囲がかぶらない場合
N=10 K=4 2 0 1 3 7 4 5 6 8 9 ~~~~~~~ ~~~~~~~
もともと昇順の箇所が2つ以上あると、かぶる。（サンプル3に感謝）
前の数字より大きければ'1', 小さければ'0'という配列に変換して、枠長 $K-1$ の尺取りで、枠内の合計値が $K-1$ なら元の配列で昇順に並んでいる。
2 0 1 3 7 4 5 6 8 9 0 1 1 1 0 1 1 1 1
昇順の箇所が1つのみの場合は、問題ないことに注意。
実装
上記だけでは互いの範囲が重複してないことを確認していない。
範囲が被る場合と被らない場合で独立に調べ、該当する区間にフラグを立て（末尾位置を代表として）、ORを取ればよい。
2 0 1 3 7 4 5 6 8 9 最初から昇順の区間 0 0 0 0 0 0 0 0 1 1 範囲が被る区間 0 0 0 0 0 0 0 0 0 1 OR 0 0 0 0 0 0 0 0 1 1
今回の場合、「4568」と「5689」の2箇所での操作が他と被ることになるので、$N-K+1$ から2を引いた 5が答えとなる。
from heapq import heapify, heappop, heappush
n, k = list(map(int, input().split()))
ppp = list(map(int, input().split()))
increases = [int(p1 < p2) for p1, p2 in zip(ppp, ppp[1:])]
h = k - 1
tmp = sum(increases[:h])
duplicated = [0] * n
first_ascending = True
for i, q in enumerate(increases[h:], start=h):
tmp += q - increases[i - h]
if tmp == h:
if first_ascending:
first_ascending = False
else:
duplicated[i + 1] = 1
state = [1] * k + [0] * (n - k)
ans = 1
minq = ppp[:k]
maxq = [-p for p in ppp[:k]]
heapify(minq)
heapify(maxq)
for i, p in enumerate(ppp[k:], start=k):
l = ppp[i - k]
if l == minq[0] and p > -maxq[0]:
pass
elif duplicated[i] == 1:
pass
else:
ans += 1
state[l] = 2
state[p] = 1
while state[minq[0]] == 2:
heappop(minq)
while state[-maxq[0]] == 2:
heappop(maxq)
heappush(minq, p)
heappush(maxq, -p)
print(ans)
C - LCMs
問題
- 長さ $N$ の整数列 $A_1,A_2,...,A_N$ が与えられる
- 次式の値を $\mod{998244353}$ で求めよ
- $\displaystyle \sum_{i=1}^{N-1}\sum_{j=i+1}^{N}LCM(A_i,A_j)$
- ただし、$LCM(x,y)$ は $x$ と $y$ の最小公倍数とする
- $2 \le N \le 2 \times 10^5$
- $1 \le A_i \le 10^6$
解法
あまり見たことない発想。ゼータ変換・メビウス変換とかその辺の発想なので行けなくもないか。。。
具体的な $i,j$ の組を試していたら日が暮れるので、「○○が答えに足される回数は××回」というのを○○毎に数える、という方針で行きたい。
今回の場合、○○に入るのは？
いつもなら数列の要素の制約は $A_i \le 10^9$ とかなのに、この問題では $10^6$ と、線形な操作が可能な程度というところが怪しい。
$LCM(x,y)=\dfrac{xy}{GCD(x,y)}$ なので、$GCD(x,y)$ が同じ組について $xy$ を合計してやれば、最後に $GCD(x,y)$ で割ることで答えへの寄与を求められる。 GCDの取り得る範囲は $1～10^6$ なので、各GCDについて調べられれば、計算量的には大丈夫。
しかし、まだこれも難しい。一方を $A_i=12$ とか固定したところで、相方によってGCDは1にも2にも3にも4にも6にも12にもなるので、 「12と組み合わせるとGCDが1になる $A_j$」「2になる $A_j$」…と考えると結局 $N^2$ の総当たりが必要なように見える。
ここで、GCDを“分解”すると、相方を気にせず個々の数字単独で寄与を求められるようになる。
どういうことかというと、以下のような数列を作る。
- $w_i=i$ の約数である全ての $d$ について $w_d$ を合計すると、$\dfrac{1}{i}$ になるような数
i w iの約数 wdの合計 -------------------------- 1 1 1 1 2 -1/2 1,2 1/2 3 -2/3 1,3 1/3 4 -1/4 1,2,4 1/4 5 -4/5 1,5 1/5 6 1/3 1,2,3,6 1/6 ...
こうすると、GCD（Greatest Common Divisor）ではなく CD（Common Divisor）で考えてよくなる。
- 元の方針
- $g$ を固定すると、$GCD(x,y)=g$ である $x,y$ について、$\dfrac{xyの総和}{g}$ が答えに寄与する
- $w$ を使った方針
- $g$ を固定すると、公約数に $g$ を持つ $x,y$ について、$w_g \times (xyの総和)$ が答えに寄与する
これだとまだ「$xy$ の総和」という点で $x,y$ ペアを考える必要があるが、ここで以下の値を求める。
- $S_g = g$ を約数に持つ全ての $A_i$ の総和
- $T_g = g$ を約数に持つ全ての $A_i$ について、$A_i^2$ の総和
求めたい「$xy$ の総和」は、この2つの値から求められる。
仮に $g$ を約数に持つ要素が $A_a,A_b,A_c$ とすると、
- 求めたい値 $=A_aA_b+A_aA_c+A_bA_c$
- $S_g^2 - T_g = (A_a+A_b+A_c)^2 - (A_a^2 + A_b^2 + A_c^2)$
- $=2(A_aA_b+A_aA_c+A_bA_c)$
これで、やっと要素を各 $A_i$ 独立で考えることができた。
ただ、$S_g,T_g$ の求め方にも工夫が必要で、各 $g=1～A_{max}$ につき $A_i$ の各要素を1つ1つ試し割っていては、$O(N \times A_{max})$ かかる。
ここは、長さ $A_{max}+1$ の配列 $C,D$ を用意して、各 $A_i$ について $C[A_i]$ に $A_i$ を、$D[A_i]$ に $A_i^2$ を加算すればよい。
ある $g$ についての $S_g,T_g$ を求めたければ、以下を計算すればいい。
- $S_g=C[g]+C[2g]+C[3g]+...$
- $T_g=D[g]+D[2g]+D[3g]+...$
一見計算量は多そうに見えるが、$g$ が大きくなるにつれ見るべき要素は少なくなる。調和級数の和となるので、 $g=1～A_{max}$ について均すと約 $O(\log{A_{max}})$ で計算が可能である。
まとめると、
- $w$ を作る（$O(A_{max} \log{A_{max}})$）
- $C,D$ を作る（$O(N)$）
- 各 $g$ につき $S_g,T_g$ を求め、そこから答えへの寄与を計算する（$O(A_{max} \log{A_{max}})$）
あわせて $O(N + A_{max}\log{A_{max}})$ でできる。
import sys
def prepare(n, MOD):
f = 1
factorials = [1]
for m in range(1, n + 1):
f *= m
f %= MOD
factorials.append(f)
inv = pow(f, MOD - 2, MOD)
invs = [1] * (n + 1)
invs[n] = inv
for m in range(n, 1, -1):
inv *= m
inv %= MOD
invs[m - 1] = inv
solo_invs = [0] + [f * i % MOD for f, i in zip(factorials, invs[1:])]
return factorials, invs, solo_invs
def decompose_inverses(solo_invs, MOD):
# 各整数 g に対して、g の約数である各 i について dcm[i] を全て足すと 1/g になるような数列を作成
n = len(solo_invs)
dcm = solo_invs[:]
for i in range(1, n):
d = dcm[i]
for j in range(2 * i, n, i):
dcm[j] -= d
for i in range(1, n):
dcm[i] %= MOD
return dcm
n, *aaa = map(int, sys.stdin.buffer.read().split())
MOD = 998244353
LIMIT = max(aaa)
count = [0] * (LIMIT + 1)
double = [0] * (LIMIT + 1)
for a in aaa:
count[a] += a
double[a] += a * a
_, _, solo_invs = prepare(LIMIT, MOD)
dcm = decompose_inverses(solo_invs, MOD)
ans = 0
inv2 = solo_invs[2]
for d in range(1, LIMIT + 1):
mulsum = sum(count[d::d]) ** 2 - sum(double[d::d]) % MOD
if mulsum:
ans = (ans + dcm[d] * mulsum * inv2) % MOD
print(ans)
D - Unique Path
問題
- 以下の $Q$ 個の条件を全て満たす $N$ 頂点 $M$ 辺の単純連結無向グラフが存在するか、判定せよ
- 条件:
- $i$ 番目の条件は、$A_i,B_i,C_i$ によって与えられる
- $C_i=0$ の時、頂点 $A_i$ と $B_i$ を結ぶ単純パスは1つしか存在しない
- $C_i=1$ の時、頂点 $A_i$ と $B_i$ を結ぶ単純パスは2つ以上存在する
- $2 \le N \le 10^5$
- $N−1 \le M \le N(N−1)/2$
- $1 \le Q \le 10^5$
解法
まず、$C_i=0$ である $A_i,B_i$ だけで連結成分を構築する。この部分は、木になってないといけない。
A B C 0 1 0 (一例) 0 2 0 → 0 -- 1 -- 2 -- 3 1 3 0
具体的な繋ぎ方は任意だが、どのように並べようと連結成分となっている以上は、 各辺について「辺の左側にある頂点から1点」「辺の右側にある頂点から1点」を選んで結ぶような条件が1つは存在する。
ここで、連結成分同士を結ぶ辺を1本以上含む閉路が存在すると、その辺の左右を結ぶ経路で単純パスが2つ以上できてしまい、矛盾する。
0 -- 1 --- 2 -- 3
` 4 '
もし同じ連結成分内の2頂点同士を結ぶ $C_i=1$ の条件があると、閉路を作らねばならず、矛盾するので構築不可能となる。
よって、まずは $C_i=0$ のみで連結成分を構築し、$C_i=1$ が矛盾していないか確認する。
次に、辺の数 $M$ が達成可能か調べる。
$C_i=0$ の連結成分同士を結ぶ辺は、$N-(連結成分の個数)$ とするとまとめて計算できる。
N=10 連結成分数=4 → 確定済みの辺=10-4=6 0 -- 1 -- 2 -- 3 4 -- 5 6 -- 7 -- 8 9
残りを $M'$ 本とする。
同じ連結成分内から2頂点以上を（間接的にでも）他の1つの連結成分に繋げてしまうと、閉路ができてしまう。同じのに繋げられるのは1頂点まで。
× 0 -- 1 -- 2 -- 3
| |
4 -- 5
この制約の元で辺数を最大化しようと思うと、1つの連結成分から1頂点選んで、完全グラフを作ってしまえばよい。
0 -- 1 -- 2 -- 3 -- 4 -- 5
| × |
6 -- 7 -- 8 -- 9
追加の辺数は、連結成分数を $S$ として、$S(S-1)/2$ となる。
逆に辺数の最小値は、$C_i=1$ の条件が1つでもあるかないかで異なる。
1つも無ければ、元のグラフは木でもよい。よって、追加分も含めた全ての辺数は $N-1$ が最小となる。（これは制約で保証されている）
1つ以上あればどこかで閉路を作らねばならず、$N$ が最小となる。これは、以下のように1つの連結成分から1頂点選んで、ループを作れば達成できる。
0 -- 1 -- 2 -- 3 -- 4 -- 5
| |
6 -- 7 -- 8 -- 9
import sys
class UnionFind:
def __init__(self, n):
self.table = [-1] * n
def _root(self, x):
if self.table[x] < 0:
return x
else:
self.table[x] = self._root(self.table[x])
return self.table[x]
def find(self, x, y):
return self._root(x) == self._root(y)
def union(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 connected_count(self):
return sum(x < 0 for x in self.table)
n, m, q = list(map(int, input().split()))
uft = UnionFind(n)
hyper_paths = set()
for line in sys.stdin:
a, b, c = list(map(int, line.split()))
if c == 1:
hyper_paths.add((a, b))
continue
uft.union(a, b)
for a, b in hyper_paths:
if uft.find(a, b):
print('No')
exit()
cc = uft.connected_count()
min_m = n if len(hyper_paths) > 0 else n - 1
max_m = n - cc + cc * (cc - 1) // 2
print('Yes' if min_m <= m <= max_m else 'No')
