日本レジストリサービス（JPRS）プログラミングコンテスト2024#2（AtCoder Beginner Contest 364）

rated

atcoder.jp

A - Glutton Takahashi

リンク：A - Glutton Takahashi (atcoder.jp)

概要：甘い料理を2連続食べるとギブアップします。すべての料理を食べきれるか判定してね。

"sweet"と"salty"の2種類が入力として与えられるので"sweet"が2連続で出現したときにギブアップします。

ここでは前回食べた料理をpreに記録し、今から食べる料理sと2つ続けて"sweet"が来たらギブアップしています。

（コンテスト中は食べられる料理の数を出力かと思って書いてた名残で変なことしてます）

#ABC364 A - Glutton Takahashi
N = int(input())
pre = input()
judge = True
if N <= 2:
    print('Yes')
    exit()
for _ in range(N-2):
    s = input()
    if pre == s == 'sweet':
        judge = False
        break
    pre = s
if judge:
    print('Yes')
else:
    print('No')   

提出リンク：A - Glutton Takahashi (atcoder.jp)

B - Grid Walk

リンク：B - Grid Walk (atcoder.jp)

概要：グリッド上を”LRUD"で与えられる指示の通り歩きます。最後の指示を終えた時の場所を教えてね

制約も厳しくないのでシミュレートします。

今いる位置をとして次にに進むことにします。

指示が"U"（1つ上）なら、"R"（1つ右）ならという風に次に進む向きを指示します。

進む先がグリッド外もしくは壁"#"ならその場にとどまるようにします。

進めるならをに更新します。

とが上下どちらか混乱しないように注意が必要です。

#ABC364 B - Grid Walk
H, W = map(int, input().split())
si, sj = map(int, input().split())
si -= 1
sj -= 1
C = [input() for _ in range(H)]
X = input()
for i in range(len(X)):
    dx = 0
    dy = 0
    if X[i] == 'L':
        dy -= 1
    elif X[i] == 'R':
        dy += 1
    elif X[i] == 'U':
        dx -= 1
    elif X[i] == 'D':
        dx += 1
    if si+dx < 0 or H-1 < si+dx or sj+dy < 0 or W-1 < sj+dy:
        continue
    if C[si+dx][sj+dy] == '.':
        si += dx
        sj += dy
print(si+1, sj+1)   

提出リンク：提出 #56020261 - 日本レジストリサービス（JPRS）プログラミングコンテスト2024#2（AtCoder Beginner Contest 364）

C - Minimum Glutton

リンク：C - Minimum Glutton (atcoder.jp)

概要：個の料理に甘さとしょっぱさが設定されています。甘さの合計がを超える、もしくはしょっぱさの合計がを超えるとギブアップします。料理を好きな順番で食べられる場合に食べる料理の数の最小値を出力してね。

甘さでギブアップする場合としょっぱさでギブアップする場合の2通りを考えて食べる料理の数を比較します。

甘さの配列としょっぱさの配列を大きい順にソートして順に食べ、どちらかが閾値を超えたときに食べた数を出力します。

#ABC364 C - Minimum Glutton
N, X, Y = map(int, input().split())
A = sorted(list(map(int, input().split())), reverse = True)
B = sorted(list(map(int, input().split())), reverse = True)
ama = 0
kara = 0
for i in range(N):
    ama += A[i]
    kara += B[i]
    if ama > X or kara > Y:
        break
print(i+1)   

提出リンク：提出 #56023754 - 日本レジストリサービス（JPRS）プログラミングコンテスト2024#2（AtCoder Beginner Contest 364）

D - K-th Nearest

リンク：D - K-th Nearest (atcoder.jp)

概要：配列に対してから番目に遠い点までの距離を回出力してね

点もクエリの数も多いので毎回全探索はできないので効率的な探索を考える必要があります。

探索、番目ということで答えで二分探索を行うとよさそうです。

以下の方針で進めます。

• 答えをと仮定する。からの間にあるの要素数を調べてに対する大小を比較する。
  • 以上となる最小の、以下となる最大のを二分探索で見つける。
• 条件を満たすなら答えに記録してを更新し次へ

44～45行目で探索の初期値としてとを設定していますが、のときは明らかに条件を満たさない、のときは明らかに条件を満たす、というところから決めています。

要素を探す二分探索の部分はPythonならbisectが使えると思います。

（私は自分で書いたものを使っていて、範囲外の返り値がヘタクソなので場合分けをしています。）

#ABC364 D - K-th Nearest
def lower(A, N): #超えない最大
    l = 0
    r = len(A)-1
    if A[r] <= N:
        return r
    if A[0] > N:
        return -1
    ans = 0
    while l+1 < r:
        mid = (l+r)//2
        if A[mid] <= N:
            ans = mid
            l = mid
        else:
            r = mid
    return ans
def upper(A, N): #超える最小
    l = 0
    r = len(A)-1
    if A[r] < N:
        return -1
    if A[0] >= N:
        return 0
    ans = r
    while l+1 < r:
        mid = (l+r)//2
        if A[mid] >= N:
            ans = mid
            r = mid
        else:
            l = mid
    return ans
N, Q = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
for _ in range(Q):
    b, k = map(int, input().split())
    if b < A[0]:
        print(A[k-1]-b)
    elif b > A[-1]:
        print(b-A[-k])
    else:
        l = -1
        r = 10**9
        ans = 10**9
        while l+1 < r:
            mid = (l+r)//2
            left = upper(A, b-mid)
            right = lower(A, b+mid)
            num = right-left+1
            if num >= k:
                ans = min(ans, mid)
                r = mid
            else:
                l = mid
        print(ans)   

提出リンク：提出 #56139183 - 日本レジストリサービス（JPRS）プログラミングコンテスト2024#2（AtCoder Beginner Contest 364）