AtCoder ABC409 振り返り(緑コーダーがPythonでABCD問題)

ABC409を振り返ります

今回はABCDまで4問解答、(2回誤答)でした。

問題文の意味を把握するのが不十分で、2回誤答を提出してしまいました。日中から、どうも文章を読んでいても頭に入らなくて嫌な予感があったのですけども、それが結果に出てしまいました。

レーティングは微増でした。2ペナがなければもう少し増えたのでしょうけども、減らなかっただけで良かったのかもしれません。

A - Conflict

T、Aを全探索しまして、両方とも "o" かどうかをチェックします。

N = int(input())
T = list(input())
A = list(input())

for i in range(N):
    if T[i] == "o" and A[i] == "o":
        print("Yes")
        exit() 
print("No")

B - Citation

解法は、0...100の中で、条件を満たすものを全探索しました。 Aをソートしておき、i がAの中でどこに位置するか...を求めれば、Aの中でi以上の要素数を求めることができます。

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

# Aをソートしておく
A.sort()

# 要素数は最大100なので、とりあえず最大までループ
answer = 0
for i in range(101):
    # Aの中で i の入る位置を求める
    index = bisect.bisect_left(A, i)

    # 残り枚数が i 以上であれば、条件を満たす
    remaining = N - index
    if remaining >= i:
        answer = i
print(answer)

ここで1ペナしてしまいました。見落としていたのは、例えば入力列が A=[7, 7, 7] のときに答えが 3 になるパターンです。てっきり答えは Aiの中のどれか...だと思い込んでしまったためでした。

C - Equilateral Triangle

この問題も、問題の意味を理解するのに時間がかかりました...。

円周が L で与えられているので、点1 を含む頂点で正三角形ができるのは、以下の3点が選ばれたときです。

• 点 1
• 点 1 + L // 3
• 点 1 + 2 * (L // 3)

ということで、円周上の各点の位置の数を求め、上記の条件を満たす組み合わせの数を数えればokです。

N, L = map(int, input().split())
D = list(map(int, input().split()))

# 円周が3の倍数でない場合は、正三角形は存在しない
if L % 3 != 0:
    print(0)
    exit()

# 各ポイントに何個の点があるかを記録する配列
points = [0] * (L + 1)
points[0] = 1
current = 0

# 時計回りに d 進めて、そこの点を数をカウントする
for d in D:
    current = (current + d) % L
    points[current] += 1

# 正三角形の数をカウント
count = 0
for i in range(L // 3 + 1):
    point1 = points[i]
    point2 = points[i + L // 3]
    point3 = points[i + 2 * (L // 3)]
    count += point1 * point2 * point3

print(count)

D - String Rotation

テストケースを観察すると、以下のことがわかります。

ATCODER → ACODERT
* A < T > C ... なので、Tを交換して後ろに持っていく
* T 以降に Tより大きい文字が無いので、Tは一番うしろにつける

SNUKE → NSUKE 
* S > N なので、Sを交換して後ろに持っていく
* S 以降で Sより大きい文字はUなので、SはUの前につける

ABCDEF → ABCDEF
* A < B < C < D < E < F → 交換の必要なし

• 文字が昇順に並んでいるときは交換する必要がない。降順の所があれば、文字を交換する
• 交換する文字は、交換文字よりも大きい文字の手前にシフトする

という操作をすれば、辞書順で最小になります。

T = int(input())

# 最小の文字列を求める
def calc_small_string(s):
    n = len(s)

    # 交換候補を求める
    swap_candidate = ""
    for i in range(n-1):
        if swap_candidate == "" and s[i] > s[i + 1]:
            swap_candidate = s[i]
            break

    # 交換候補があれば、交換
    if swap_candidate != "":
        done = False
        swap = ""
        queue = deque()
        for i in range(n):
            # 交換候補はキューに入れずに保持する
            if not done and swap == "" and s[i] == swap_candidate:
                swap = s[i]
                continue

            # 交換候補を入れる場所があれば、そこにいれる
            if not done and swap != "" and s[i] > swap:
                queue.append(swap)
                queue.append(s[i])
                done = True
                continue
            
            queue.append(s[i])

        # 交換候補をいれる場所がなければ、文字列の最後につける
        if not done:
            queue.append(swap_candidate)

        return "".join(queue)

    # 交換候補がなければ、文字列はそのまま
    return "".join(s)

# 各候補に対する処理を行う
for i in range(T):
    N = int(input())
    S = list(input())
    small_s = calc_small_string(S)
    print(small_s)