ABC410の感想戦

2025-06-15

CodeQUEEN 2025 予選 (AtCoder Beginner Contest 410)に参加しました。今回は、A, B, Cの3問正解でした。B問題Reverse Proxyは毎回全スキャンで正解できたが、もう少しループ回数を減らせるように工夫を加えてみました。またC問題Rotatable Arrayでは、リングバッファーを思いつけたので比較的簡単に正解できました。

2025年6月14日に開催されたCodeQUEEN 2025 予選 (AtCoder Beginner Contest 410)に参加しました。今回は、A, B, C問題を正解できました。

A - G1

レースに出場できる年齢制限と年齢が与えられるので、出場できるレースの数を回答する問題。

単純に年齢と年齢制限を比較して、出場できる時は出場可能数を加算しました。

n = int(input())
a = list(map(int, input().split()))
k = int(input())

count = 0
for i in a:
    if i >= k:
        count += 1
print(count)

技術的工夫

ナイーブに条件分岐と加算をループする代わりに、Pythonの内包表記を使う方法も考えられます。

年齢と年齢制限を比較するのは同じですが、内包表記で比較結果を出場可能Trueと出場できないFalseの真理値に変換します。そしてTrueの数をsum()で数えます。

n = int(input())
a = list(map(int, input().split()))
k = int(input())

entry = [True if i >= k else False for i in a]
print(sum(entry))

B - Reverse Proxy

ボールを指示された箱に入れ、どこにボールを入れたか答える問題。ただしボールを入れる箱は毎回指定されるのではなく、\(0\)の場合には先頭から見て一番ボールが少ない箱に入れる必要があります。

\(0\)の場合に毎回全ての箱に入っているボールを数えるのは時間制限を超えるのではないかと思いました。しかしB問題だからという悪知恵を身に着けたので、素直に毎回箱をスキャンするコードを書いて正解できました。

技術的工夫

ボールをどの箱に入れたかを配列で記憶しました。この結果を出力する時にループで1つずつ出力するのではなく、*listを使って出力しました。

n, q = map(int, input().split())
x = list(map(int, input().split()))

box_count = [0 for _ in range(n)]
box_q = []

for i in x:
    if i == 0:
        min_v = box_count[0]
        min_p = 0
        for j in range(1, n):
            if box_count[j] < min_v:
                min_p = j
                min_v = box_count[j]
        box_count[min_p] += 1
        box_q.append(min_p + 1)
    else:
        box_count[i - 1] += 1
        box_q.append(i)

print(*box_q)

もうひと工夫

今回は毎回全ての箱に入っているボールの数を調べました。しかし、これは非効率なことが明らかです。\(0\)でボールを入れる箱を調べる時、ボールを入れる箱の候補が複数あり、その内から先頭を選んでいる可能性です。この時は、再度全ての箱をスキャンするのではなく、前回のスキャン結果を使うことで効率化できます。

def full_scan(box):
    candidate = [0]

    p = 0
    v = box[p]
    for i in range(1, len(box)):
        if box[i] < v:
            p = i
            v = box[i]
            # reset
            candidate = [i]
        elif box[i] == v:
            candidate.append(i)
    return candidate


n, q = map(int, input().split())
x = list(map(int, input().split()))

box_count = [0 for _ in range(n)]
box_q = []

candidate = []

for i in x:
    if i == 0:
        if len(candidate) == 0:
            candidate = full_scan(box_count)

        min_p = candidate.pop(0) # pop at 0. default is -1 or at the last
        box_count[min_p] += 1
        box_q.append(min_p + 1)
    else:
        box_count[i - 1] += 1
        box_q.append(i)
        # update candidate
        if (i - 1) in candidate:
            candidate.remove(i - 1)

print(*box_q)

ただ実際にB問題で試した結果は、使用メモリ量の削減が見られましたが計算速度に関してはケースに含まれる箱の数が最大で100しか無いためかほぼ差がありませんでした。

C - Rotatable Array

3種類の操作が与えられて、順番にこなしていった結果を示す問題。

リストの組み換えなのでa[k:] + a[:k]でローテート処理は簡単です。しかし、これでは想像通り時間制限に引っかかってしまいます。

そこで思いついたのが出力と入力の速度が異なる周辺機器を接続する時に使用するリング・バッファー¹です。これは、入出力がある毎に先頭を示すポインタを更新し、バッファー領域を超えた場合にはバッファーの先頭に戻るという操作をします。これと同じ様に、ローテート操作で内容を移動させるのではなく、先頭を示すポインタの値が変化すると捉えられることに気が付きました。そしてローテート後の\(A_i\)は、ポインタが示す値に\(i\)を加算した相対値で取得できます。

技術的工夫

操作の種類は、最初の1文字で示されます。昔のPythonであればifとelifしかありませんでしたが、今はmatchが使用できます。そこで今回はmatchを使ってスッキリとまとめられました。
シフト操作の回数は、ローテート操作を指示される毎に\(\mod N\)していましたが、\(\max K \times \max Q = 3 \times 10^{14}\)となり\(2^{64}\)よりも小さいので桁溢れの心配はないと判断できます。そこで余りを求める操作をしないことにしました。

n, q = map(int, input().split())
a = [i + 1 for i in range(n)]

head = 0
for _ in range(q):
    q = list(map(int, input().split()))

    match q[0]:
        case 1:
            p = (head + q[1] - 1) % n
            x = q[2]
            a[p] = x
        case 2:
            p = (head + q[1] - 1) % n
            print(a[p])
        case 3:
            k = q[1]
            # head = (head + k) % n
            # max(head) = 3*10^14 < 2^64
            head += k

D - XOR Shortest Walk

解説によると、頂点倍化法というアルゴリズムを使うらしいです。

グラフ問題はAtCoder Beginner Contestの定石なのにグラフをたどる方法を実装できなかったので、この問題が少し応用的とはいえ基本的なグラフをたどるアルゴリズムはマスターしておきたかったです。

リングバッファ ↩︎