ABC 405の感想戦

2025-05-12

at_coder, python

AtCoder Beginners contes に参加し始めて、初めて A, B, C, D の 4 問を時間内に正解できました。ここではどのように回答したかを振り返ってみます。

B - Not All

与えられたその数列から、1 から指定された数字までの数列の一部を含まないようにするための削除回数を回答する問題でした。

そのため削除した時に条件を満たしているか調べる必要があります。しかし、この時に毎回残りの数列をスキャンして条件を満たすか調べたのでは制限時間を超えることが目に見えました。

そこで、逆に考えることにしました。後ろから削除していって条件を満たさなくなるということは、前から見ていくと回答となる位置で条件を満たすということです。

そこで、条件となる数字をset()に入れておき、これが空になった時に条件が成立すると判断しました。

all()

私は消去法で条件を満たす判断をしましたが、Python では引数の List が全てTrueの時になるall()を使用して条件の成立を判断できることを知りました。

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

expected = [False for _ in range(m)]
# print(expected)
for i in range(n):
    tmp = a[i]
    if tmp <= m:
        expected[tmp - 1] = True
        if all(expected):
            print(n - i)
            exit()
print(0)

C - Sum of Product

$A_1$から$A_N$までの数列が与えられ、$\sum_{1\le{i}\lt{j}\le{N}} A_iA_j$を計算する問題です。このタイプの問題は、累積和と言うそうです。

素直に i と j の二重ループだと時間制限を満たせないのでうまい方法を考えます。

そこで i=1 の場合に注目すると、

$$ A_1 * A_2 + A_1 * A_3 + … + A_1 * A_N = A_1 * (A_2 + A_3 + … + A_N) $$

となっています。そして、i=2 の場合は、

$$ A_2 * A_3 + A_2 * A_4 + … + A_2 * A_N = A_2 * (A_3 + A_4 + … + A_N) $$

となり、カッコ内に注目すると$A_i$の計算を進める毎に加算する項目が減っていく法則が見つかります。

最後から計算

そこで、$A_{N-1} *A_N$、次に$A_{N-2} * (A_{N-1}+A_N)$と後ろから計算することで、前の項の加算結果を使って計算することで二重ループを回避できます。

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

total = 0
sum = 0
for i in range(n - 1, 0, -1):
    sum += a[i]
    total += a[i-1] * sum
print(total)

加算項を減らしていく方法

これと同じ方法で、最初に加算項の合計を計算しておき、掛け算を進める毎に加算項を減らしていく方法も考えられます。

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

total = 0
sum = sum(a)
for i in range(0, n - 1):
    sum -= a[i]
    total += a[i] * sum
print(total)

そんな方法があるのか解

しかしもっとスマートに得方法があることを@ilaoから知りました。

数列を 2 次元配列に見立てて、今回の問題を考えると

$$ A_1 * (A_1 + A_2 + … + A_N) + A_2 * (A_1 + A_2 + … + A_N) + … A_N * (A_1 + A_2 + … + A_N) $$

から

$$ A_1 * A_1 + A_2 * A_2 + … + A_N * A_N $$

を引いた結果を 2 で割ったものとなります。言葉で説明するとうまく伝わらないので、この方法を教えてくれた@ilaoのメッセージを見てください。

D - Escape Route

通路と壁からなる地図が与えられて、地図表の非常口へ向かう最短経路を示す矢印を通路に付ける問題。

ABC400 の D 問題 Takahashi the Wall Breakerで覚えた paint 手法を使うことを思いつきました。最終的に非常口に到達するので、非常口から 1 ステップずつ広げてゆき、各通路のマスにどちらから来たかの反対向きの矢印を付ければ回答となります。

Python の文字列

Python の文字列は、List 型のように文字列の各文字を str[n]のようにアクセスすることができます。そこでマップの要素を分解する必要がないと最初は考えました。

しかし、通路を矢印で置換することができません。

a="123"
a[0] # '1'

a[0] = 'x'
# TypeError: 'str' object does not support item assignment

そこで文字列を文字の配列にする必要があり、list()で分解できることを初めて知りました。

a="123"
list(a) # ['1', '2', '3']

h, w = map(int, input().split())

map = []
for _ in range(h):
    s = list(input())
    map.append(s)

# print(map)
next_pos = []
for y in range(h):
    for x in range(w):
        if map[y][x] == 'E':
            next_pos.append((y, x))
# print(next_pos)

while len(next_pos):
    this_pos = next_pos
    next_pos = []
    for pos in this_pos:
        # upper
        y = pos[0] - 1
        x = pos[1]
        if 0 <= y < h and 0 <= x < w:
            if map[y][x] == '.':
                map[y][x] = 'v'
                next_pos.append((y, x))

        # down
        y = pos[0] + 1
        x = pos[1]
        if 0 <= y < h and 0 <= x < w:
            if map[y][x] == '.':
                map[y][x] = '^'
                next_pos.append((y, x))

        # right
        y = pos[0]
        x = pos[1] + 1
        if 0 <= y < h and 0 <= x < w:
            if map[y][x] == '.':
                map[y][x] = '<'
                next_pos.append((y, x))

        # left
        y = pos[0]
        x = pos[1] - 1
        if 0 <= y < h and 0 <= x < w:
            if map[y][x] == '.':
                map[y][x] = '>'
                next_pos.append((y, x))

for y in range(h):
    print("".join(map[y]))