AtCoder ABC474振り返り (PythonでABCD問題)

ABC474を振り返ります

今回はABCDまで4問解答でした。
Dまではスムーズで、E問題も解けそうな雰囲気はあったんですけど...力及ばずでした。

終了後は「4問解けたし、順位も22xxだし、これは高得点では...」と思ったんですが、順位が高いのは変則日程(日曜 13:10-開催)の影響で参加者が少ないせいでした。

とはいえ結構レーティングも上がったので、今後も頑張りたいところです。

A - Not X

素直に1から3のループを行い、X以外の数になったらprintします。

X = int(input())
for i in range(1, 4):
    if i != X:
        print(i)
        exit()

B - Exit Order

10人ずつ退場するので、そのグループ内であり得る座席番号の最小と最大を求めます。
退場した人が、範囲内かどうかをチェックすればokです。

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

group = 0
count = 0    
is_ok = True
for i in range(N):
    group = count // 10
    p = P[i]

    # グループ内の最小と最大を求める
    min_p = 10 * group + 1
    max_p = min_p + 9

    # グループ内の最小・最大の範囲内か？
    if min_p <= p <= max_p:
        count += 1
        continue
    else:
        is_ok = False
        break

print("Yes" if is_ok else "No")

C - Remove and Append

番号 x が、配列のindexではどこにいるか？ を求めておきます。

P = [2 4 3 1] なら a_index[2] = 0, a_index[4] = 1... というふうにする

「P から 値が a である要素を削除し、Pの末尾に追加する」
↓
a_index[a] = max(a_index) + 1 みたいにすれば、末尾に追加をしたことになります。

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

# 値 a が 配列Pのどこ(index)にあるか
a_index = [0] * (N + 1)
for i in range(N):
    a_index[P[i]] = i

# 現在の配列Pの最後尾の位置
max_index = N + 1

for i in range(Q):
    # 値aを最後尾に移動
    a = int(input())
    a_index[a] = max_index
    max_index += 1

# Q回の操作後、a_index をindex順に並び替えて復元する
index_value = []
for i in range(1, len(a_index)):
    index_value.append((a_index[i], i))

index_value.sort()
answers = []
for i in range(len(index_value)):
    index, value = index_value[i]
    answers.append(value)

print(*answers)

D - Outweigh

問題の条件をよく見ると、最低1個だけでも Ai > Bi の箇所があれば、Yesになることがわかります。

あとは、以下の条件に従って、W[i]を決めていけばokでした。

• A[i] > B[i] → 最大値の 10**18 を入れる
• A[i] == B[i] → 何でも良い
• A[i] < B[i] → 最小値の1を入れる

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

W = []

minus_diff = 0
plus_diff = 0
for i in range(N):
    if A[i] > B[i]:
        W.append(10**18) # 最大値の 10**18 を入れておく
        plus_diff += A[i] - B[i]
    if A[i] == B[i]:
        W.append(2)     # 何でも良いのでとりあえず2をいれる
    if A[i] < B[i]:
        W.append(1)     # 最小値の 1 にしておく
        minus_diff += B[i] - A[i]

if plus_diff > 0:
    print("Yes")
    print(*W)
else:
    print("No")