競プロ典型90問 自習1

スポンサーリンク
AtCoder
スポンサーリンク

競技プログラミング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のラインを意識して、この二つが並んだところで計算終了とする

コメント