E問題まではほぼ完璧に近いムーブができていたんだけどなあ。
D - Ears
問題
長さLの数列a[i]が与えられる。以下の規則で長さLの数列b[i]を作る時、\sum abs(a[i] - b[i])を最小化し、その最小値を求めよ。
- b[i]の要素をすべて0で初期化する。0からLまでの番号がついた点がある。初期地点と終了地点を適当に決め、任意回以下の操作を行う。
- 現在点Xにいるとき、X-1またはX+1のどちらかに移動する。(存在しない点には移動できない。)この移動でi-1とiの間を通った時、b[i] += 1を行う。
解法
bとしてあり得る数列はどのようなものだろうか? これは(0の連続)-(2以上の偶数の連続)-(奇数の連続)-(2以上の偶数の連続)-(0の連続)の形に限られることが示せる。
- bをつくるときのパスの始点をs、終点をtとすると、パスにtからsへの一本道を足すと閉路になる。閉路において各区間を通る回数は偶数なので、もともとのパスにおいてはs-t間だけが奇数、それ以外が0より大きい偶数だったことになる。
- 逆に、c = (0の連続)-(2以上の偶数の連続)-(奇数の連続)-(2以上の偶数の連続)-(0の連続)として、b = cとするためのパスが必ず存在することを示す。点iと点i + 1の間にc[i]本の辺を設けた無向グラフを考える。Eulerの定理より、このグラフは連結で、次数が奇数の点が0個または2個であるため、オイラーパスが存在する。そのオイラーパスによってできるbはcと一致する。
この形の数列を全探索してaとの差分を求めることは不可能である。以下の観察を利用する:
- 0以外の整数をb[i]とする場合、a[i]から2以上離れた値を使う意味はない。
これにより、現在のbが上の5状態のどれにあるかを状態として持つDPができる。状態数は5で遷移の個数は3である。
登場する典型
- 形を決め全探索
- オートマトンとして見てDP
実装上の注意点
- 遷移がそこそこ複雑なので、遷移をあらかじめテーブルにして、ロジックとデータを分離する
提出: Submission #4211296 - Yahoo Programming Contest 2019 (Rust)
fn solve() { let out = std::io::stdout(); let mut out = BufWriter::new(out.lock()); macro_rules! puts { ($($format:tt)*) => (write!(out,$($format)*).unwrap()); } input! { l: usize, a: [i64; l], } const INF: i64 = 1 << 58; // 0: not started // 1: started, odd not started // 2: odd started // 3: started, odd ended // 4: ended let mut dp = vec![[INF; 5]; l + 1]; dp[0][0] = 0; for i in 0..l { let mut cost = vec![0; 3]; cost[0] = a[i]; if a[i] == 0 { cost[1] = 1; cost[2] = 2; } else { let r = a[i] % 2; cost[1] = 1 - r; cost[2] = r; } // 5: not allowed let trans = [ [0, 2, 1], [4, 2, 1], [4, 2, 3], [4, 5, 3], [4, 5, 5], ]; for j in 0..5 { for k in 0..3 { let to = trans[j][k]; if to >= 5 { continue; } dp[i + 1][to] = min(dp[i + 1][to], dp[i][j] + cost[k]); } } } let mi: i64 = dp[l].iter().min().cloned().unwrap(); puts!("{}\n", mi); }
まとめ
企業コンらしい非自明考察 + 強実装の問題という印象。解けたら誇っていいと思います。
