競技プログラミングAtCoderのレベルアップのため、競プロ典型問題をPythonで解いていきます。
時間対効果を最大にするために以下のスキームで行います。
①問題を見る②10分だけ自力で考える③解説をみる④解説を見ながら、周辺知識を補完して、自力でコードを書く⑤問題を解く⑥他の方のコードを見て参考にして学習する⑦ブログにまとめる
001 – Yokan Party（★4）
キーワード：「二分探索」、「分割可否の判定」
自分のコード（AC後）
from sys import stdin
input = stdin.readline
# 入力
N, L = map(int, input().split())
K = int(input())
A = [0]+list(map(int, input().split()))+[L]
# Yokanを長さmin_lenでK+1等分できるか判定
def ck_yokan(min_len):
sep_length = 0
cnt = 0
for i in range(1, N+2):
sep_length += A[i]-A[i-1]
if sep_length >= min_len:
cnt += 1
if cnt >= K+1:
return True
else:
sep_length = 0
return False
# 二分探索でK+1等分できる最大のスコアを探索
def bs(min_score, max_score):
if max_score <= min_score:
return min_score
else:
mid_score = min_score + (max_score - min_score) // 2 + 1
if ck_yokan(mid_score):
return bs(mid_score, max_score)
else:
return bs(min_score, mid_score-1)
print(bs(1,L))[ポイント]
・二分探索で効率的に答えを探索する
・等分可能かどうかについては、関数で独立させるとシンプル
・Yokanの分割長さのリストの扱いで苦慮した（結局0とLを前後に追加した。。。）
見直し後の解答
from sys import stdin
input = stdin.readline
# 入力
N, L = map(int, input().split())
K = int(input())
A = [0] + list(map(int, input().split())) + [L]
# 差分をあらかじめ計算しておく
D = [A[i+1] - A[i] for i in range(N+1)]
# Yokanを長さmin_lenでK+1等分できるか判定
def ck_yokan(min_len):
sep_length = 0
cnt = 0
for i in range(N+1):
sep_length += D[i]
if sep_length >= min_len:
cnt += 1
if cnt >= K+1:
return True
else:
sep_length = 0
return False
# 二分探索でK+1等分できる最大のスコアを探索
max_score = L+1 # NGとなる値
min_score = -1 # OKとなる値より小さな値
while max_score - min_score > 1: # 差が1以下になったら終了
mid_score = min_score + (max_score - min_score) // 2
if ck_yokan(mid_score):
min_score = mid_score # OK確認済みのラインを上げる
else:
max_score = mid_score # NG確認済みのラインを下げる
print(min_score)[修正点]
・差分は最初に計算しておく方が計算時間が短くて済む
・再帰関数を使うとややこしいのでwhile文でシンプルに書く
・NGとラインとOKのラインを意識して、この二つが並んだところで計算終了とする
コメント