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,\ldots,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,\ldots,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]+\ldots$
  • $T_g=D[g]+D[2g]+D[3g]+\ldots$

一見計算量は多そうに見えるが、$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')

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