ABC 305 備忘録

概要

　今回は、ABC305（2023年6月10日21:00~22:40）の実装、ポイント、および自分の実装について述べていこうと思う。

A問題

ポイント

• 高橋くんの位置を5で割った余りが3以上かどうかで場合分け
• 2以下ならば、スタート地点に近い方で3以上ならばゴール地点に近い方の給水所

自分の実装

ABC_305_A.py

N = int(input())

if N%5 <= 2:
    print(N - N%5)
else:
    print(N + 5 - N%5)

B問題

ポイント

• 各アルファベットと座標が対応するように、ASCII文字コードによる変換を行う

自分の実装

ABC_305_B.py

coordinates = [0, 3, 4, 8, 9, 14, 23]

p, q = map(str, input().split())

p_coords = ord(p) - 65
q_coords = ord(q) - 65

print(abs(coordinates[p_coords] - coordinates[q_coords]))

C問題

ポイント

• 食べられたクッキーがあるのは長方形の周および内部の範囲
• '.', '#' であることを全探索し、当該座標自体が'.'でありかつ、調べている座標の周囲4マスのうち２つ以上が'#'である座標が答え

自分の実装

ABC_305_C.py

H, W = map(int, input().split())

S = [['.' for i in range(W+2)]]
for i in range(H):
    S_line = ['.'] + list(input()) + ['.']
    S.append(S_line)
S.append(['.' for i in range(W+2)])
grid_x = [-1, 0, 1, 0]
grid_y = [0, -1, 0, 1]

for i in range(1, H+1):
    for j in range(1, W+1):
        count_cookies = 0
        for k in range(4):
            x = i + grid_x[k]
            y = j + grid_y[k]
            if S[x][y] == '#' and S[i][j] == '.':
                count_cookies += 1
            if count_cookies >= 2:
                print(i, j)
                exit()

D問題

ポイント

• 各クエリの開始・終了時間が睡眠記録のどの記録の間に位置しているかを2分探索で調べる
• 記録間の睡眠時間をいちいち計算 or sum で計算するのではなく、累積和で各区間の時間を計算（起きている区間は0となるように注意）
• 累積和同士の差、および開始。終了時間による差分を引いた上で答えを出力

自分の実装

ABC_305_D.py

from bisect import bisect_left

N = int(input())

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

sleep = [0]*N

# 就寝・起床時間時点で何時間寝たかの累積和
for i in range(1, N):
    if i % 2 == 0:
        sleep[i] = sleep[i-1] + A[i] - A[i-1]
    else:
        sleep[i] = sleep[i-1]

Q = int(input())

# 各クエリの処理
for i in range(Q):
    l, r = map(int, input().split())
    r_index = bisect_left(A, r)
    l_index = bisect_left(A, l)
    minute = 0
    minus = 0
    A_r, A_l = A[r_index], A[l_index]
    if A_r != r:
        r_index -= 1
    if A_l != l:
        l_index -= 1
    if l_index %2 == 1:
        minus += l - A[l_index]
    if r_index %2 == 1:
        minus -= r - A[r_index]
    minute = sleep[r_index] - sleep[l_index] - minus
    print(minute)

感想

　今回はC問題までは10分程度で解けたのはよかった。一方で、D問題で2分探索を使うことまでは考えられたが、累積和で睡眠時間を求めること、および開始・終了時間が時間軸の中で睡眠中なのか起床しているのかを場合分けするのに手間取り、時間内に解くことができなかった。全て頭の中で考えていたので、メモするなりしてもっと考えをまとめながらコーディングするべきだった。