Supershipの名畑です。先日、知り合いの一世代上の女性が「スラムダンクの映画が流行ってるんですよね。原作読んだことないけど行ってみようかな」という話をしていて、本当に人気なんだなと実感しました。
はじめに
競プロ典型 90問の過去問解答例シリーズです。
今回は1問目のYokan Partyです。難易度は★4なので緑diffの難易度でしょうか。
競プロ典型 90問についての説明や解答例の目次はこちらの記事をご覧ください
001 - Yokan Party（★4）
公式リンク
言語
- Python (3.8.2) / PyPy3 (7.3.0)
PyPy3 (7.3.0)だと100msec程度ですが、Python (3.8.2)でも500msecは切ります。
解答例
# 条件を満たすした分割が可能か判定する貪欲法の関数
def can_cut(req_length, req_cut, length_list):
# req_length:求められる長さ
# req_cut：求められる分割数
# length_list：切れ目毎の長さ
cut = 0 # 分割数
length = 0 # 最後に分割してからの長さ
for ix in range(0, len(length_list) - 1):
if length + length_list[ix] >= req_length and cut < req_cut: # 分割可能か判定
cut += 1
length = 0
else: # 今の切れ目では分割できない
length += length_list[ix]
length += length_list[-1] # 最後の切れ目以降の長さを加える
return cut == req_cut and length >= req_length
# 入力
N, L = map(int, input().split())
K = int(input())
A = list(map(int, input().split()))
# 処理しやすいようにAを切れ目毎の長さに変換しておく
A.append(L)
for i in range(len(A) - 1, 0, -1):
A[i] -= A[i - 1]
# 二分探索によって最大となるスコアを求める
score = 0
low = 1
high = L - 1
while True:
score = (low + high) // 2
if can_cut(score, K, A): # 分割できるためscore以上が最大値と確定する
if low == score:
break
low = score
else: # 分割できないためscore未満が最大値と確定する
if high == score:
break
high = score
Kの値もNの値も100000とそこまで大きくないですが、総当たりすると間に合わないため、二分探索を用いています。たとえば羊羹の長さが100であれば、解のとりうる最小値を1、解のとりうる最大値は99とした二分探索で処理できます。
そのスコアの取得が可能かどうか は貪欲法で求めています。長さのリストを先頭から順番に操作して分割可能かどうかを判定しています。解答例の関数 can_cut です。
宣伝
SupershipのQiita Organizationを合わせてご覧いただけますと嬉しいです。他のメンバーの記事も多数あります。
Supershipではプロダクト開発やサービス開発に関わる方を絶賛募集しております。
興味がある方はSupership株式会社 採用サイトよりご確認ください。