AtCoder ABC416 解いてみた(PythonでABCD問題)

ABC416を振り返ります

今回はリアルタイム参加出来なかったので、復習回です。
ざっくり時間を図って問題を解いた感じでは、100分以内で解けたのはC問題まででした。
D問題は、概ね解答を導けていたんですけども、TLEが取れなかったです。

A - Vacation Validation

L, Rの区間の文字を調べて、"x" が見つかったらNoを出力します。

N, L, R = map(int, input().split())
S = input()

# L, Rの区間の文字を調べて、"x" が見つかったらNoを出力。
for i in range(L-1, R):
    if S[i] == "x":
        print("No")
        exit()
print("Yes")

B - 1D Akari

問題の意味がわかりにくい問題でした。
問題文を読みまして、「#が出てきたら、oを1つ加えることができる」ということかと理解しました。

以下の処理をおこなって、答えを求めました...。

• 最初に "." が出現したら、"o"に変換する
• その後、"#." と文字が並んでいたら "#o" に書き換える

S = list(input())
T = S.copy()

first = False
for i in range(len(T)):
    if T[i] == "." and not first:
        T[i] = "o"
        first = True
        continue
    if T[i] == "." and i > 1 and T[i-1] == "#":
        T[i] = "o"
        continue
print("".join(T))

C - Concat (X-th)

条件がゆるいので、いったんすべての文字列を作成してしまって、それをソートすれば良さそうです。

そうすると、[1,1][1,2][1,3]...[3,1][3,2][3,3] みたいな組み合わせを作る必要があります。pythonでは、itertools.product() で作ることが出来ます。

N, K, X = map(int, input().split())
S = []
for i in range(N):
    S.append(input())

# itertools用の配列を作成
c = []
for i in range(N):
    c.append(i)

# itertools.product()で、ある配列の組み合わせ(重複可)を作れる
str_list = []
for v in itertools.product(c, repeat=K):
    # 文字列を作成し、配列に追加
    s = ""
    for i in range(len(v)):
        s += S[v[i]]

    str_list.append(s)

# 配列をソートしてX番目を表示
str_list.sort()
print(str_list[X-1])

D - Match, Mod, Minimize 2

これは解説を読んでACしました。

(A+B) % M の合計を求めるのですけども、Modの性質からいかが成り立ちます

• A+B < M → A+B
• A+B >= M → A+B - M

というわけで、「A+B >= MになるA,B」の組み合わせを最大にすれば、良いというわけでした。

答えは sum(A) + sum(B) - count * M で求まってしまいます。

T = int(input())
for i in range(T):
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))

    A.sort()
    B.sort(reverse=True)
    
    count = 0 # 条件を満たすBのカウント数
    index_a = -1 # 探索済のAの位置

    for j in range(len(B)):
        # 尺取法で B + A >= M となるような Aを探す
        # index_a までは捜索済なので、探さなくて良い
        for k in range(index_a + 1, len(A)):
            index_a = k
            if A[k] + B[j] >= M:
                count += 1
                break
    
    answer = sum(A) + sum(B) - count * M
    print(answer)