Ｓｋｙ株式会社プログラミングコンテスト2025（AtCoder Beginner Contest 434）D,E,F問題メモ

Ｓｋｙ株式会社プログラミングコンテスト2025（AtCoder Beginner Contest 434）

D - Clouds

• 空は $2000 \times 2000$ のマス目で表されます。
• 空を見上げた時、上から $r$ 行目、左から $c$ 列目にあるマスを $(r,c)$ と呼びます。
• いま、この空には雲 $1,2,\dots,N$ が浮かんでいます。
  • 雲 $i$ は、$(U_i, L_i),(D_i, R_i)$ を左上と右下とする矩形範囲を覆っています。
• $k=1,2,\dots,N$ について、以下の問いに答えてください。
  • $N$ 個の雲のうち、雲 $k$ のみを取り除く。この時点で空には $N-1$ 個の雲が浮かんでいる。このとき、どの雲にも覆われていないマスがいくつあるか答えよ。

• $1 \le N \le 2 \times 10^5$
• $1 \le U_i \le D_i \le 2000$
• $1 \le L_i \le R_i \le 2000$
• 入力される値は全て整数

2次元累積和を2回やる。

$k$ を取り除いた時の答えは「①始めからどの雲にも覆われていないマス」+「②雲 $k$ のみによって覆われているマス」となる。

①はどの $k$ についても共通であり、2次元imos法によって各雲を矩形で足し込んでいき、

• $A_{i,j}:=$ マス $(i,j)$ を覆っている雲の個数

を求めた結果の $A_{i,j}=0$ である $(i,j)$ の個数である。

また、$A$ を使って2次元累積和で以下を求めておけば、

• $B_{i,j}:=$ マス $(1,1)$ から $(i,j)$ までの矩形に含まれる、$A_{p,q}=1$ である $(p,q)$ の個数

任意の矩形についての「$A_{p,q}=1$ である $(p,q)$ の個数」がわかる。

• 累積和を何も考えずに書けるようにする！ #AtCoder - Qiita

「雲 $k$ の矩形に含まれる $A_{p,q}=1$ である $(p,q)$」は、雲 $k$ でのみ覆われているに決まっているので、②もわかる。

Python3

def solve(n, clouds):
    sky = [[0] * 2002 for _ in range(2002)]
    for u, d, l, r in clouds:
        d += 1
        r += 1
        sky[u][l] += 1
        sky[u][r] -= 1
        sky[d][l] -= 1
        sky[d][r] += 1
    for i in range(2002):
        for j in range(2001):
            sky[i][j + 1] += sky[i][j]
    for j in range(2002):
        for i in range(2001):
            sky[i + 1][j] += sky[i][j]

    not_covered = 0
    for i in range(1, 2001):
        for j in range(1, 2001):
            if sky[i][j] == 0:
                not_covered += 1

    only1 = [[int(c == 1) for c in row] for row in sky]
    for i in range(2002):
        for j in range(2001):
            only1[i][j + 1] += only1[i][j]
    for j in range(2002):
        for i in range(2001):
            only1[i + 1][j] += only1[i][j]

    ans = []
    for u, d, l, r in clouds:
        u -= 1
        l -= 1
        tmp = only1[d][r] - only1[u][r] - only1[d][l] + only1[u][l]
        ans.append(not_covered + tmp)
    return ans


n = int(input())
clouds = [list(map(int, input().split())) for _ in range(n)]
ans = solve(n, clouds)
print('\n'.join(map(str, ans)))

E - Distribute Bunnies

• $1$ から $N$ の番号がついた $N$ 匹のウサギが数直線上にいます。
• ウサギ $i$ は座標 $X_i$ にいて、ジャンプ力は $R_i$ です。同じ座標に複数のウサギがいることもあります。
• これから全てのウサギがちょうど $1$ 回ずつジャンプします。座標 $x$ にいるジャンプ力 $r$ のウサギがジャンプすると座標 $x+r$ または座標 $x-r$ に移動します。
• それぞれのウサギがどちらの座標にジャンプするかを自由に選べる時、全てのウサギがジャンプした後にウサギがいる座標の種類数としてあり得る最大値を求めてください。

• $1 \leq N \leq 2 \times 10^5$
• $-10^9 \leq X_i \leq 10^9$
• $1 \leq R_i \leq 10^9$
• 入力される値は全て整数

ウサギと座標をそれぞれ頂点とした二部グラフの最大マッチングを求めたい。

ウサギ $i$ から2つの座標 $X_i-R_i,X_i+R_i$ へ辺を張ったグラフでの 最大流で解けそうと思ったが、計算量は $O(\sqrt{N}M)$ となり、若干、制約が大きいのでもう少し効率的な解法を考えたい。

• 最大流の計算量参考:Dinic 法とその時間計算量 - みさわめも

連結成分ごとに考える。この問題の場合、以下が成立する。

• その連結成分から取れる最大マッチング = $\min(ウサギ頂点数, 座標頂点数)$

略証

ウサギ  ❶❷
        /\/\
座標   ①②③  →  ①-②-③

連結成分毎にDFSやUnion-Findの改良などでこれを求め、合計すると答えとなる。

Python3

from collections import defaultdict


def solve(n, rabbits):
    coords = defaultdict(list)
    for i in range(n):
        x, r = rabbits[i]
        coords[x - r].append(i)
        coords[x + r].append(i)
    checked = [False] * n
    ans = 0
    for s in range(n):
        if checked[s]:
            continue
        checked[s] = True
        checked_coords = set()
        q = [(0, s)]
        rc = 1
        cc = 0
        while q:
            tp, i = q.pop()
            if tp == 0:
                x, r = rabbits[i]
                if x - r not in checked_coords:
                    q.append((1, x - r))
                    checked_coords.add(x - r)
                    cc += 1
                if x + r not in checked_coords:
                    q.append((1, x + r))
                    checked_coords.add(x + r)
                    cc += 1
            else:
                for j in coords[i]:
                    if not checked[j]:
                        q.append((0, j))
                        checked[j] = True
                        rc += 1
        ans += min(rc, cc)

    return ans


n = int(input())
rabbits = [list(map(int, input().split())) for _ in range(n)]
ans = solve(n, rabbits)
print(ans)

F - Concat (2nd)

• $N$ 個の英小文字からなる文字列 $S_1,S_2,\dots,S_N$ が与えられます。
• $(1,2,\dots,N)$ の順列 $P=(P_1,P_2,\dots,P_N)$ としてありえるもの全てについて、以下の通りに生成される文字列を書き並べます。
  • $S_{P_1},S_{P_2},\dots,S_{P_N}$ をこの順に連結する。

• 書き並べられた $N!$ 個の文字列を辞書順に並べた列を $A_1,A_2,\dots,A_{N!}$ とします。
• $A_2$ を出力してください。

• $T$ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

• $1 \le T \le 1.5 \times 10^5$
• $2 \le N \le 3 \times 10^5$
• $T,N$ は整数
• $S_i$ は英小文字からなる長さ $1$ 以上 $10^6-1$ 以下の文字列
• ひとつの入力について、 $N$ の総和は $3 \times 10^5$ を超えない
• ひとつの入力について、全てのテストケースにおける $|S_i|$ の総和は $10^6$ を超えない

候補文字列を連結した上で辞書順最小にする問題は、以下の記事が参考になる。

• Educational Codeforces Round 9 C. The Smallest String Concatenation (R1700) - けんちょんの競プロ精進記録

ソートするときに 「辞書順で $a+b \lt b+a$ なら $a$ は $b$ より小さい」という順序を定義してこれに従ってソートすると、 ソート結果を連結したものが辞書順最小になる。

ab, abaab, abaabaaab
 ↓
abaabaaab abaab ab

この問題は「その次に小さいの」が何かである。

まず、$a+b=b+a$ となるような2つの文字列がある場合、その2つを入れ替えれば辞書順最小と同じ文字列が作れる。
そのようなペアはソート後の $S=(S_1,...,S_N)$ で隣接しているはずなので、隣接2項を順に確認していけばよい。

以下、そのような文字列ペアはないとする。
答えは、辞書順最小から必ず変化する。

隣接する2つ（$N-1$ 箇所のどこか）を入れ替えればよい。それ以外は辞書順2番目になり得ない。
∵ソート結果 $S=(S_1,...,S_N)$ から添字の転倒数を1増やす毎に必ず辞書順が悪化するので、転倒数 $0$（辞書順最小）の次に小さいのは $1$ 以外にあり得ない。

そして、入れ替える2つはなるべく後ろの方がよさそう。だが、、、
最も後ろの2つ「$S_{N-1}$ と $S_{N}$ を入れ替える」という方法ではWAとなる。

どのような場合に上手くいかないか？を考える。

隣接2項を入れ替えると、少なくともそれがカバーする文字のどこかで辞書順が悪化する箇所が発生する。
だいたいは（入れ替え前の）$S_1$ の範囲で悪化するが、上手くすると $S_2$ の範囲ではじめて悪化する、という例も作れる。

S1=ababa  S2=ab

  [a  b  a  b  a][a  b]
           ↓
  [a  b][a  b  a  b  a]
  ~~~~~~~~~~~~~~  ^
   ここまで同じ   ここで悪化

3項の関係性に広げると、「$S_{2}$ と $S_{3}$ を入れ替える」より「$S_{1}$ と $S_{2}$ を入れ替える」方がよい場合もあることが分かる。

S1=ababa  S2=ab  S3=c

  [a  b  a  b  a][a  b][c]      [S1][S2][S3]の並び

  [a  b][a  b  a  b  a][c]      S1とS2の入れ替え
                  ^
  [a  b  a  b  a][c][a  b]      S2とS3の入れ替え
                  ^

また、末尾から4番目以前の入れ替えは考えなくてよいことも分かる。
たとえば4項 $S_1,S_2,S_3,S_4$ では、「$S_1$ と $S_2$ の入れ替え」より「$S_3$ と $S_4$ の入れ替え」が必ず辞書順で先になる。 $S_1$ と $S_2$ を入れ替えると、2つの文字列が占める部分のどこかの文字が必ず悪化するが、 $S_3$ と $S_4$ の入れ替えでは、この部分の文字にはノータッチのため、辞書順最小が保たれている。

よって、「$S_{N-1}$ と $S_{N}$ の入れ替え」に加えて「$S_{N-2}$ と $S_{N-1}$ の入れ替え」を試すと、十分となる。

Pythonを使っていると全く意識しないままACしてしまったが、 「$a+b \lt b+a$ か？」という文字列比較に $O(|a|+|b|)$ かけ、またソートアルゴリズムが悪いと、TLEとなる。

• 公式Editorial

でも、TimsortはCPythonでしか実装されていない？ような実験結果があったように思うんだけど（記憶違いかも）、 提出時は PyPy で比較に $O(|a|+|b|)$ かけていても、ちゃんと間に合ってるんだよな。。。
なんでだろ。

Python3

from functools import cmp_to_key


def d_sort(a, b):
    ab = a + b
    ba = b + a
    if ab == ba:
        return 0
    if ab > ba:
        return 1
    return -1


key = cmp_to_key(d_sort)


def solve(n, sss):
    sss.sort(key=key)

    for i in range(n - 1):
        if d_sort(sss[i], sss[i + 1]) == 0:
            ans = ''.join(sss)
            return ans

    if n == 2:
        sss[-2], sss[-1] = sss[-1], sss[-2]
        ans = ''.join(sss)
        return ans

    prefix = ''.join(sss[:-3])
    ans1 = prefix + sss[-3] + sss[-1] + sss[-2]
    ans2 = prefix + sss[-2] + sss[-3] + sss[-1]
    ans = min(ans1, ans2)
    return ans


t = int(input())
for _ in range(t):
    n = int(input())
    sss = [input() for _ in range(n)]
    ans = solve(n, sss)
    print(ans)