【競プロ典型 90 問】001 - Yokan Party

Arakaki Tokyo -

AtCoder始めました。

という訳で、米田氏が企画した「競プロ典型90問」を解いていきます。

ここでは私の試行錯誤やら解説の理解やら気づきやらをメモしていこうと思います。
競プロ初心者なのでどうか温かい目で見守ってください。

なお、本記事中のPythonコードはブラウザ上で実行可能です。
よろしければ遊んでいってください。

問題

kyopro_educational_90/001.jpg at main · E869120/kyopro_educational_90

001 - Yokan Party（★4）

やってみよう！

テストデータ・テスト関数定義　↓

# 縮小表示 test_data = [ { "in": [3, 34, 1, [8, 13, 26]], "out": 13 }, { "in": [7, 45, 2, [7, 11, 16, 20, 28, 34, 38]], "out": 12 }, { "in": [3, 100, 1, [28, 54, 81]], "out": 46 }, { "in": [3, 100, 2, [28, 54, 81]], "out": 26 }, { "in": [20, 1000, 4, [51, 69, 102, 127, 233, 295, 350, 388, 417, 466, 469, 523, 553, 587, 720, 739, 801, 855, 926, 954]], "out": 170 }, ] def test_all(f): for i, data in enumerate(test_data): exp = data["out"] ans = f(*data["in"]) result = "AC" if exp == ans else "WA" print(f"{i+1} {result}: expected: {exp}, output: {ans}")

下のmain0関数を完成させて「Run」ボタンをクリックしよう！

def main0(N, L, K, data): pass test_all(main0)

自由欄

try(1st.)

とりあえず何も参照せずにやってみます。
今の私は全探索以外の武器を持っていないので愚直に全探索です。

from itertools import combinations def main(N, L, K, data): mins = list() for comb in combinations(range(N), K): pieces = list() for i, s in enumerate(comb): if i == 0: pieces.append(data[s]) else: pieces.append(data[s] - data[comb[i-1]]) else: pieces.append(L - data[s]) mins.append(min(pieces)) return max(mins) test_all(main)

よっしゃ、ちょろいぜ！提出！！

結果(1st.)

やはり全探索では無理がある…

提出 #32287997 - 競プロ典型 90 問

解説

kyopro_educational_90/001.jpg at main · E869120/kyopro_educational_90

答えで二分探索とのこと。
そんな発想、微塵もなかった…

羊羹問題、完全に理解した。

try(2nd.)

def main(N, L, K, data): def is_exist(v): left = 0 cnt = 0 for l in data+[L]: target = l - left if target < v: continue left = l cnt += 1 if cnt > K: return True return False l = 0 r = L while r != l: mid = (r + l + 1) // 2 if is_exist(mid): l = mid else: r = mid - 1 return l test_all(main)

結果(2nd.)

無事AC

提出 #32313575 - 競プロ典型 90 問

推敲

ここで想定コードを見ながらもうちょっと考えてみます。

なんか、自分の二分探索のコードがスッキリしないなぁ…
と考えていたら、そのものズバリのご指摘が。

謎のJK(?)に的確なご助言賜り複雑な心境ですが、とりあえずめぐる式二分探索法に修正したのが以下。

def main(N, L, K, data): def is_exist(v): left = 0 cnt = 0 for l in data+[L]: target = l - left if target < v: continue left = l cnt += 1 if cnt > K: return True return False ok = 0 ng = L while abs(ok - ng) > 1: mid = (ok + ng) // 2 if is_exist(mid): ok = mid else: ng = mid # okは条件を満たす最大の値、 # ngは条件を満たさない最小の値 return ok test_all(main)

提出 #32319198 - 競プロ典型 90 問
(結果や実行時間はほぼ変わらず)

追記(2022/06/26)

最近、bisectモジュールの存在を知ったのですが、Python3.10からbisect内の各関数でkey引数を取ることができるようになりました。

上のmain関数を書き換えると以下のようになります。

import bisect def main(N, L, K, data): def is_exist(v): left = 0 cnt = 0 for l in data+[L]: target = l - left if target < v: continue left = l cnt += 1 if cnt > K: return True return False return L - bisect.bisect_left(range(L, -1, -1), True, key=is_exist) # ok = 0 # ng = L # while abs(ok - ng) > 1: # mid = (ok + ng) // 2 # if is_exist(mid): # ok = mid # else: # ng = mid # # okは条件を満たす最大の値、 # # ngは条件を満たさない最小の値 # return ok test_all(main)

う～ん、コードが短くなるのはいいとして、直感的には理解しづらいですかね。

取りうる範囲の中でTrueとFalseの境目を探すために「答えで二分探索」はそのままです。
内部的にはあくまでも大小関係を比較します。True > FalseはTrueなので、「ソート済み配列」にするためにrange(L, -1, -1)としています。

現状、AtCoderのPythonは3.8なので(参照)実戦で使うのはまだ先になりそうですが、知っていて損はないでしょう。

追記終わり

自由欄