AtCoder ABC412 振り返り(緑コーダーがPythonでABC問題)

ABC412を振り返ります

今回はABCまで3問解答(1ミス)でした。

C問題でだいぶ手こずってしまい、解けたのが終了間際になってしまいました。優先度付きキューを使うのか？とか、色々迷ってしまって、コードを書いては消しを繰り返してしまいました。

ややこしい仕様になる場合は、いったん紙に書いたりしてまとめないといかんですね...。

A - Task Failed Successfully

各日付について、AとBを比較していきます。

N = int(input())

# A < B の日数を求める
count = 0
for i in range(N):
    A, B = map(int, input().split())
    if A < B:
        count += 1

print(count)

B - Precondition

以下のように全探索します。文字列 S, T がそれほど大きくないので(100文字以下)、全探索で間に合います。

1. Sの中の大文字を調べる
2. Sの中に大文字があったら、その直前の文字がTに含まれるかを判定

sys.setrecursionlimit(10 ** 8)
INF = 10 ** 18

S = input()
T = input()

for i in range(1, len(S)):
    # S[i]==大文字 だったら
    if S[i].isupper():
        # 大文字の直前の文字が、Tに含まれるか判定
        before = S[i-1]
        exist = False
        for j in range(len(T)):
            if T[j] == before:
                exist = True
                break

        # 大文字の直前の文字が、Tに含まれなかったら、No
        if not exist:
            print("No")
            exit()

print("Yes")

C - Giant Domino

手こずった問題です。

まず、問題の意味を配列にして考えると、以下のようになります。
始点と終点は必須なので、その間のS[1] から S[N-2] のドミノを最小化したいわけです。

S[0] # 始点 start 
S[1] ... S[N-2] # middle = ここを最小で乗り切りたい
S[N-1] # 終点 end 

アルゴリズムは以下のように貪欲法で、解きました。
現在のドミノで倒せる限界の大きさのドミノを選んでいき、最終的に終点のドミノを倒せれば完了。というわけです。

前処理: middle(S[1] ... S[N-2]) をソートして、小さい順に並べる

* 始点が倒せる限界の大きさ(= S[0] * 2) のドミノを、middle から選ぶ
* ↑で選んだドミノを倒せる限界の大きさのドミノを、middle から選ぶ
* ↑で選んだドミノを倒せる限界の大きさのドミノを、middle から選ぶ
* ...くりかえし

選んだドミノで、終点のドミノを倒せれば終了。

# 各テストケースを調べる
T = int(input())
for i in range(T):
    N = int(input())
    S = list(map(int, input().split()))
    start = S[0]
    end = S[-1]

    # 始点のドミノで終点のドミノを倒せるなら、終了
    if start * 2 >= end:
        print(2)
        continue

    # N=2のときの判定
    if N == 2:
        if start * 2 >= end:
            print(2)
        else:
            print(-1)
        continue

    # 中間部分の配列を作り、ソートする
    middle = S[1:-1]
    middle.sort()

    current_value = start # 現在のドミノのサイズ
    answers = [] # middleの中で、採用したドミノの数
    for i in range(len(middle)):

        # 終点のドミノを倒せれば、終了
        if current_value * 2 >= middle[i] and middle[i] * 2 >= end:
            answers.append(middle[i])
            print(len(answers) + 2)
            break

        if i + 1 < len(middle):
            # i+1のドミノを倒せる → 倒せる限界はまだ先にある
            if current_value * 2 >= middle[i] and current_value * 2 >= middle[i + 1]:
                continue

            # i+1のドミノを倒せる → 倒せる限界はここ
            if current_value * 2 >= middle[i] and current_value * 2 < middle[i + 1]:
                # この位置のドミノを採用する
                answers.append(middle[i])
                current_value = middle[i]
                continue
        
        # middleの最後まで来たが、endを倒せなかった
        print(-1)
        break