AtCoder ABC379 復習(緑コーダーがPythonでA〜D問題まで)

ABC379 感想まとめ

今回も体調に不安がありUnratedで参加です。A-Dまで4問解答でした。

今回はC問題の難易度(951)がD問題(745)より難しかったようです。わたしもC問題は60分かけて、4回WAして、ようやく正解にたどり着いております...。

それでも諦めずにC問題を解いて、D問題も残り20分しかない状況で解答できたので、諦めない姿勢が良かったなと思います。

もしRated参加だったら1000パフォーマンスくらいは出ていて、レーティングも少し上がっていたはずなので、もったいなかったです。これはまあUnratedで気楽に参加している以上、仕方がないですね。

A - Cyclic

入力の3桁の値(a, b, c)をそれぞれを求めておき、それを 100倍とか10倍して出力します。

N = int(input())
c = N % 10
b = N // 10 % 10
a = N // 100

print(b*100 + c*10 + a, c*100 + a*10 + b)

B - Strawberries

入力文字列 S の先頭から1文字ずつチェックしていきます。連続で出現した回数を保存しておいて、それが基準値を超えた回数を答えとして出力します。

N, K = map(int, input().split())
S = input()

sequence = 0 # "O"の連続回数
count = 0 # "OOO..."が何回出たか

for i in range(N):
    if S[i] == "O":
        sequence += 1

        # 連続がK回になった場合
        if sequence == K:
            count += 1
            sequence = 0
    else:
        # "O" でない場合は連続をリセット
        sequence = 0
print(count)

C - Sowing Stones

C問題が今回の難問でした。私も60分かけて、4回WAして、ようやく正解にたどり着いております。

方針

石があるマス(X1)から、次の石のあるマス(X2)まで、1個ずつ石をおいていきます。石が足りなくなったら、-1 を出力して終了します。

石を移動する際にかかるコストは以下の cost1, cost2 の合計になります。

cost1 : X1からX2までの間に入れる石のコスト

X1 - X2間の空マスが1つ → コスト=1
X1 - X2間の空マスが2つ → コスト=1+2
X1 - X2間の空マスが3つ → コスト=1+2+3

なので、コストは等差数列の和 (empty + 1) * empty // 2 で求められます。

cost2 : X1からX2まで石を移動するコスト

空きマスに入り切らない石は、X2まで移動します。これは単純に、

(移動する石の数) * (移動するマスの距離)

で求められます。

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

# Xをソートしておく(重要)
sorted_x = sorted(zip(X, A))

# 石の総数とマスの数が一致していない場合は、不可能
if sum(A) != N:
    print(-1)
    exit()

# 1番目のマスに石が置かれていない場合は、不可能
if sorted_x[0][0] != 1:
    print(-1)
    exit()

# 最後のマスに石が2つ以上ある場合は、不可能
if sorted_x[-1][0] == N and sorted_x[-1][1] > 1:
    print(-1)
    exit()

# 簡単に考える用に、最後のマスを入れておく
if sorted_x[-1][0] != N:
    sorted_x.append((N, 0))

current_index = 1 # 現在位置
stock_count = 0 # 現在の石の数
cost = 0 # 移動コスト

for i in range(1, len(sorted_x)):

    # 現在位置と、石の数を更新
    current_index = sorted_x[i-1][0]
    stock_count += sorted_x[i-1][1]

    # 次の石のある場所
    next_index = sorted_x[i][0]

    # 現在のマスから次の石のあるマスまで行けるか判定
    if next_index - current_index > stock_count:
        print(-1)
        exit()
    else:
        # 現在のマス - 次のマスまでの間の空箱に入れる石のコスト
        empty_count = next_index - current_index - 1
        move1_cost = empty_count * (empty_count + 1) // 2

        # 現在のマスから次のマスまで石を移動するコスト
        move2_cost = (stock_count - empty_count - 1) * (next_index - current_index)

        # 現在の箱に入れる分を引く
        stock_count -= 1

        # 空箱に入れる分を引く
        stock_count -= empty_count

        cost += move1_cost + move2_cost
        current_index = next_index
        
print(cost)

誤回答の原因

どこで間違っているかというと、『入力「X1, X2...」がソートされていない場合もある』という条件を見落としており、これが理由で何回もつまずいてしまいました。

入力例ではソートされていたので、気づかなかったんや...。

D - Home Garden

これは両面キュー(pythonならdeque)を知っていれば、比較的簡単に解ける問題でした。

各Queryごとに、dequeに値を入れたり、値を一つ一つ取り除いたりしていけば大丈夫です。

一見すると計算量が多くTLEになってしまいそうですけども、Qの数は最大 2x10^5 なので、十分に間に合います。

from queue import deque

Q = int(input())

# 両面キュー
que = deque()
current_time = 0

for i in range(Q):
    query = input().split()
    if query[0] == '1':
        # queue に値を追加(現在時刻を記録)
        que.append(current_time)
    elif query[0] == '2':
        # 現在時刻を更新
        current_time += int(query[1])
    else:
        H = int(query[1])
        count = 0
        # Queueに入ってから H以上経過したものは、Queueから取り除く
        while que and current_time - que[0] >= H:
            que.popleft()
            count += 1
        print(count)