AtCoder ABC 463 振り返り (PythonでABCD問題)

ABC463を振り返ります

昨年の10月以来、ひさびさにAtCoderコンテスト参加してみた。
過去問を数問解いてみたら、Pythonの書き方をすっかり忘れており、for文を書くのすら危うい状態...。

そんな状態なので、もちろんUnrated参加です。
そうしたら意外と解けてしまって、今回はABCDまで4問解答でした。

A - 16:9

単純に割り算しているだけなので誤差が出そうなんですが、正解だったのでヨシ👈️🐱

X, Y = map(int,input().split())
if X / 16 == Y / 9:
    print("Yes")
else:
    print("No")

B - Train Reservation

新幹線の席を予約する問題。

N, X = input().split()
N = int(N)

# ABCDE席 を [0-4]に変換
seat = ["A", "B", "C", "D", "E"]
seat_index = seat.index(X)

# 空席があるかチェック
exist = False
for i in range(N):
    S = input()

    if S[seat_index] == "o":
        exist = True
        break

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

C - Tallest at the Moment

時刻Lに退出した人の身長がH...という配列が与えられている。
ということは、配列を後ろから求めれば、その時点での最高身長の人をあらかじめ求めることができる(max_list)。

from collections import defaultdict
import bisect

N = int(input())
L_LIST = []
H_LIST = []
for i in range(N):
    H, L = map(int,input().split())
    L_LIST.append(L)
    H_LIST.append(H)
Q = int(input())
T = list(map(int, input().split()))

# 時刻L時点での最大値の値を求めておく
# 身長リスト(H_LIST)を後ろから探索している
max_list = []
current_max = 0
for i in range(N-1, -1, -1):
    current_max = max(H_LIST[i], current_max)
    max_list.append(current_max)
max_list.reverse()

# Queryを処理
# 時刻t 時点での最高身長をprintする
for i in range(len(T)):
    t = T[i]
    index = bisect.bisect_right(L_LIST, t)
    print(max_list[index])

D - Maximize the Gap

• 「答え x が成立するか」を判定する関数を作る
• 答えのMax値を2分探索で求める

という考えで求めました。

判定関数は、布の右端でソートした配列を作っておくと便利です。

N, K = map(int,input().split())
LR = []
RL = [] 
max_r = 0
for i in range(N):
    L, R = map(int,input().split())
    LR.append([L,R])
    RL.append([R,L])
    max_r = max(R, max_r)

RL.sort() # 布の右端のX座標でソート

# 値 score が成立するか判定する関数
def canComplete(score):
    # 最初の一枚目
    num = 1
    index = 0
    max_r = RL[0][0] 

    while num <= K or index < len(RL):
        exist = False
        # 次の布を探す
        for i in range(index, len(RL)):
            rl = RL[i]
            right = rl[0]
            left = rl[1]

            # 条件を満たす布があったので、座標を更新
            if left >= max_r + score:
                max_r = right
                num += 1
                index = i
                exist = True
                break

        if exist == False:
            break

    if num >= K:
        return True
    else:
        return False

# 答え x が成立する最大値を2分探索でさがす
left = 0
right = max_r
mid = (left + right) // 2
while right - left > 1:
    mid = (left + right) // 2
    if canComplete(mid):
        left = mid
    else:
        right = mid

if left == 0:
    print(-1)
else:
    print(left)