さすがにこれが解けないのは反省。
D - Choose Your Characters
問題
N種類のキャラクターがいるゲームで対戦を行う。N種類のキャラクターには1からNまでの番号がついている。またそれらの間には相性という概念が定まっており、「キャラクターaはキャラクターbに対して有利(キャラクターbはキャラクターaに対して不利)」という関係がM個存在する。
このゲームでA君とB君が対戦する。A君にどうしても勝ちたいB君は、以下のような条件で特訓を行うことにした。
- 特訓するキャラクターは[L, R] (閉区間)の範囲の番号のキャラクターに集中して行う。少なければ少ないほどよい。
- A君がどのキャラクターaを選んでも、[L, R]内のキャラクターbであって、a != bでbはaに対して不利ではないようなbが存在する
- 少なくとも五分五分以上にはなるようなbが存在する
条件を満たす閉区間[L, R]は存在するか? 存在する場合は長さがもっとも短いものを、複数存在する場合はLが最小のものを出力せよ。存在しない場合は-1を出力せよ。
制約
- 2 <= N <= 100000
- 1 <= M <= 200000
- 同じ条件は1回まで出現する
- 正反対の条件は出現しない
解法
二分探索を使うと、区間長R - L + 1を固定した時に、条件を満たすようなLが存在するかどうかをO(N)時間程度で判定できればよいことがわかる。
これは可能で、以下のようにすれば良い。
まず、各キャラクターbについて、B君がbを選んだ時にA君に選んでほしくないキャラクター(bが不利になるキャラクターとb自身)を管理する。
以降B君が選ぶ区間[L, R]を伸び縮みさせることを考える。[L, R]の中のキャラクターに対するA君に選んで欲しくないキャラクターが、何回数えられるかを管理する。明らかに、選んで欲しくないキャラクターとしてR - L + 1回登場するキャラクターが存在する場合、今見ている範囲[L, R]ではそのキャラクターには対応できない。
長さlenで条件を満たす区間が存在するかどうか確かめる場合には、[0, len - 1] -> [0, len] -> [1, len] -> [1, len + 1] -> ... のように、右端と左端を交互に右にずらしていけばよい。あるステップで区間に入ったり区間から除外される頂点をvとすれば、そのステップの計算量はO(vを選んだ時にA君に選んでほしくないキャラクターの個数)である。その合計はO(M)なので、長さlenでOKかどうかの判定もO(M)時間である。
2分探索なので全体の計算量はO(M log N)。
登場する典型
- 尺取り法
- セグメント木を使いたいが計算速度が間に合わないときは、尺取り法やスライド最小値でなんとかできないかを考える
- 頻度表
- setを使いたくなったら頻度表でなんとかできないかを考える
実装上の注意点
- 尺取りなので気をつける
- 2分探索時とLを求める時の2回行うので、関数にした方がよい
- 頻度表なのでデータの整合性に気をつける
- 変換用の関数を作るとよい
提出: #4543465 (Rust)
fn op(len: usize, a: &mut [usize], count: &mut usize, idx: usize, newval: usize) { if a[idx] == len { *count -= 1; } a[idx] = newval; if newval == len { *count += 1; } } fn sweep(g: &[Vec<usize>], len: usize) -> Option<usize> { let n = g.len(); // sweep let mut freq = vec![0; n]; let mut cnt = 0; for i in 0..len { for &v in &g[i] { let val = freq[v] + 1; op(len, &mut freq, &mut cnt, v, val); } } for i in 0..n - len + 1 { if cnt == 0 { return Some(i); } // progress if i < n - len { for &v in &g[i + len] { let val = freq[v] + 1; op(len, &mut freq, &mut cnt, v, val); } for &v in &g[i] { let val = freq[v] - 1; op(len, &mut freq, &mut cnt, v, val); } } } None } fn solve() { let out = std::io::stdout(); let mut out = BufWriter::new(out.lock()); macro_rules! puts { ($($format:tt)*) => (write!(out,$($format)*).unwrap()); } input! { n: usize, m: usize, ab: [(usize1, usize1); m], } let mut g = vec![vec![]; n]; for &(a, b) in &ab { g[b].push(a); } for i in 0..n { g[i].push(i); } let mut pass = n + 1; let mut fail = 1; while pass - fail > 1 { let mid = (pass + fail) / 2; if sweep(&g, mid).is_some() { pass = mid; } else { fail = mid; } } // len = pass if pass > n { puts!("-1\n"); return; } let l = sweep(&g, pass).unwrap(); puts!("{} {}\n", l + 1, l + pass); }
まとめ
本番は「セグ木に平衡2分探索木を乗せて、毎回O(N log^2 N)時間かけて判定すればいいから全体ではO(N log^3 N)！w」みたいなことを考えて途方にくれていたが、セグ木も平衡2分探索木も自然により良い方法が存在したので、考えるべきだった。
