【경쟁 프로 전형적인 90문】001의 해설(python)

개요

경쟁 프로 전형 90문 의 해설 기사입니다.
해설의 이미지를 봐도 모르는 (이해력이 부족한) 것이 많이 있었으므로, 나중에 다시 풀었을 때에 확인할 수 있도록 정리했습니다.

※순차적으로, 모든 문제의 해설 기사를 들어갈 예정입니다.

이슈001-요칸파티

문제 개요

길이 L과 같은 감귤을 K+1개로 나누었을 때의 피스 중에서 가장 작은 피스의 최대값을 구한다.
단, 절단하는 장소는, N개소의 어느 하나(A1~AN)로 지정되어 있다.

제약

1 <= K <= N <= 100000 \\

0 < A1 < A2 < ・・・ < AN < L <= 10^9

해결 방법

모든 절단 방법을 구한 다음 계산하는 방법은
N개의 틈으로부터 K개 선택하는 패턴, 즉 nCk대로를 조사하게 되어, NG.

그래서 이번에는
1. X(cm) 이상의 길이로 감귤을 잘라낼 수 있는지를 판정한다
2. 1~L까지로 상기 1의 판정을 통과하는 것의 최대값을 구한다
같은 흐름으로 구현한다.

1에 관해서, 귤의 끝에서 순서대로 틈을 보고, X(cm) 이상이 되면
요칸의 피스를 +1(개)하는 형태로 실장할 수 있다.
이 때의 계산량은 O(N).

2에 관해서, 1~L에 ​​대해, 이분 탐색을 이용함으로써,
판정을 만족하는 최대치를 구한다. (이분 탐색에 대해서는 여기)
이 때의 계산량은 O(logL).

판정의 계산량이 N이고, 판정할 때의 계산량이 logL이기 때문에,
합계로 O(NlogL). 이것은 약 10의 6승이 되기 때문에, 충분히 시간에 맞는다.



인용 소스 : 경쟁 프로 전형 90문 Github

구현

answer.py

# 入力の受け取り
N, L = map(int, input().split())
K = int(input())

# 先頭に0、末尾にLを追加することで切れ目の差を求めやすくする
A = [0]+list(map(int, input().split()))
A.append(L)

# 判定するメソッド。cntで切れ目の差の合計がx以上になった時の個数を計測。lで切れ目の差を加算していく。（x以上になったらlはリセット）
def check(x):
  cnt = 0
  l = 0
  for i in range(N+1):
    l += A[i+1] - A[i]
    if l >= x:
      cnt += 1
      l = 0
  return cnt >= K+1

# 二分探索のテンプレ
ng = L
ok = -1

while ng - ok > 1:
  mid = (ok + ng) // 2
  if check(mid):
    ok = mid
  else:
    ng = mid

# 二分探索により、okにcheckがtrueになる、最大値が入っているので、okを出力
print(ok)

마지막으로

문제의 해설을 읽어도 다른 사람의 코드를 봐도 확실히 모르는 분
힘에 조금이라도 될 수 있으면 다행입니다.
(자신은 처음, 전혀 몰랐습니다.)

여기까지 읽어 주셔서 감사합니다.