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

  copy md

diff --git a/_posts/2018-10-06-abc112.md b/_posts/2018-10-06-abc112.md
new file mode 100644
index 0000000..44ab51b
--- /dev/null
+++ b/_posts/2018-10-06-abc112.md
@@ -0,0 +1,168 @@
+---
+title: ABC112
+date: 2018-10-06
+categories:
+- Competitive Programming
+tags:
+  - AtCoder
+description: 考察
+---
+AtCoder Beginners Contest 112の参加記録。
+
+
+## [A](https://beta.atcoder.jp/contests/abc112/tasks/abc112_a)
+
+入力`N`が1なら指定の文字列を出力, 2なら更に標準入力から数字を読み、計算結果を出力.
+
+インタラクティブに標準入力の分岐処理を行う問題はABCだと初めて?
+
+
+### 解答
+\```rust
+fn main() {
+    let n = read_one::<String>();
+
+    if n == "1" {
+        println!("Hello World");
+    } else {
+        let a = read_one::<usize>();
+        let b = read_one::<usize>();
+        println!("{}", a + b);
+    }
+}
+\```
+
+## [B](https://beta.atcoder.jp/contests/abc112/tasks/abc112_b)
+
+`(c_i, t_i)`のうち、`t_i <= T`を満たす最小の`c_i`を求める.
+存在しない場合には`TLE`を出力する。
+
+### 解答
+
+\```rust
+fn main() {
+    let (n, t) = {
+        let i = read::<usize>();
+        (i[0], i[1])
+    };
+
+    let mut ct = Vec::new();
+    for _ in 0..n {
+        let i = read::<usize>();
+        ct.push((i[0], i[1]));
+    }
+
+    let ans = ct.iter()
+        .filter(|x| x.1 <= t)
+        .map(|x| x.0)
+        .min();
+
+    match ans {
+        Some(x) => println!("{}", x),
+        None => println!("TLE"),
+    }
+}
+\```
+
+## [C](https://beta.atcoder.jp/contests/abc112/tasks/abc112_c)
+
+座標`(x_i, y_i)`と高度`h_i`及び高度の計算式が与えられ、それを満たす中心座標及びそれの高度を求める.
+
+制約が`x < 10^2, y < 10^2, N < 10 ^ 2`なので全探索でも`10^8`なので通る.
+`x, y`及び`n`を固定すれば`h = max(H - (X - c_x).abs() - (Y - c_y).abs(), 0)`から`H`は定まるが、最初`h_i`が`0`になりうるケースを考慮せずにやってWA.
+そこで, クエリを`h_i`によってソートすれば`max(..., 0)`の結果が正になるから, ここでの条件分岐を考えずに済む.
+
+後は各クエリがこの`x, y, h`と一致するか確認する.
+
+
+\```rust
+fn main() {
+    let n = read_one::<usize>();
+    let mut vec = Vec::new();
+    for _ in 0..n {
+        let i = read::<isize>();
+        vec.push((i[0], i[1], i[2]));
+    }
+
+    vec.sort_by_key(|x| x.2);
+    vec.reverse();
+
+    let mut ans_x = 0;
+    let mut ans_y = 0;
+    let mut ans_h = 0;
+    for x in 0..101 { for y in 0..101 {
+        let mut flg = true;
+        let h = vec[0].2 + (x - vec[0].0).abs() + (y - vec[0].1).abs();
+        for v in vec.iter() {
+            if v.2 != cmp::max(h - (x - v.0).abs() - (y - v.1).abs(), 0) {
+                flg = false;
+                continue;
+            }
+        }
+
+        if flg {
+            ans_x = x;
+            ans_y = y;
+            ans_h = h;
+        }
+    }}
+
+    println!("{} {} {}", ans_x, ans_y, ans_h);
+}
+\```
+
+
+## [D](https://beta.atcoder.jp/contests/abc112/tasks/abc112_d)
+
+数列`an`の要素数`N`と和`M`が与えられるので、`an`の各要素の最大公約数の取りうる最大値を求める.
+
+
+`a_1 + a_2 + ... + a_N`の最大公約数が`K`であるとき, 次のように括り出すことができる.
+
+\```
+K * (a_1' + a_2' + ... + a_N') = K * sum(a')
+\```
+
+したがって`K`は`M`の約数.
+
+次に`an`の要素数を`N`にするためには, `a'`の要素数が`N`個である必要がある.
+`min(sum(a'))`は全ての要素が`1`の場合に`N`となるので, `K`は大きくても`M / N`の範囲であることがわかる.
+
+よって, `i in 1 ~ M / N`について,Mが割り切れる`i`のうち最大のものが答え.
+
+
+また制約から`n = 1, m = 10^9`のケースがありうる. その場合処理が全て走ってしまうのでTLE(1WA), その場合の処理はアドホックに書いてしまった.
+
+
+### 解答
+\```rust
+fn main() {
+    let (n, m) = {
+        let i = read::<u64>();
+        (i[0], i[1])
+    };
+
+    let mut ans = 1;
+
+    if n == 1 {
+        println!("{}", m);
+        return;
+    }
+
+    for i in 1..(m / n + 1) {
+        if m % i == 0 { ans = i; }
+    }
+
+    println!("{}", ans);
+}
+\```
+
+## 所感
+A -> B -> D -> Cの順で解いた.
+立ち回りは悪くなかったと思う(DよりCにかけた時間の方が長かったので).  
+ただこのレベルで立ち回りとか考えずに全部解けるようにすべき,というのはそれはそうなので精進する.
+Cに戻ってきたときに全探索が可能なことに気づくまでは早かったがそこからの比較ミスは2WAに抑えられるものだったので反省.
+
+CよりDの方が簡単じゃないですか?  
+2WA以上出した時は全部消して0から書き直すと吉っぽい.  
+これを書いた後に見た解説放送中のコメントに, Cは`max(h) <= H <= max(h) + 200`に収まるからHについても全探索が可能、とあってなるほどなあとなった.