AGC029

考察

AtCoder

AtCoder Grand Contest 29の参加記録。

A

xoxooox のようにオセロの並びが与えられるので, 隣合うox を xo にする操作が最大何回行えるか求める.

oooox の場合, xooooとなるまでに4回操作できる.
ooooxx の場合, まず右から二つ目のxを↑の様に動かしてからxoooo + xとみるとそれぞれのxに対する操作は独立.
なので各xの左側にあるoの数の和を求めればいい.

解答

fn main() {
    let mut ans = 0;
    let s = read_one::<String>().chars().collect::<Vec<char>>();
    let mut cnt = 0;
    for i in 0..s.len() {
        if s[i] == 'B' { cnt += 1; }
        if s[i] == 'W' { ans += cnt; }
    }
    println!("{}", ans);
 
}

上の解答はWAになります()
Rustの数値リテラルにおける型推論のデフォルトはi32のため, s.len() < O(10^5)の制約ではオーバーフローしうる.

5分で解答してWA食らって正直全く分からなかった.これに気付くまで25分.
流石に初歩過ぎるので反省.

B

3 11 14 5 13 のように数列が与えられる. この中から和が2^kの形になるようにペアをつくるとき, 最大いくつ作れるか.

↑の例だと, ペアは(3, 5), (3, 13), (5, 11) の3通り考えられる. 複数回使うことは出来ないので, 2部グラフの最大マッチングか? n <= 2 * 10^5からできる候補なら計算量O(NM)でも間に合うのか? などと考えていた(無事TLE).

まずソートして, 各a_iに対しそれより大きい最小の2^kを求める.
2^k - a_iが数列の中に存在するかどうかbinary search等で求めてペアの候補とする.

ペアの候補は, 大きいものから順に選択していけば最大となる.

解答

fn main() {
    let n = read_one::<usize>();
    let mut an = read::<usize>();
    an.sort();
 
    let mut graph = Vec::new();
    let mut bn = an.clone();
 
    for i in 0..n {
        let x = bn.binary_search(&an[i]).unwrap();
        // 自身がペア対象にならないように一旦
        bn.remove(x);
 
        let mut ceil = 2;
        while ceil <= an[i] {
            ceil *= 2;
        }
 
        match bn.binary_search(&(ceil - an[i])) {
            Ok(n) => { graph.push((i, n)); },
            _ => {}
        }
        // 自身を戻す
        bn.insert(x, an[i]);
    }

    /* 最大マッチングWA
    let n = graph.len();
    let mut dinitz = Dinitz::new(n * 2 + 2);
    for (a, b) in graph {
        dinitz.add_edge(a, b, 1);
        dinitz.add_edge(b, a, 1);
    }
    println!("{:?}", dinitz.max_flow(n * 2, n * 2 + 1));
    */
}

所感

Aのミスで800位くらい落ちてて草も生えない.
Bは2部マッチングを勉強したあとだったのでそれに引っ張られた.
精進の量がたりてないので300~500埋めをやろう.

Commits

2021-01-30 22:18:1735b550aecopy md
commit 35b550ae83af4efaeadf33471c8ca8a32c1079c8
Author: koka &&gt;
Date:   Sat Jan 30 22:18:17 2021 +0900

  copy md

diff --git a/_posts/2018-12-15-agc029.md b/_posts/2018-12-15-agc029.md
new file mode 100644
index 0000000..1b81973
--- /dev/null
+++ b/_posts/2018-12-15-agc029.md
@@ -0,0 +1,102 @@
+---
+title: AGC029
+date: 2018-12-15
+categories:
+- Competitive Programming
+tags:
+  - AtCoder
+description: 考察
+---
+
+
+AtCoder Grand Contest 29の参加記録。
+
+# [A](https://beta.atcoder.jp/contests/agc029/tasks/agc029_a)
+
+`xoxooox` のようにオセロの並びが与えられるので, 隣合う`ox` を `xo` にする操作が最大何回行えるか求める.  
+
+`oooox` の場合, `xoooo`となるまでに4回操作できる.  
+`ooooxx` の場合, まず右から二つ目の`x`を↑の様に動かしてから`xoooo + x`とみるとそれぞれの`x`に対する操作は独立.  
+なので各`x`の左側にある`o`の数の和を求めればいい.
+
+## 解答
+
+\```rust
+fn main() {
+    let mut ans = 0;
+    let s = read_one::&lt;String&gt;().chars().collect::&lt;Vec&lt;char&gt;&gt;();
+    let mut cnt = 0;
+    for i in 0..s.len() {
+        if s[i] == 'B' { cnt += 1; }
+        if s[i] == 'W' { ans += cnt; }
+    }
+    println!("{}", ans);
+ 
+}
+\```
+
+上の解答はWAになります()  
+Rustの数値リテラルにおける型推論のデフォルトは`i32`のため, `s.len() &lt; O(10^5)`の制約ではオーバーフローしうる.
+
+5分で解答してWA食らって正直全く分からなかった.これに気付くまで25分.  
+流石に初歩過ぎるので反省.
+
+
+# [B](https://beta.atcoder.jp/contests/agc029/tasks/agc029_b)
+
+`3 11 14 5 13` のように数列が与えられる. この中から和が`2^k`の形になるようにペアをつくるとき, 最大いくつ作れるか.  
+
+↑の例だと, ペアは`(3, 5), (3, 13), (5, 11)` の3通り考えられる. 複数回使うことは出来ないので, 2部グラフの最大マッチングか? `n &lt;= 2 * 10^5`からできる候補なら計算量`O(NM)`でも間に合うのか? などと考えていた(無事TLE).
+
+まずソートして, 各`a_i`に対しそれより大きい最小の`2^k`を求める.  
+`2^k - a_i`が数列の中に存在するかどうかbinary search等で求めてペアの候補とする.  
+
+
+ペアの候補は, 大きいものから順に選択していけば最大となる.
+
+
+## 解答
+
+\```rust
+fn main() {
+    let n = read_one::&lt;usize&gt;();
+    let mut an = read::&lt;usize&gt;();
+    an.sort();
+ 
+    let mut graph = Vec::new();
+    let mut bn = an.clone();
+ 
+    for i in 0..n {
+        let x = bn.binary_search(&an[i]).unwrap();
+        // 自身がペア対象にならないように一旦
+        bn.remove(x);
+ 
+        let mut ceil = 2;
+        while ceil &lt;= an[i] {
+            ceil *= 2;
+        }
+ 
+        match bn.binary_search(&(ceil - an[i])) {
+            Ok(n) =&gt; { graph.push((i, n)); },
+            _ =&gt; {}
+        }
+        // 自身を戻す
+        bn.insert(x, an[i]);
+    }
+
+    /* 最大マッチングWA
+    let n = graph.len();
+    let mut dinitz = Dinitz::new(n * 2 + 2);
+    for (a, b) in graph {
+        dinitz.add_edge(a, b, 1);
+        dinitz.add_edge(b, a, 1);
+    }
+    println!("{:?}", dinitz.max_flow(n * 2, n * 2 + 1));
+    */
+}
+\```
+
+## 所感
+Aのミスで800位くらい落ちてて草も生えない.  
+Bは2部マッチングを勉強したあとだったのでそれに引っ張られた.  
+精進の量がたりてないので300~500埋めをやろう.