AtCoder ABC468振り返り (PythonでABC+D問題)

ABC468を振り返ります

今回はABCまで3問解答でした。

D問題はなんとなく解けそうな雰囲気があったんですが、TLEでした。
解説を見たら、これは思いつかなかったし、どちらにしても、解けなかったなと言う感じです。

フジロックの配信をBGMに聞きながらやったので、集中力が低めになってしまいました。
A問題は解くのが遅かったし、B問題で1回WAしてしまいました。
まあ仕方がないですね。

A - Maximal Value

条件を満たしているパターンをカウントして、出力します。

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

count = 0
for i in range(1, N - 1):
    if A[i-1] < A[i] and A[i] > A[i + 1]:
        count += 1

print(count)

B - Corridor Watch

全探索で求めます。
現在のマスが "." なら、周囲 D の範囲内にGがあるかをチェックし、いなければカウントします。

M, D = map(int, input().split())
S = input()

count = 0
for i in range(len(S)):
    # マスがGそのものの場合は対象外
    if S[i] == "G":
        continue

    # マスが.の場合、範囲内のGを探査する
    left = max(0, i-D)
    right = min(M, i+D+1)
    exist = False
    for j in range(left, right):
        if S[j] == "G":
            exist = True
            break

    # Gがいないのでカウント
    if exist == False:
        count += 1

print(count)

C - Between P and Q

いわゆる順列全探索なので、 permutations を使用しました。
P, Q は比較しやすいように、数値に変換しています。
(数値配列→数値 変換は、一旦文字列に変換して数値変換でも良かったかも)

from itertools import permutations

N = int(input())
P = list(map(int, input().split()))
Q = list(map(int, input().split()))

# Aを作成
A = []
for i in range(1, N+1):
    A.append(i)

# Pを数値にする
p_num = 0 
reverse_p = P[::-1]
for i in range(len(P)):
    p_num += reverse_p[i] * (10 ** (i))

# Qを数値にする
q_num = 0 
reverse_q = Q[::-1]
for i in range(len(Q)):
    q_num += reverse_q[i] * (10 ** (i))

ans = 0

# Aの並び替えを順列全探索
for a in permutations(A):
    # Aを数値にして比較
    a_num = 0 
    reverse_a = a[::-1]
    for i in range(len(a)):
        a_num += reverse_a[i] * (10 ** (i))

    if p_num < a_num and a_num < q_num:
        ans += 1

print(ans)

D - Pre-Palindrome

D問題はコンテスト後に解説を見て解きました。

回分の中心点を動かして全探索する、という発想は思いつきませんでした。
あと、回文文字数が偶数のときと、奇数の時のカウントの仕方の工夫も思いつきにくいところです。

S = input()

count = 0

# 回分の中央を全探索
for center in range(len(S)):
    # 回分の文字数が偶数か奇数か療法で調べる
    for k in range(2):
        left = center - k
        right = center
        diff_count = 0

        while 0 <= left and right < len(S):

            if S[left] != S[right]:
                diff_count += 1

            # 左右違う文字が2個以上になったら、条件を満たさない
            if diff_count >= 2:
                break

            left -= 1
            right += 1
            count += 1

print(count)