知ってる前提の専門用語
計算量・計算次元/競技プログラミング/ソート/log
スタート
001 – Yokan Party（★4）
https://atcoder.jp/contests/typical90/tasks/typical90_a
の解説をします。
↑の解説記事も参考にしました。本記事では、カサニマロブログらしく、より初心者向きに書いたつもりです。
前提知識〜二分探索〜
前提
リストは昇順にソート済みとします。
概要
「７」を探すとしましょう。
探索の対象となるリストが
A = [1, 3, 5, 7, 9]
とします。
普通の探索では、Aの頭から１、３、５、７と探していきます。最悪の場合計算量はO(n)になります。
二分探索では、リストの中央にある５から探索を始めて、目標の７よりも５が小さいので、「まず５より大きい部分を切り取ります」。
すると [7, 9]が出てきます。リストの長さが偶数なので、中央は７か９どちらもでいいですが、あえて「要素数が偶数のときは大きいものを選ぶ」というルールだったとしましょう。
すると「９」を選択しますが、これは目標の７より大きいです。
よって[7, 9]の9より小さい部分を切り取ります。
すると[7]が残ります。
[7]は目標の７と一致するので探索終了。というわけです。
計算量（とそのイメージ）
計算量はリストの長さがnだったとして、O(log n)で済みます。
イメージは幅64cmのすだれを畳んで、幅を4cmにしたい時、端から4cmずつ畳んでいくよりも、中心を２つ折りにし32cmに、もう１回中心を折って16cmに、、、、と繰り返した方が畳む回数が少なくて済みますよね。
具体的には
端から折る作戦
4 = 64 – 4x
x = 17
中心を折る作戦
64 = 4 * 2x
log64 = log(4 * 2x) （底は２）
8 = 2+x
x = 6
です。やっぱ中心から追ったほうが早いですよね。（体育でバトミントンとかバレーボールのネットを片付ける時を思い出しますね。）
本編
問題文
左右の長さが L [cm] のようかんがあります。 N 個の切れ目が付けられており、左から i 番目の切れ目は左から Ai [cm] の位置にあります。
あなたは N 個の切れ目のうち K 個を選び、ようかんを K+1 個のピースに分割したいです。そこで、以下の値を スコア とします。
- K+1 個のピースのうち、最も短いものの長さ（cm 単位）
スコアが最大となるように分割する場合に得られるスコアを求めてください。
解説
競プロ勢の思考の流れ
- この問題は「〜の最小値をスコアとする。その最大値を求めてください」という形（問題理解）
- 「最小値を最大化してください」という問題では二分探索が有効であることが多い（経験・洞察）
- 「スコアを x 以上にすることは可能ですか？」という問題を解ければxを変えるだけで良い（発想）
よって、この判定問題は、次のように言い換えられます。
「切断されてできる K+1 個のようかんの長さをすべて x 以上とすることは可能ですか？」
（なんだか数学の文章題を解く感じに似てますね）
ソースコード
N, L = map(int, input().split())
K = int(input())
A = list(map(int, input().split()))
#後の計算のための準備
A.append(L)
A.insert(0, 0)
def check(mid):
cnt = 0
pre = 0
for i in range(1, N+2):
if A[i] - A[pre] >= mid: #ここのpreの設定の仕方が肝
cnt += 1 #「長さx以上」の羊羹の数
pre = i
if cnt >= K+1:
return True
else:
return False
left = 0
right = L
while right - left > 1: #O(n)
mid = (left + right) // 2 # O(n log n)
if check(mid):
left = mid
else:
right = mid
print(left)
その他筆者の素人発想
羊羹の長さ50cmが10等分されているとする。１つ5cm。これはめっちゃスコアが高い。（説明省略）
だから、5,4,3,2,1cmだけを考えれば良い。
みたいな感じでとりあえず自分の考えで実装してみました。計算時間オーバーになったので、改善していった過程を記事の最後におまけで書いてみました。
おまけ（読まなくていいよ^^）
最初のトライ
僕の間違い変遷を紹介してみます。初学者が「ああなんだ、みんなこんなもんなのか」となる可能性を期待して書いてみます。
羊羹の長さ50cmが10等分されているとする。１つ5cm。これはめっちゃスコアが高い。１０個に分ける方法でスコアが最高。（説明省略）
だから、5,4,3,2,1cmだけを考えれば良い。
↓
一般化すると、長さ/(切れ目+1) を小数点切り捨た数を１になるまでfor文を回したらなんかいける？
↓
あ〜、でもそれだけでは最高のスコアを出すことに直結してないな
↓
ま、とりあえず書いてみよ
その結果がこちら。
#ソースコード
N, L = map(int, input().split())
K = int(input())
A = list(map(int, input().split()))
max_value = round(L/(K+1))
for k in range(max_value): #１重ループ
norma = max_value - k
cut = 0
score =0
i = -1
while i < N-1:#２重ループ
i += 1
if i == 0:
if norma <= A[i] and norma <= L - A[i]:#等分されていたらここで終了。
cut += 1
score = min(A[i], L-A[i])
else:#等分でないほとんどの場合
for j in range(1, N):#３重ループ
if A[i+j] >= norma and L - A[i+j] >= norma: #ノルマを超えたら切る
cut += 1
score = min(A[i+j], L-A[i+j])
i = i+j
break
else: # 2回目以降
if norma <= A[i]-A[i-1] and norma <= L - A[i] :#等分以上に大きければここで終了。
cut += 1
if A[i]-A[i-1] < score:
score = min(A[i]-A[i-1], L-A[i])
else:#等分でないほとんどの場合
for j in range(1, N-i):
if A[i+j]-A[i-1] >= norma and norma <= L - A[i+j] : #ノルマを超えたら切る
cut += 1
if A[i+j]-A[i-1] < score and norma < L - A[i+j]:
score = min(A[i+j]-A[i-1], L-A[i+j])
i = i+j
break
if cut >= K:
print(score)
break
競プロではよくあるのですが、計算の仕方自体はあってても、２重ループなどにより計算時間が大きすぎると「時間オーバー」となり、スコアがもらえません。
現在のやり方だと、一応３重ループが存在しているので、まぁ当然の結果ですね笑。
逆から考えてみた
長いものを切っていくのでなく、細切れになったものをくっつけたら行けるのかなとも思いました。
全部切断されている状態を考える→２分探索で見つかるやつは最小のやつ→最小を見つけて、最小の左右の小さい方と結合→これを繰り返す→羊羹が指定の数になる
を思いつきました。違うとはわかっているのですが、勉強のためにも書いてみました。
N, L = map(int, input().split())
K = int(input())
A = list(map(int, input().split()))
B = []
for i in range(N+1):
if i == 0:
B.append(A[i])
elif i >0 and i < N:
B.append(A[i] - A[i-1])
else:
B.append(L - A[-1])
for i in range(N): # 結合させて、N+1こをK+1個にする。O(n)
if N - i == K: # N個の切断が、K個の切断になったら終了。K+1のピースができている。
break
m = min(B)
m_index = B.index(m)
if m_index == 0: #先頭
m = B[0]+B[1]
del B[0]
del B[0]
B.insert(0, m)
elif m_index == len(B)-1: #末尾
m = B[-2]+B[-1]
del B[-1]
del B[-1]
B.append(m)
else: #中間
if B[m_index+1] < B[m_index-1]: # 右側が小さい場合
m = B[m_index]+B[m_index+1]
del B[m_index]
del B[m_index]
B.insert(m_index, m)
else: # 左側が小さい場合
m = B[m_index-1]+B[m_index]
del B[m_index-1]
del B[m_index-1]
B.insert(m_index-1, m) # O(n^2)
print(min(B))
このコードは、長さLの棒をN個の位置で切り、N+1個のブロックに分け、そこから羊羹を結合させていく、K+1個にしています。最小のピースを探し、それを隣接するピースと結合するというアプローチは「最終的な最小ピースの長さを最大化するとは限らない」ので不正解を出すことがあります。
また計算量はO(n^2)なのでもうちょいよくしたいですね。
使わんかったけど、調べたやつ
#pythonで降順にfor文使う方法
sample_list = [1, 2, 3, 4, 5]
for x in reversed(sample_list):
print(x)
# 5
# 4
# 3
# 2
# 1
コメント