ABC126

考察

AtCoder

TODO

AtCoder Beginners Contest 126の参加記録. 今回から6問100分になった.

D-Even Relation

NN頂点の木があり、頂点uiu_iとviv_i間の長さがwiw_iのとき、距離が偶数である頂点を全て同色で塗り分ける.

偶数の場合を0(白), 奇数の場合を1(黒)とする. 与えられるグラフは木なので閉路が存在しない。したがって一点を0と決めてしまって、そこからの距離の偶奇が等しければ0, 異なれば1のように塗り分ければいい. グラフの探索部分はDFSでできる.

解答

fn main() {
    let n = read_one::<usize>();
    let mut edge = vec![Vec::new(); n];

    for _ in 0..n - 1 {
        let (u, v, w) = {
            let i = read::<usize>();
            (i[0] - 1, i[1] - 1, i[2])
        };
        edge[u].push((v, w));
        edge[v].push((u, w));
    }

    let mut color = vec![2; n];
    let mut cost = vec![0; n];
    let mut q = VecDeque::new();
    q.push_back(0);
    color[0] = 0;
    while let Some(u) = q.pop_front() {
        for &(v, w) in edge[u].iter() {
            if color[v] != 2 { continue; }
            cost[v] = cost[u] + w;
            if (cost[v] - cost[u]) % 2 == 0 { color[v] = color[u]; }
            else { color[v] = 1 - color[u]; }
            q.push_front(v);
        }
    }

    for i in 0..n { println!("{}", color[i]); }
}

E-1 or 2

AX+BY+ZiA_X + B_Y + Z_i % 2 == 0を満たす組がMM組与えられる. AX,BYA_X, B_Yにはそれぞれ1または2が書かれている. このとき数字が不確定なカードは何枚か.

場合分けをしてみる. ZiZ_iが偶数の場合、AX+BYA_X + B_Yは偶数となるのでAXA_XとBYB_Yの偶奇は等しい. ZiZ_iが奇数の場合、AX+BYA_X + B_Yは奇数となるのでAXA_XとBYB_Yの偶奇は異なる.

つまりZiZ_iの偶奇に依らずAXA_XがわかればBYB_Yの数字がわかる. よって各組をグルーピングしてあげて、最終的なグループ数を求めればよい.

解答

fn main() {
    let (n, m) = {
        let i = read::<usize>();
        (i[0], i[1])
    };

    let mut uf = UnionFind::new(n);
    for _ in 0..m {
        let (x, y, _) = {
            let i = read::<usize>();
            (i[0] - 1, i[1] - 1, i[2])
        };
        uf.unite(x, y)
    }

    let mut hs = HashSet::new();
    for i in 0..n { hs.insert(uf.find(i)); }
    println!("{}", hs.len());
}

F-XOR Matching

  • aaは00以上2M2^M未満の整数をちょうど２つずつ含む
  • ai=aja_i = a_jを満たすi,j(i<j)i, j (i < j)について, aia_i xor ai+1a_{i+1} xor ... xor aj=Ka_j = K を満たす長さ2M+12^{M+1}の数列aaを構築する.

解答

所感

Dでpush_front()とするところをpush_back()としてしまい(DFSのつもりがBFS), それに気づけなかった。

Eは最初矛盾があるケースを考えてしまい結局誤読のまま.
Fはこれから考える.
最近この時間帯に眠くなってしまうので次回は仮眠してから参加する。

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/2019-05-20-abc126.md b/_posts/2019-05-20-abc126.md
new file mode 100644
index 0000000..5be04f4
--- /dev/null
+++ b/_posts/2019-05-20-abc126.md
@@ -0,0 +1,106 @@
+---
+title: ABC126
+date: 2019-05-20
+categories:
+- Competitive Programming
+tags:
+  - AtCoder
+  - TODO
+description: 考察
+---
+AtCoder Beginners Contest 126の参加記録.
+今回から6問100分になった.
+
+## [D-Even Relation](https://atcoder.jp/contests/abc126/tasks/abc126_d)
+$N$頂点の木があり、頂点$u_i$と$v_i$間の長さが$w_i$のとき、距離が偶数である頂点を全て同色で塗り分ける.
+
+偶数の場合を`0`(白), 奇数の場合を`1`(黒)とする.
+与えられるグラフは木なので閉路が存在しない。したがって一点を`0`と決めてしまって、そこからの距離の偶奇が等しければ`0`, 異なれば`1`のように塗り分ければいい.
+グラフの探索部分はDFSでできる.
+
+### 解答
+
+\```rust
+fn main() {
+    let n = read_one::&lt;usize&gt;();
+    let mut edge = vec![Vec::new(); n];
+
+    for _ in 0..n - 1 {
+        let (u, v, w) = {
+            let i = read::&lt;usize&gt;();
+            (i[0] - 1, i[1] - 1, i[2])
+        };
+        edge[u].push((v, w));
+        edge[v].push((u, w));
+    }
+
+    let mut color = vec![2; n];
+    let mut cost = vec![0; n];
+    let mut q = VecDeque::new();
+    q.push_back(0);
+    color[0] = 0;
+    while let Some(u) = q.pop_front() {
+        for &(v, w) in edge[u].iter() {
+            if color[v] != 2 { continue; }
+            cost[v] = cost[u] + w;
+            if (cost[v] - cost[u]) % 2 == 0 { color[v] = color[u]; }
+            else { color[v] = 1 - color[u]; }
+            q.push_front(v);
+        }
+    }
+
+    for i in 0..n { println!("{}", color[i]); }
+}
+\```
+
+## [E-1 or 2](https://atcoder.jp/contests/abc126/tasks/abc126_e)
+$A_X + B_Y + Z_i % 2 == 0$を満たす組が$M$組与えられる.
+$A_X, B_Y$にはそれぞれ`1`または`2`が書かれている.
+このとき数字が不確定なカードは何枚か.
+
+場合分けをしてみる.
+$Z_i$が偶数の場合、$A_X + B_Y$は偶数となるので$A_X$と$B_Y$の偶奇は等しい.
+$Z_i$が奇数の場合、$A_X + B_Y$は奇数となるので$A_X$と$B_Y$の偶奇は異なる.
+
+つまり$Z_i$の偶奇に依らず$A_X$がわかれば$B_Y$の数字がわかる.
+よって各組をグルーピングしてあげて、最終的なグループ数を求めればよい.
+
+### 解答
+
+\```rust
+fn main() {
+    let (n, m) = {
+        let i = read::&lt;usize&gt;();
+        (i[0], i[1])
+    };
+
+    let mut uf = UnionFind::new(n);
+    for _ in 0..m {
+        let (x, y, _) = {
+            let i = read::&lt;usize&gt;();
+            (i[0] - 1, i[1] - 1, i[2])
+        };
+        uf.unite(x, y)
+    }
+
+    let mut hs = HashSet::new();
+    for i in 0..n { hs.insert(uf.find(i)); }
+    println!("{}", hs.len());
+}
+\```
+
+## [F-XOR Matching](https://atcoder.jp/contests/abc126/tasks/abc126_f)
+- $a$は$0$以上$2^M$未満の整数をちょうど２つずつ含む
+- $a_i = a_j$を満たす$i, j (i &lt; j)$について, $a_i$ xor $a_{i+1}$ xor ... xor $a_j = K$
+を満たす長さ$2^{M+1}$の数列$a$を構築する.
+
+### 解答
+\```rust
+\```
+
+## 所感
+Dで`push_front()`とするところを`push_back()`としてしまい(DFSのつもりがBFS), それに気づけなかった。
+
+Eは最初矛盾があるケースを考えてしまい結局誤読のまま.  
+Fはこれから考える.  
+最近この時間帯に眠くなってしまうので次回は仮眠してから参加する。