https://atcoder.jp/contests/past202012-open/tasks/past202012_m
前提知識
解説
https://atcoder.jp/contests/past202012-open/submissions/22299599
複合的な問題。
しかも、二分探索+セグメントツリーではあるが、時間制限は2secなので無駄なコードを書くとすぐTLEする。
適度にモジュール化しながら、かつ、添え字管理に気を付けて実装を進めていこう。
二分探索
二分探索問題は二分探索に気が付くまでが第一関門となるが、いつもの「最小値の最大化」とも
とれる問題設定なので、とりあえず二分探索を考えてみると、とりあえずできることは分かる。
check(lim) := 切断後の棒の長さがlim以上である棒の切り方を達成できるか
これの境界線が答えになる。
check関数
判定問題をいかに解決しようか。
これは実はDPで解くことができる。
以下のようなyes/noのDP tableを構築する。
dp[i] := i番目までの棒をうまく切ることでlim以上L以下のまとまりに分割することができるか
dp[i]を更新する場合を考える。
i番目の棒からさかのぼってどこで切るかを考えると、ここもある程度の単調性を持っていることに気が付く。
例えば 1 2 3 4 5 という長さになっていて10～14の長さが作れる範囲は長さ5からスタートすると、
no yes yes no noのような [noグループ] [yesグループ] [noグループ]となる。
これだと単調性を持たないが、10以上ならきれいにyes/noに分かれるし、14以下ならきれいにyes/noに分かれる。
よって、それぞれの場合で二分探索を行うことでyesグループの始点と終点を割り出すことができる。
この過程で区間和が必要になるが、累積和を利用しよう。
始点と終点が分かれば、その範囲内でdp[x]=yesとなっているものがあれば、
そこで切ることでdp[i]=trueを達成できる。
このようなある範囲にyesのものがあるかという問題はBITで区間和をとることで高速に計算が行える。
後は最終的にdp[N]=1であれば、条件を満たす分割が可能になる。
余談
二分探索系は割と制約が厳しい（気を抜くとN2が通りがち）上に添え字管理が難しいので、
なるべくライブラリ化できる部分はしていくのがオススメ。
最初、累積和部分をBITでやっていたらTLEした。
これはメタテクニックだが、WAはなくTLEということは計算方法があっている可能性が高いので、
多少計算量の悪い方法でも解法チェックに投げてしまうというのがある。
（あえて書くと怒られそうだけれど）
int N; ll L; int A[201010]; //--------------------------------------------------------------------------------------------------- ll tot[201010]; ll getLen(int l, int r) { // [l, r) if (l >= r) return 0; ll res = tot[r - 1]; if (l) res -= tot[l - 1]; return res; } //--------------------------------------------------------------------------------------------------- bool check(ll lim) { BIT<int> dp(N + 1); dp.add(0, 1); rep(i, 0, N) { if (getLen(0, i + 1) < lim) continue; int okR = 0, ngR = i + 1; while (okR + 1 != ngR) { int md = (okR + ngR) / 2; if (lim <= getLen(md, i + 1)) okR = md; else ngR = md; } int ngL = -1, okL = okR + 1; while (ngL + 1 != okL) { int md = (ngL + okL) / 2; if (getLen(md, i + 1) <= L) okL = md; else ngL = md; } int sum = dp.get(okL, okR + 1); if (0 < sum) dp.add(i + 1, 1); } return 0 < dp.get(N, N + 1); } //--------------------------------------------------------------------------------------------------- void _main() { cin >> N >> L; rep(i, 0, N) cin >> A[i]; tot[0] = A[0]; rep(i, 1, N) tot[i] = tot[i - 1] + A[i]; ll ok = 0, ng = L + 1; while (ok + 1 != ng) { ll md = (ok + ng) / 2; if (check(md)) ok = md; else ng = md; } cout << ok << endl; }
