ABC385 感想まとめ

ユニークビジョンプログラミングコンテスト2024 クリスマス（AtCoder Beginner Contest 385） - AtCoder

今回は、師走の忙しさに振り回されてリアルタイム参加が出来なかったので、翌日に復習しました。

個人的にはC問題が難しく感じて結局解けなかったのですけども、Difficulty:445とC問題としては普通の難易度のようでした。

D問題は自分にとってはちょっと難易度が高めだったのですけども、SortedSetの勉強を兼ねて解説を見ながら書いてみました。

A - Equally

A, B, C をうまく場合分けすればokでした。

A, B, C = map(int, input().split())

if A == B == C:
    print("Yes")
    exit()
if A + B == C or B + C == A or A + C == B:
    print("Yes")
    exit()

print("No")

B - Santa Claus 1

B問題としては、実装量が多めだったような印象です。地図の探索問題なので、コード量が多くなりますね。

H, W, X, Y = map(int, input().split())

# Mapの四辺を # で囲うことで、配列のindexと座標を合わせている
S = []
S.append("#" * (W + 2))
for i in range(H):
    S.append("#" + input() + "#")
T = list(input())
S.append("#" * (W + 2))

current = (X, Y)
count = 0
visited = set() # 訪問済の家を記録するset
for i in range(len(T)):
    t = T[i]
    move = (0,0)
    if t == "U":
        move = (-1, 0)
    elif t == "D":
        move = (1, 0)
    elif t == "L":
        move = (0, -1)
    elif t == "R":
        move = (0, 1)

    next = (current[0] + move[0], current[1] + move[1])
    if S[next[0]][next[1]] == "#":
        continue
        
    # 未訪問の家だった場合はカウントする
    if S[next[0]][next[1]]  == "@":
        if next not in visited:
            count += 1
        visited.add(next) # 訪問済に追加
    current = next

print(current[0], current[1], count)

公式解説では、「同じ家を複数回数えないようにするためには、(中略) 到達した家の個数のカウントを1増やし、その家を破壊するのが単純な方法でしょう。」と書いてあり、ずいぶん物騒なサンタさんやな...と思ったのでした

C - Illuminate Buildings (解説AC)

今回困った問題でした。素直に配列の先頭から見ていくとTLEになってしまうのは見えていたので、どう工夫するかの問題なんですけども。

わからなかったので解説を見てACしました。

ポイントは、文字の間隔でループさせることです。こうすることで、計算量がぐっと減るわけですね。

特定のアルゴリズムを知らなくても解けるので、実は良問なのかもしれません。

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

answer = 1
# space文字間隔で、最長何文字連続があるか？を探索する
for space in range(1, N):
    for base_index in range(space):
        before_value = H[base_index] # 直前の値
        count = 0 # 連続カウント数
        for i in range(base_index, N, space):
            if before_value == H[i]:
                # 直前の値と同じなら、カウントを増やす
                count += 1
                answer = max(answer, count)
            else:
                # 直前の値と異なるなら、カウントをリセット
                count = 1
                before_value = H[i]
print(answer)

D - Santa Claus 2 (解説AC)

問題文を読んで「SortedSetを使うのかな？」と思っていたら、やはりそうでした。SortedSetをあまり使ったことがないため、経験を積むためにコードを書いてみました。

「SortedSet の区間 left - right の間の要素を削除する」という処理がうまく書けず、結局かなり解説を参考にしています。

工夫どころとしては、家の座標を rows_dict と cols_dict という行と列で持っています。

~~サンタが横方向に動くときは rows_dict から家を消去~~
~~サンタが縦方向に動くときは cols_dict から家を消去~~

~~とし、「最終的に rows_dict と cols_dict 両方にある家が、サンタが未訪問の家」と判定するようにしてます。~~

(12/25 追記)
上に書いたような面倒なことをしなくても、以下のようにすれば O(1) で家を消せますね...。

# 座標(X, Y)にある家を訪問したら、row,col両方から家(X, Y)を消す
rows_dict[Y].discard(X)
cols_dict[X].discard(Y)

下の解答コードよりも、こちらの方法のほうが速いです。

参考：解説 - ユニークビジョンプログラミングコンテスト2024 クリスマス（AtCoder Beginner Contest 385）

SortedSetのソースは、GitHub - tatyam-prime/SortedSet を使わさせていただきました。


# ここにSortedSetのコードを入れてください
# ここにSortedSetのコードを入れてください

N, M, SX, SY = map(int, input().split())

homes = []
rows_dict = defaultdict(SortedSet)
cols_dict = defaultdict(SortedSet)
for i in range(N):
    X, Y = map(int, input().split())
    homes.append((X, Y))
    rows_dict[Y].add(X)
    cols_dict[X].add(Y)


for i in range(M):
    D, C = input().split()
    C = int(C)

    next_x = SX
    next_y = SY

    # 方向ごとに処理
    if D == "U":
        next_y += C
        # SY...next_ｙ 間の家を削除
        lower_value = SY
        upper_value = next_y

        while True:
            value = cols_dict[SX].le(upper_value)
            if value is None or value < lower_value:
                break
            cols_dict[SX].discard(value)

    elif D == "D":
        next_y -= C

        # next_ｙ...SY 間の家を削除
        lower_value = next_y
        upper_value = SY

        while True:
            value = cols_dict[SX].le(upper_value)
            if value is None or value < lower_value:
                break
            cols_dict[SX].discard(value)

    elif D == "L":
        next_x -= C
        # next_x - SX 間を削除
        left_value = next_x
        right_value = SX

        while True:
            value = rows_dict[SY].le(right_value)
            if value is None or value < left_value:
                break
            rows_dict[SY].discard(value)
        
    elif D == "R":
        next_x += C
        # SX ... next_x 間を削除
        left_value = SX
        right_value = next_x

        while True:
            value = rows_dict[SY].le(right_value)
            if value is None or value < left_value:
                break
            rows_dict[SY].discard(value)

    # 座標更新
    SX = next_x
    SY = next_y

# 両方残っているのだけが、未訪問の家
non_visit_count = 0
for home in homes:
    X, Y = home
    if X in rows_dict[Y] and Y in cols_dict[X]:
        non_visit_count += 1

print(SX, SY, N - non_visit_count)