−目次

AtCoder Grand Contest 038 A～D問題メモ
- A - 01 Matrix
  - 問題
  - 解法
- B - Sorting a Segment
  - 問題
  - 解法
- C - LCMs
  - 問題
  - 解法
- D - Unique Path
  - 問題
  - 解法

AtCoder Grand Contest 038 A～D問題メモ

AtCoder Grand Contest 038

AtCoder Grand Contest 038 - YouTube

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')

            

        
      