commit 35b550ae83af4efaeadf33471c8ca8a32c1079c8
Author: koka <koka.code@gmail.com>
Date:   Sat Jan 30 22:18:17 2021 +0900

  copy md

diff --git a/_posts/2018-12-22-caddi2018b.md b/_posts/2018-12-22-caddi2018b.md
new file mode 100644
index 0000000..2225289
--- /dev/null
+++ b/_posts/2018-12-22-caddi2018b.md
@@ -0,0 +1,191 @@
+---
+title: CADDi2018
+date: 2018-12-15
+categories:
+- Competitive Programming
+tags:
+  - AtCoder
+description: 考察
+---
+
+CADDi 2018 for Beginners の参加記録。
+
+## [A - 12/22](https://caddi2018b.contest.atcoder.jp/tasks/caddi2018b_a)
+
+与えられる数字の中に`2`がいくつあるか.
+数字を一桁毎に走査していくのはしんどいので, 文字の配列として扱うのが吉.
+
+### 解答
+
+\```rust
+fn main() {
+    let n = read_one::<String>().chars().collect::<Vec<char>>();
+    let mut cnt = 0;
+    for c in n {
+        if c == '2' { cnt += 1; }
+    }
+    println!("{}", cnt);
+}
+\```
+
+## [B - AtCoder Alloy](https://caddi2018b.contest.atcoder.jp/tasks/caddi2018b_b)
+
+N枚の板のうち`H * W`の大きさが切り出せるものは何枚あるか.  
+今回は`H * W`を`W * H`にしてはいけないことに注意したくらい.
+
+### 解答
+
+\```rust
+fn main() {
+    let (n, h, w) = {
+        let i = read::<usize>();
+        (i[0], i[1], i[2])
+    };
+    let mut ans = 0;
+    for _ in 0..n {
+        let (h_i, w_i) = {
+            let i = read::<usize>();
+            (i[0], i[1])
+        };
+
+        if h_i >= h && w_i >= w { ans += 1; }
+    }
+
+    println!("{}", ans);
+}
+\```
+
+
+## [C - Product and GCD](https://caddi2018b.contest.atcoder.jp/tasks/caddi2018_a)
+
+n個の整数からなる配列があって,その要素数と積が与えられる`(N, P)`.  
+各要素の最大公約数として考えられるもののうち, 最も大きいものを求める.
+
+配列`an`が`x`を公約数にもつ ←→ `an`の各要素は`x`を約数に持っている  
+なので, `an`を素因数分解して, `n`個以上ある素因数の積が答えになる.
+
+### 解答
+
+\```rust
+fn main() {
+    let (n, p) = {
+        let i = read::<u64>();
+        (i[0], i[1])
+    };
+
+    let mut hm = HashMap::new();
+    let mut x = p;
+    // 素因数分解してhashmapにいれる
+    while let Some(f) = divide(x) {
+        x /= f;
+        *hm.entry(f).or_insert(0) += 1;
+    }
+    *hm.entry(x).or_insert(0) += 1;
+
+    let mut ans: u64 = 1;
+
+    for (k, v) in hm.iter() {
+        // 因数kが2n個以上あったときにk^xする(2敗)
+        if v >= &n {
+            ans *= k.pow((v / n) as u32);
+        }
+    }
+
+    println!("{}", ans);
+}
+
+
+fn divide(n: u64) -> Option<u64> {
+    for i in 2..(n as f64).sqrt().ceil() as u64 + 2 {
+        if n % i == 0 {
+            return Some(i);
+        }
+    } 
+    return None;
+}
+\```
+
+## [D - Harlequin](https://caddi2018b.contest.atcoder.jp/tasks/caddi2018_b)
+
+格子の交点を横線または点でなぞって、最後の点をなぞった人の勝ち.
+お互いに最善手をとる前提で実験してみる.  
+やった実験は
+- `2 * 2`
+- ↑を横にのばす
+- ↑を縦にのばす
+- ↑を合成したやつ
+の4パターン.
+
+\```
+o o
+o o
+\```
+のように`2*2`の格子があった場合, 先手の取り得る点は1か2.
+
+\```
+o o
+x o
+\```
+
+のように一つとった場合, 後手は同列の点を一つとればよい.
+
+\```
+x o
+x o
+\```
+
+また, 2つとった場合 後手はそのまま2つ取って勝ち.
+
+
+次に`2 * k`のように引き伸ばした場合.
+
+\```
+o o o ..... o o
+o o o ..... o o
+\```
+
+これについても`2 * 2`の場合と同様で, 先手のとった数だけ後手もとれば負けることはない(最終的に`2 * 2`に帰着するので).  
+
+では`k * 2`の場合はどうか.  
+
+\```
+o o
+o o
+...
+o o
+\```
+
+これまでの実験から, `2 * k`の形に持ち込んだら勝敗がきまることがわかったので, そうしない立ち回りを行なえば良い.
+`k`が偶数の場合, 後手の勝ち. `k`が奇数の場合, 先手の勝ち.
+
+最後に一般形を考える.
+元の問題では`1 4 5 2 4`のようにランダムに並んでるけどソートしてしまっても問題ない.
+すると`n * (偶数)`の形をつくるかどうか, になるので,初期配置の各列の偶奇を判断すればよい.
+
+
+### 解答
+
+\```rust
+fn main() {
+    let n = read_one::<usize>();
+    let mut an = Vec::new();
+    for _ in 0..n {
+        an.push(read_one::<usize>());
+    }
+
+    if an.iter().all(|a| a % 2 == 0) {
+        println!("second");
+    } else {
+        println!("first");
+    }
+}
+\```
+
+### 所感
+
+一番よかったとき(!)
+![](./img/caddi2018b.png)
+(結果は31位)
+
+Dの考察をスムーズに行なえたのに, Cでの2WAがもったいない.
+デバッグを如何にやるかが課題っぽい.