ABC330 勉強メモ
先日開催された、AtCoder Beginner Contest 330の勉強メモです。
問題への言及がありますので、今後解く予定の方はご注意ください。
使用言語はPython・提出はPyPy3です。
公式解説
A Counting Passes
解法
for文が一番簡単です。内包表記でもよいです。
filter関数は遅かったのでおすすめしません。
実行時間テスト
$N=10^8$としたときの各解法の実行時間を、AtCoderのコードテストで測定しました。
forループ << 内包表記(sum) = filter(forループ) < 内包表記(リスト再作成) = filter(リスト再作成)
となったので、学習コストを踏まえても、filter関数は忘れてよいでしょう。(終)
#forループ
def solve_for_loop(N,L,A): #600ms
cnt = 0
for i in range(N):
if A[i] >= L: cnt += 1
return cnt
#内包表記
def solve_comprehension_sum(N,L,A): #1160ms
return sum(1 if A[i]>=L else 0 for i in range(N))
def solve_comprehension_makelist(N,L,A): #2300ms
B = [A[i] for i in range(N) if A[i]>=L]
return len(B)
#filter関数
def solve_filter_for(N,L,A): #1310ms
cnt = 0
for num in filter(lambda x: x>=L, A): cnt += 1
return cnt
def solve_filter_makelist(N,L,A): #2940ms
return len(list(filter(lambda x: x>=L, A)))
テストケース作成
from time import perf_counter as pf
from random import randint
#ランダムテスト Nの制約のみ壊す
def random_test(N):
testcase = [randint(0,1000) for _ in range(N)]
L = randint(0,1000)
S=pf()
solve_for_loop(N,L,testcase)
print(pf()-S); S=pf()
solve_comprehension_sum(N,L,testcase)
print(pf()-S); S=pf()
solve_comprehension_makelist(N,L,testcase)
print(pf()-S); S=pf()
solve_filter_for(N,L,testcase)
print(pf()-S); S=pf()
solve_filter_makelist(N,L,testcase)
print(pf()-S)
#ランダムテストを実行
random_test(10**8)
B Minimize Abs 1
解法
制約が$L,R,A_i \leq 10^9$なので、B問題なのに全探索ができません。
なので$|X_i - A_i| \leq |Y-A_i|$ の数式を解くのがこの問題のすべてです。
$A_i$は定数なので、ひとまず$|Y-A_i|$の最小値を探すことにしましょう。
$|Y-A_i|=0$ にできるとき
$L \leq Y \leq R$ の範囲内に$A_i$があるとき、$Y=A_i$とすれば$|Y-A_i|=0$にできます。
すなわち $L \leq A_i \leq R$のとき、$|Y-A_i|$の最小値は0になります。
すると$X_i$の条件は $L \leq X_i \leq R$, $|X_i - A_i| = 0$となるので、$X_i = A_i$が適しています。
$|Y-A_i|=0$ にできないとき
「できるとき」の逆なので、条件は$A_i < L$ または $R<A_i$のときです。
どちらにせよ $L \leq X_i,Y \leq R$の範囲なら、$|X_i-A_i|$も$|Y-A_i|$も絶対値が外しやすい形になります。
- $A_i < L$の場合
絶対値を外すと $X_i - A_i \leq min(Y-A_i)$ となります。
$X_i - A_i$が最小となるようにしたいので、$X_i = L$とします。 - $R<A_i$の場合
絶対値を外すと $A_i - X_i \leq min(A_i-Y)$ となります。
$A_i - X_i$が最小になるようにしたいので、$X_i = R$とします。
C Minimize Abs 2
解法
公式解説で知ったのですが、これは半径$√D$の円に最も近い格子点を探す問題です。
ですが$min(|x^2 + y^2 - D|)$からここまで読み取るのは難しいので、他の解き方を考えます。
全探索
公式解説の通りです。
forループでxを全探索します。xを固定したときの「いい感じ」のyを調べます。
xが大きいとき($x^2-D \geq 0$)は$|x^2 + y^2 -D| = x^2+y^2-D$と開けますが、問題はxが小さいとき($x^2-D<0$)です。
この場合、$y^2$を$|x^2-D| = D-x^2(>0)$に近づけたいので、yは$√(D-x^2)$の近傍の非負整数を調べることにしましょう。
なお、ルートを開くときは小数点が発生します。誤差の原因となるので、近傍は広めに探索したほうが安全です。
計算量は$O(√D)$です。
三分探索
xを固定すると、$f(y) = |x^2 + y^2 - D|$は下に凸な関数となります。
$y_L < y_R < √(D-x^2)$ だと$f(y_L)>f(y_R)$
$√(D-x^2)<y_L<y_R$だと$f(y_L)<f(y_R)$ です。
このように極値を挟んで狭義単調増加/減少が入れ替わる関数の場合、三分探索が使えます。
(広義単調増加/減少だと三分探索は使えないようです。→問題例)
forループでxを全探索し、$f(y)$の最小値は三分探索で絞りましょう。
三分探索は二分探索に似ていますが、実装は大きく異なるので注意しましょう。
実装部分はgonyariyaさんの解説を参考にさせて頂きました。
計算量は$O(√DlogD)$です。
def f(x,y): return abs(x**2 + y**2 - D)
ans = 10**18
for x in range(int(D**0.5)+2):
Lt,Rt = 0,int(D**0.5)+2
while abs(Lt-Rt)>2:
mid_Lt, mid_Rt = (Lt * 2 + Rt)//3, (Lt + Rt * 2)//3
#悪い方を更新し、良い方を残す
if f(x,mid_Lt) > f(x,mid_Rt): Lt,Rt = mid_Lt, Rt
else: Lt,Rt = Lt, mid_Rt
for y in [Lt, (Lt+Rt)//2, Rt]: #最終候補は3択
ans = min(ans, f(x,y))
尺取法
半径√Dの円の近傍の格子点を探す問題と考え、xを全探索します。
xを昇順探索すると、$y= √(D - x^2)$が$0 \leq x \leq √D$の範囲で単調減少となることから、yの近傍点に対する尺取法ができます。
計算量は$O(√D)$です。本問ではここまで必要ありませんが、円周の尺取法はたまに出題されます。問題例(青diff)
提出例(全解法)
D Counting Ls
解法
1個目のoを固定すると、あとふたつの縦のo、横のoの選び方だけ自由度があります。
事前に縦横のoの個数を数え上げておけば、各マスごとに$O(1)$、合計$O(N^2)$で解けます。
コンテスト中は二次元累積和のライブラリを使って楽しました。提出例
二次元累積和の原理はimosさんのブログが最も詳しいです。
E Mex and Update
解法
長さNの数列のmax(mex)はNなので、Nより大きい数字は無視できます。
mexの計算は一点更新セグメント木があると楽に行えます。
S: N以下の非負整数のうち、Aに含まれない要素の集合
とすると、mexの取得はmin(S)で可能です。
集合の最小値が取得できればなんでもよいので、たとえばheapqやsortedcontainersでも解けます。
ただし、sortedcontainersのうちSortedSetは動作が不安定なので避けましょう。
提出例(全解法)
各解法の概要・実行時間の比較
SegTree(615ms) < heapq(671ms) << SortedList(1120ms) < SortedSet(TLE2 + 1107ms)
1. SegTree
一点更新・区間min取得のセグメント木を使います。
・A[i]の追加: S.update(A[i], +INF)
・A[i]の削除: S.update(A[i], A[i])
・mexの取得: S.fold(0,N+1)
2. heapq
優先度付きキューを2個使用することでも最小値の取得ができます。
注意点として、heapqからの削除は$O(N)$かかってしまうので、削除待ち用のキューを別に用意する必要があります。
S = [i for i in range(N+1)]
T = [] #削除待ちキュー
#Sの最小値を正しい値に修正
while S and T and S[0] == T[0]:
heapq.heappop(S); heapq.heappop(T)
3. SortedList
先日の言語アップデートでsortedcontainersが追加されました。
このうち、順序付き多重集合のSortedListを用いることでも解けます。
・A[i]の追加: S.discard(A[i])
・A[i]の削除: S.add(A[i])
・mexの取得: S[0]
4. SortedSet
順序付き集合であるSortedSetでも解ける･･･はずなのですが、なぜかTLEします。
一応SortedSetの宣言を遅らせることでACできますが、実行時間が不安定なのでとても困ります。
可能な限り使わないようにしましょう。
#TLE
S = SortedSet([i for i in range(N+1)]) #最初にSortedSetを宣言
for num in A:
D[num] += 1
if D[num] == 1: S.discard(num) #要素の削除 O(logN)くらい
#AC
S = set([i for i in range(N+1)]) #まずset型で宣言
for num in A:
D[num] += 1
if D[num] == 1: S.discard(num) #要素の削除 O(1)
S = SortedSet(S) #はじめてSortedSetを宣言
TLE版のSortedSetはhack_01とhack_02で落ちています。
この凶悪テストケースの中身が知りたいです。(終)
F Minimize Bounding Square
解法
点の移動はx軸方向とy軸方向に独立に考えてよいです。
すなわち、正方形の幅をWとして「すべての点のx座標を幅W以内に収める」かつ「すべての点のy座標を幅W以内に収める」ことを目標にします。
事前に点のx座標・y座標を取得し、軸ごとにソートしておきましょう。
解の二分探索
「正方形の幅を固定したとき、K回以内にすべての点を正方形内に収められるか？」という判定問題を解きます。
X軸・Y軸ごとに、「幅Wの区間内にすべての点を収める最小操作回数は？」を高速で計算できれば、これの和を合計操作回数として計上できます。
これを解きましょう。以下、各軸ごとの一次元問題を考えます。
考察すると、「区間を左右に動かすと、区間外の左右にある点の差分によって操作回数が増減する」性質に気づきます。
区間外の左のほうが点が少ないようなら区間を右に動かすたびに操作回数が減り、左のほうが多ければ操作回数が増えます。
なので、区間ごとの操作回数は下に凸になります。
あるいは「操作回数の変曲点は、区間の端に点がある場所だ」とも分かります。なので、端に点がある区間のみを調べれば、どれかは最小操作回数を満たします。
これらの性質を利用して判定を行います。
区間端が候補となる性質を使う場合は尺取法、下に凸の性質を使う場合は三分探索を行います。
どちらにしても、「点iより左側/右側の点を点iまで動かすための最小操作回数」を尺取法で調べておきましょう。
#L_Lt[i]: 区間の左端をL[i]に合わせるために必要な操作回数
#L_Rt[i]: 区間の右端を(同上)
def count_ope(L):
global N
L_Lt, L_Rt = [[0]*(N+1) for _ in range(2)]
for i in range(1,N):
L_Lt[i] = L_Lt[i-1] + (L[i]-L[i-1]) * i #距離差と、はみ出た個数の積を加算
for i in range(N-2,-1,-1):
L_Rt[i] = L_Rt[i+1] + (L[i+1]-L[i]) * (N-i-1)
return L_Lt, L_Rt
尺取法
区間左端、次に区間右端を固定し2N回の検索を行います。
固定していない側は「区間外のうち、最も区間に近い点」までの操作回数が分かっているので、そこからの差分を加算すればよいです。
尺取法の計算が$O(N)$、解の二分探索回数が$O(logM)$(M: 最大座標値)なので、最初の座標のソートと合算して$O(N(logM + logN))$ です。
ans = 10**18
L.append(0) #便宜上、末尾になにかつけておく
#区間の左側を固定したときの最小操作回数
Rt = 0
for Lt in range(N):
while Rt <N and L[Lt]+W >= L[Rt]: Rt += 1 #L[Lt]+W < L[Rt]を満たすまで
ans = min(ans, L_Lt[Lt] + L_Rt[Rt] + (L[Rt] - (L[Lt]+W)) * (N-Rt))
三分探索
区間の両端を定めたときの操作回数は、前処理を行うと二分探索で計算できます。
#区間左端をpoint, 右端をpoint + W とする
def check(point, L, L_Lt, L_Rt, W):
global N
cnt = 0
#区間左端よりも左側に出ている点をpointに移動させる
i = bisect_right(L, point)-1 #point以左にある最近傍点
if i>=0: cnt += L_Lt[i] + (point - L[i]) * (i+1)
#区間右端よりも右側に出ている点をpoint + Wに移動させる
i = bisect_left(L, point + W) #point以右にある最近傍点
if i <N: cnt += L_Rt[i] + (L[i]-(point+W)) * (N-i)
return cnt
区間幅を固定したとき、操作回数は区間位置に対して下に凸な関数となります。
なので、たとえば区間左端の座標値をキーに三分探索を行うことで最小操作回数が分かります。
三分探索が$O(logM)$(M: 最大座標値), 三分探索の判定部分に$O(logN)$, 解の二分探索に$O(logM)$なので、最初の座標のソートと合算して$O(NlogN + (logM)^2logN)$です。
提出例(解の二分探索・判定部分の三分探索) (237ms)
貪欲法
境界部分に張り付いている点が少ないほうを動かす貪欲法でも解けます。
ただし実装激重です。詳しくは提出例をご確認ください。
提出例: list(324ms), deque(564ms)
実装の注意点
現在の矩形が長方形なら正方形になるように、正方形なら両端を同時に縮めることで解けます。
現在の矩形の両端の位置、境界に張り付いて移動する点の個数(あるいはindex)を保持して、尺取法のように動かしましょう。
処理法にはlistとdequeを使う方法がありますが、listによる尺取法を強く推奨します。
dequeだと区間の境界が残り1区間だけになったときにバグる可能性があります。具体的にはこのケースが危ないです。(終)
2 1
0 0
1 0
おわりに
おわりです。
いろんなじっそうがあるとにぎやかでいいなとおもいました。