2022年6月11日開催のAtcoder Beginner Contest 255を、備忘的にギリ茶の私の回答を残しておきます。
コンテンツ一覧
A - You should output ARC, though this is ABC.
問題文
回答のアプローチ
タイトル通り今回はビギナーコンテスト(ABC)ですが、ARC（行列\(\ A \)のRow、Columnの値）を出力しようという問題。レギュラーコンテスト（ARC）の略称にちなんだ問題になってます。
アプローチも何もって感じですが、\(\ 2 \) 行\(\ 2 \) 列なので愚直に書いてしまいました。
R,C = map(int,input().split())
A=[[0]*2 for _ in range(2)]
A[0][0],A[0][1] = map(int,input().split())
A[1][0],A[1][1] = map(int,input().split())
print(A[R-1][C-1])B - Light It Up
問題文
回答のアプローチ
ぱっと見、私程度だとちょっとびっくりしちゃう問題です。B問題にしては難しいのでは？？
ややメタ的なアプローチですが、こういう場合は制約がヒントになったりします。制約がかなり大きな数字（\(\ 10^9 \) オーダーとか）の場合はちゃんとしたアルゴリズムを考えるべき問題だったりします。 しかし今回は制約見ると、\(\ N \) が\(\ 1000 \)以下なので、素朴な方法でやっていけば良い可能性が高いとわかります。
- 各ランプ係から各人への距離を求める。
- 各人に対して、ランプを照らされるための最小の距離を求める。
- 各人が照らされるための最小距離のうち、最も大きい値を出力する。
ちょっと考えると、意外と単純な問題に落ち着きそうだとわかります。
import math
N,K = map(int,input().split())
A=list(map(int,input().split()))
X,Y = [],[]
for _ in range(N):
x, y = map(int,input().split())
X.append(x)
Y.append(y)
A_L = [[0]*N for _ in range(K)]
M_L = [0]*N
for n in range(N):
temp = []
for k in range(K):
temp.append(math.sqrt((X[n]-X[A[k]-1]) **2 + (Y[n]-Y[A[k]-1])**2))
M_L[n] = min(temp)
print(max(M_L))C - ±1 Operation 1
問題文
回答へのアプローチ
\(\ X \) が、等差数列の範囲外にいる場合は、数列の境界（数列の最小値又は最大値）との差の絶対値を出せば良いです。
また等差が\(\ 0 \) つまり、値が初項のみの場合は、\(\ X \) と\(\ A \) の差の絶対値を出せば良いです。
これら\(\ 2 \) つの少し特殊な場合を除き、等差数列の範囲内に\(\ X \) がある場合を考えます。
ちょっとここから、考え方がスマートではないですが、大まかにはXを初項分ずらして、等差で割った余りを出力すれば良いと考えました。
しかし、ただ余りを出力するだけだと、例えば、\(\ 6 \) で割った余りが\(\ 1 \) の時は良いですが、\(\ 5 \) になってしまったときはこの問題の条件の最小値ではありません。
何故なら、その場合は余りの\(\ 5 \) を引いて\(\ 6 \) の倍数にするよりも、 \(\ 1 \) を追加して\(\ 6 \) の倍数にした方が良いからです。
なので、交差を\(\ 2 \) で割った値よりも小さい場合は余りを出力、そうじゃない場合は（交差 - 余り）を出力。としました。
X,A,D,N = map(int,input().split())
Min = min(A,A + D*(N-1))
Max = max(A,A + D*(N-1))
if X <= Min:
print(Min - X)
elif X >= Max:
print(X - Max)
else:
X_0 = abs(X - A)
if D == 0:
print(abs(X-A))
else:
R = X_0 % abs(D)
if R <= abs(D/2):
print(R)
else:
print(abs(R-abs(D)))D - ±1 Operation 2
問題文
回答へのアプローチ
問題名はC問題の続き感がありますが、制約もアプローチ方法も何もかも別問題と言っても良いでしょう。
素朴には、
N, Q = map(int,input().split())
A = list(map(int,input().split()))
X = []
for _ in range(Q):
X = int(input())
R = 0
for a in A:
R += abs(a- X)
print(R)ですが、\(\ N,Q \leq 2 \times 10^5 \) なので、TLEです。結局はこの素朴な考え方とほぼ同じなんですが、TLEにならぬように工夫が必要です。
前処置が肝心です。
まず\(\ A \) はソートしておきます。
その上で、降順と昇順の累積和の数列を用意して置きます。
あとは、ソート済みの\(\ A \) 内での\(\ X \) の位置を二分探索で見つけて、そこまでの累積和と\(\ X \)との差を求めるという感じです。
import bisect
N, Q = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
A_lw,A_hi = [0],[0]
lw,hi = 0,0
for a_lw,a_hi in zip(A,reversed(A)):
lw += a_lw
hi += a_hi
A_lw.append(lw)
A_hi.append(hi)
X = []
for _ in range(Q):
X = int(input())
a = bisect.bisect(A,X)
R = (a*X - A_lw[a]) + (A_hi[N-a] - (N-a)*X)
print(R)