ABC334の記録

はじめに

最近競技プログラミングに取り組んでいるので、解いた問題や参加したコンテストの記録を残す。
ABCについてはA～Cまで解ききりたい。当面は茶を目指す感じで。
というわけでABC334の記録。

ユニークビジョンプログラミングコンテスト2023 クリスマス (AtCoder Beginner Contest 334)
https://atcoder.jp/contests/abc334
成績：Aのみ1完(100)

A

数値の大小比較で分岐する。

A

b, g = map(int, input().split())
if b>g:
    print("Bat")
else:
    print("Glove")

なお、公式解説によると三項演算子というものがあってそれが便利らしい。

A'

b, g = map(int, input().split())
print("Bat" if b > g else "Glove");

B

植木算。RとLの間の距離をMで割って、RにもLにも木があったら+1すればいいと思った。

B

import math
a, m, l, r = map(int, input().split())
num = math.ceil((r-l)/m)
if (l-a)%m == 0 and  (r-a)%m == 0: #lにもrにもに木があるならnum+=1
    num += 1
print(num)

どっこいこれが8WA。
いろいろ試しているとそもそもL, Rの取り方次第で割り算の結果を切り上げる方法と結果が食い違うパターンがあることが分かった。単なる考察不足。
※$(A, M, L, R) = (1, 3, 2, 15)$など。範囲内に入る木の本数が変わらないように範囲をできるだけ広くなるようにとると間違えやすいらしい。

というわけで解説などを見てちゃんと考え直す。
結局公式解説が一番ピンときやすくて、
「R以下で一番東にある木の番号」から「Lより小さくて一番東にある木の番号」を引けば良いことになる。
別の言い方をするなら「区間内で一番東にある木の番号」から「区間の西側範囲外のうち一番東にある木の番号」を引く。
これはRをMで割った商からLをMで割った商を引くことで求まるが、Lに木があった場合はその木は範囲内にあるので1足すと良い。

B'

#全体の座標を-aすることで、Mの倍数の座標にツリーが立っている状態にできる。
a, m, l, r = map(int, input().split())
l += -a
r += -a
ans = r//m - l//m
if l%m==0:
    ans +=1
print(ans)

C

正しい組み合わせが残っている靴下はそれを組み合わせると奇妙さ0なのでそうすべき。よって、$A_1, A_2,…A_K$を組み合わせて奇妙さが最小になるようにする。
Kが偶数の場合は隣り合った2つずつを組み合わせていけばよいが、Kが奇数の場合は余らせる一つを決めないといけない。
ここで$A_i$と$A_{i+1}$の階差$B_i$を考えると、$B$の最大値が$B_j$のとき$A_j$か$A_{j+1}$のいずれかを余らせるのが最適。
$B_j+B_{j+1}$と$B_{j-1}+B_j$を比較し、前者が大きければ$A_j$、後者が大きければ$A_{j+1}$を消す。

C

n, k = map(int, input().split())
A = list(map(int, input().split()))
if k%2 == 1:
    B = []
    for j in range(k-1):
        B.append(A[j+1]-A[j])
    maxB = B.index(max(B))
    if B[maxB-1] + B[maxB] > B[maxB]+B[maxB+1]:
        A.remove(A[maxB])
    else:
        A.remove(A[maxB+1])
    k -=1
score = 0
for i in range(0,k,2):
    score += abs(A[i]-A[i+1])
print(score)

と、ここまで考えて時間切れになった。
後々考えると間違ってはないと気がするけど汎用性がない方針ですね。
$k = 1, 3$のときに成立しなくなったりするし。

公式解説だとKが奇数の場合は余らせる靴下を決めて全探索。それぞれの奇妙さの合計は累積和を使って求めるとある。この累積和は最初からと末尾からの両方を求めておいて、余らせるところで参照する累積和を切り替えればいい。
また、余らせる靴下はAのうち$A_1, A_3, A_5,…$に限られるはず（$A_2, A_4$…を余らせると$A_1, A_3, A_5,…$を余らせたときに比べて奇妙さが余計に生じる）。

C'

n, k = map(int, input().split())
A = list(map(int, input().split()))
if k%2 == 1:
    sumh = [0]*(k+1)
    sumt = [0]*(k+1)
    for i in range(1, k):
        sumh[i] = sumh[i-1]
        if i%2 == 1:
            sumh[i] += A[i]-A[i-1]
    for i in range(k-1, -1, -1):
        sumt[i] = sumt[i+1]
        if i%2 == 1:
            sumt[i] += A[i+1]-A[i]
    ans = float('inf')
    for i in range(0, k+1, 2):
        ans = min(ans, sumh[i]+sumt[i])
    print(ans)
    exit()
else:
    score = 0
    for i in range(0,k,2):
        score += abs(A[i]-A[i+1])
    print(score)

もうちょっと効率良いやり方がある気もするが……

D

D問題が簡単らしいのでやってみる。

D

import bisect
n, q = map(int, input().split())
R = list(map(int, input().split()))
sortR = sorted(R)
sumR = [sortR[0]]
for i in range(1, len(R)):
    sumR.append(sumR[i-1]+sortR[i])

for _ in range(q):
    query = int(input())
    print(bisect.bisect_right(sumR,query))

本当に簡単だった。累積和取って二分探索するだけ。

B問題とC問題が難しい回だったみたいですね。本当にrateを上げたいなら解く問題の選び方も重要かも。