😊

Atcoder - ABC339 勉強会まとめ

yamasaKit

2024/04/12に公開

競技プログラミング

AtCoder

tech

背景

Cykinso の研究&データ技術開発の山﨑です。

Cykinso 社内には競技プログラミング部があり、コンテストに参加している人していない人含め、ワイワイ問題を解いてます。

今回は ABC339 A, B, C, F をとりあげたので復習用にまとめておきます。

https://atcoder.jp/contests/abc339

What's 競プロ？

競プロとは競技プログラミングの略です。
競技プログラミングとはコンピュータサイエンスに関する問題や純粋に実装が重い問題が出題されそれをバグを含まず速く解くことを競う競技です。

プログラミング学習をゲーミフィケーションした成功例とも言えます。

競プロのコンテスト

競技プログラミングの大会は「コンテスト」と呼ばれています。
海外も含めると週に3, 4回は開催されており毎週参加することができます。

日本で有名な競技プログラミングのサービスは以下の3つです。社内の部活動では最初のAtCoderと呼ばれている日本で一番規模が大きいサービスの問題を解いています。

海外まで範囲を広げるとさらに以下のようなサイトがあります。

A - TLD

問題文
英小文字と . のみからなる文字列
S が与えられます。
S を . で分割したときの末尾の文字列を出力してください。
すなわち、. を含まない
S の接尾辞のうち最長のものを出力してください。

. が必ず1つ含まれるので Python なら split で . で分割し末尾の -1 を出力すればOKです。

ans = input().split(".")[-1]
print(ans)

ちなみにコンテスト中は気づかなかったですが TLD は Top Level Domain の略のようです。

B - Langton's Takahashi

トーラス状というのは簡単にいうとドラクエのフィールドのように世界の一番左端にいったら右端から出てくる状態です。したがってドラクエのマップみたいにちょこちょこ反対から出たり入ったりする移動を繰り返します。

現在、向いている方向を cur という変数に整数で保存しておき、時計回りあるいは反時計回りに向きを変えるたびに +1, -1 します。その結果 cur が -1 や 4 になる場合があるので mod 4 をしておくのがポイントですね。

その後、実際に移動させてあげトーラス状なのでグリッドの端に行った場合の処理も mod $H$ または mod $W$ してあげるとよいですね。

やや重目の実装ができますか？という感じの問題でした。

H, W, N = map(int, input().split())
G = [["."] * W for _ in range(H)]

directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]
cur_direction = 0
cur_h = 0
cur_w = 0

for _ in range(N):
    match G[cur_h][cur_w]:
        case '.':
            # 現在いるマスを黒にして時計回りに90度回転する
            G[cur_h][cur_w] = '#'
            cur_direction += 1
            cur_direction %= 4
        case '#':
            # 現在いるマスを白にして反時計回りに90度回転する
            G[cur_h][cur_w] = '.'
            cur_direction -= 1
            cur_direction %= 4
    # 現在向いている方向に進む
    dh, dw = directions[cur_direction]
    nh = (cur_h + dh) % H
    nw = (cur_w + dw) % W
    cur_h = nh
    cur_w = nw

for g in G:
    print("".join(g))

C - Perfect Bus

途中のバス停で人が乗り降りしていて現在の乗客がマイナス $X$ 人という謎の状態にならないためには最初に最低何人乗っていたらいいですか？という問題です。

最初に $0$ 人乗っていたと仮定した時、途中の乗り降りで人が増えたり減ったりしますが、これはまさに累積和と言えます。
累積和を求めて一番低い値が $Y$ という負の値である時、そこが $0$ になるように帳尻を合わせるために最初に $Y$ 人乗ってれば良いと言えます。

なお、一番低い値が負にならない時があるのでその場合の処理をしないといけないのに注意です。勉強会時、不覚にも WA になりました。

from itertools import accumulate

N = int(input())
A = list(map(int, input().split()))

acc = list(accumulate(A))

x = min(acc)
if x > 0:
    ans = acc[-1]
else:
    ans = -x + acc[-1]

print(ans)

なお、コンテスト中は「最初に $x$ 人乗っていると仮定した時、すべてのバス停で乗客がマイナスにならないか？」という関数を作り二分探索で最小値を求めました。こちらでも計算量は $O(N logN)$ となり AC できます。

N = int(input())
A = list(map(int, input().split()))

ng = -1
ok = 10 ** 19

def is_ok(x):
    y = x
    for a in A:
        y += a
        if y < 0:
            return False
    return True

while ok - ng > 1:
    mid = (ok + ng) // 2
    if is_ok(mid):
        ok = mid
    else:
        ng = mid

ans = ok + sum(A)
print(ans)

F - Product Equality

勉強会では時間の関係もあり D, E を飛ばし、解説 AC でしたがやっていることがおもしろかった F に取り組みました。

まず制約が以下のように小さい時を考えます。

$1 \leq N \leq 100$
$1 \leq A_{i} \leq 10^{10}$

ぐらいなら B 問題ぐらいの難易度でしょうか？

これなら for を３回ループで全探索でカウントしても計算量は $O(N^{3})$ = $10^{6}$ となり余裕で間に合います。

A = list(map(int, input().split())

ans = 0
for i in range(N):
    for j in range(N):
        for k in range(N):
            if A[i] * A[j] == A[k]:
                ans += 1

print(ans)

次に

$1 \leq N \leq 1000$
$1 \leq A_{i} \leq 10^{10}$

を考えます。今度は $O(N^{3})$ = $10^{9}$ となってしまうため愚直に全探索すると TLE になってしまいます。

そこで $i$ と $j$ だけ全探索し、 $A[i] \times A[j]$ と同じ値が $A$ に含まれているかを defaultdict を用いて O(1) でチェックします。 (defaultdict のすでに存在する key であれば ans が +1 され、そうでなければ +0 されるようになっています)

左辺のパートナーである右辺は多くてただ１つなので先程のように for を回す必要が実はないというイメージですね。計算量は $O(N^{2})$ です。

from collections import defaultdict

A = list(map(int, input().split())
D = defaultdict(int)
for a in A:
    D[a] += 1

ans = 0
for i in range(N):
    for j in range(N):
        ans += D[A[i] * A[j]]

print(ans)

最後に F の問題の制約を考えてみます。

$1 \leq N \leq 1000$
$1 \leq A_{i} \leq 10^{1000}$

今度は $A_{i}$ が非常に大きいため Python では計算できないこともないのですが、非常に時間がかかるため、このままでは TLE になってしまいます。

そこで $A_{i} % x × A_{j} % x = A_{k} % x$ という式が成立することからあらかじめ $A$ の値を $x$ で割り、リスト $B$ として保存し、

「 $B_{i} × B_{j}$ と同じ値が $B$ に含まれているなら $A_{i} × A_{j} = A_{k}$ 」とみなす

と仮定します。

結論から言うと、この仮定はうまくやれば成立するのですが、1つ問題点があります。
それは $x$ の値によっては MOD の値が等しくなってしまうことがあることです。

例えば、 $x = 4, A = [4, 7, 20]$ としたら

$4 \times 7 = 28$ なのに
$(4 mod 4) \times (7 mod 4) = (20 mod 4) = 0$ と等しいとみなされてしまいます。

ではさらにどう工夫するか？

上記のように本来等しくない値同士が等しいとみなされてしまうことは、 mod をとることをハッシュ化とみなすと、 4 と 20 のハッシュが衝突していることが原因と言えます。

したがってハッシュがどのくらいの確率で衝突するか考えて、計算が大変じゃないかつ確率的にほぼ 0 の値になるように $x$ の値を大きくするとよさそうです。

$1 \leq N \leq 1000$ の制約を考えると例えば $x$ の値を 100 とすると鳩の巣原理より必ず衝突します。箱を 100 個用意し 1000 個のボールをランダムに入れたら必ずいずれかの箱に2つ以上ボールが入ると考えるとわかりやすいです。

では $x$ の値をどの程度まで大きくしたらよいでしょうか？
例えば $N = 10$ , $x = 100$ とした時のすべてのハッシュが衝突しない確率を求めてみます。

すべてのハッシュの選び方は $100^{10}$ 通りあります。

一方、ハッシュが衝突しない選び方は
1個目のハッシュを選ぶ方法は $100$ 通り
2個目のハッシュを選ぶ方法は $99$ 通り
3個目のハッシュを選ぶ方法は $98$ 通り
4個目のハッシュを選ぶ方法は $97$ 通り
5個目のハッシュを選ぶ方法は $96$ 通り
...
10個目のハッシュを選ぶ方法は $91$ 通り
となります。

よって式にすると

$(すべてのハッシュが衝突しない確率) = (100 × 99 × ... 91) / 100^{10} = 0.6282$

と、約62.8% と計算されます。逆に言えば「いずれかのハッシュが衝突する確率」は約37.2%と非常に高いです。

細かい計算は割愛しますが、 $N = 1000$ の時に、この確率が十分 $0$ になる $x$ を調べると $10^{33}$ ~ $10^{34}$ ぐらいになります。

確率をちゃんと計算しといてイメージの話をしていしまいますが、箱を $10^{33}$ 個用意し 1000 個のボールをランダムに入れるのを何度繰り返してもいずれかの箱に２つ以上ボールが入っているところはとても想像できないのではないでしょうか。

以上のことから、 $10^{33}$ ~ $10^{34}$ ぐらいの $x$ の値をキーボードを適当に叩いてアサインしましょう。

from collections import defaultdict

N = int(input())
A = [int(input()) for _ in range(N)]
x = 98080989074039189058908908209992

B = [a % x for a in A]
D = defaultdict(int)
for b in B:
    D[b] += 1

ans = 0
for i in B:
    for j in B:
        ans += D[(i * j) % x]
print(ans)

ちなみに $x = 10^{33}$ とするとキレイな値過ぎて衝突します。素数や素数のように約数が少ない値がよりハッシュが衝突しにくくなるようです。

余談ですが、逆に「 $x$ の値が小さいと実は思っている以上にハッシュが衝突するよ」という話に帰着できるのが「誕生日のパラドックス」ですね。

簡単に言うと「 $N$ 人の人がいて、その中のいずれかの２人の誕生日が一致している確率は意外と高い」というのが「誕生日のパラドックス」ですが、これは $x = 365$ とした時のいずれかのハッシュが衝突する確率を求めることになり、例えば $N = 40$ とすると確率は $89.1$ %と非常に高くなります。

Cykinso's Tech BlogPublication

「細菌叢の力で人々を健康に」をミッションに掲げるバイオテックスタートアップ「サイキンソー」の技術ブログ。