ABC117 | /var/log/koka

ABC117

考察

AtCoder

TODO

published: 2019-02-03updated: 2022-11-27

AtCoder Beginners Contest 117の参加記録。

A-Entrance Examination

$X \cdot T : T = T : x$ を満たす $x$ を求める.式変形して
$x = \frac{T}{X}$

解答

fn main() {
    let (t, x) = {
        let i = read::<f64>();
        (i[0], i[1])
    };
    println!("{}", t / x);
}

B-Polygon

$\bm{L} = L_1, L_2, \dots , L_N$ の $N$ 角形は存在するか.

定理 : 一番長い辺が他の $N−1$ 辺の長さの合計よりも真に短い場合に限り、条件を満たす $N$ 角形が描ける。

から, 最も長い辺とその他の辺の和を比較する.
その他の辺の和は, (全ての辺の和) - (最長辺)とすれば楽.

解答

fn main() {
    let _ = read_one::<usize>();
    let ln = read::<usize>();
    let max = ln.iter().max().unwrap();
    let sum = ln.iter().sum::<usize>() - max;
    if max < &sum {
        println!("Yes");
    } else {
        println!("No");
    }
}

C - Streamline

$N$ 個の駒と数直線上に $M$ 個の座標が与えられる. 最初に $N$ 個の駒を好きな座標に置いてから,

ある駒を1つ選び, その駒の座標を $+1$ または $-1$ する

操作を行い, $M$ 個全ての座標を訪れる為の操作の最小回数を求める.

初期配置にはコストがかからない.

-90 -10 0 1 4に対して2つ駒を置くとする. このとき移動コストは以下のようになる.

-90

-10

$x_i$ から $x_j$ に移動する為の操作回数は $abs(x_i - x_j)$ だから, 移動コストが大きい座標 $x_i, x_j$ に配置すればその2点間の移動コストが節約できる.

-90

-10

3つ目以降の駒や, 駒を座標の途中に置いた場合でも, 右端からその座標までの移動と, その座標から左端までをそれぞれの駒で行なえばよい.
したがって(駒数 - 1)個分だけ座標間の移動コストを取り除けばよい.

解答

fn main() {
    let (n, m) = {
        let i = read::<usize>();
        (i[0], i[1])
    };
    let mut xm = read::<isize>();
    xm.sort();
    let mut cost = Vec::new();
    for i in 0..m - 1 {
        cost.push((xm[i] - xm[i + 1]).abs() as usize);
    }

    cost.sort();

    for _ in 0..n - 1 { cost.pop(); }
    println!("{}", cost.into_iter().sum::<usize>());
}

D - XXOR

TODO

桁DPについて復習

$\bm{A} = A_1, A_2, \dots , A_N$ と $K \geq 0$ が与えられる.
$f(x) = \sum^{N}_{i}(X xor A_i) \; where \; x \leq K$
の最大値を求める.

3 7
1 6 3

上の入力例1 6 3を2進数で表してみる.

0 1 1 0 # 6
0 0 1 1 # 3
0 0 0 1 # 1

各々とのXORが最大になるようにするには, 各桁で0/1の少ない方を立てればいい.

所感

Dの方針が立ってから無限にバグらせてた. C迄のスピード感は良かったのでもったいなかった.

http://drken1215.hatenablog.com/entry/2019/02/03/224200 にある

$X \leq K$ であるとは、上位ビットから見たときに $X$ と $K$ のビットが初めて一致しなかった桁が $d$ であったとしたとき

$d$ より上位の桁については、 $X$ は $K$ と一致

$d$ 桁目については $X$ は $0$ で, $K$ は $1$ である

$d$ より下位の桁については $X$ はなんでもいい

がわかりやすかった. 各桁のビット比較で大小比較が行えればデータをbit列のまま取り扱うことができ, bit - usize間の変換がいらず実装が楽になる.

Commits

2022-11-27 00:25:35897b048fupdate remark-custom-container to 1.2.0

commit 897b048fe31450b5d4f6545855125b76492f9066
Author: koka &lt;koka.code@gmail.com&gt;
Date:   Sun Nov 27 00:25:35 2022 +0900

  update remark-custom-container to 1.2.0
  
  fix

diff --git a/_posts/2019-02-03-abc117.md b/_posts/2019-02-03-abc117.md
index 0fd5477..72d750d 100644
--- a/_posts/2019-02-03-abc117.md
+++ b/_posts/2019-02-03-abc117.md
@@ -115,7 +115,9 @@ fn main() {

## D - XXOR
::: warning TODO
-  桁DPについて復習
+
+桁DPについて復習
+
:::

$\bm{A} = A_1, A_2, \dots , A_N$ と$K \geq 0$が与えられる.

2021-01-30 22:18:1735b550aecopy md

commit 35b550ae83af4efaeadf33471c8ca8a32c1079c8
Author: koka &lt;koka.code@gmail.com&gt;
Date:   Sat Jan 30 22:18:17 2021 +0900

  copy md

diff --git a/_posts/2019-02-03-abc117.md b/_posts/2019-02-03-abc117.md
new file mode 100644
index 0000000..0fd5477
--- /dev/null
+++ b/_posts/2019-02-03-abc117.md
@@ -0,0 +1,155 @@
+---
+title: ABC117
+date: 2019-02-03
+categories:
+- Competitive Programming
+tags:
+  - AtCoder
+  - TODO
+description: 考察
+---
+AtCoder Beginners Contest 117の参加記録。
+
+## [A-Entrance Examination](https://atcoder.jp/contests/abc117/tasks/abc117_a)
+$X \cdot T : T = T : x$
+を満たす$x$を求める.式変形して  
+$x = \frac{T}{X}$
+
+### 解答
+
+\```rust
+fn main() {
+    let (t, x) = {
+        let i = read::&lt;f64&gt;();
+        (i[0], i[1])
+    };
+    println!("{}", t / x);
+}
+\```
+
+## [B-Polygon](https://atcoder.jp/contests/abc117/tasks/abc117_b)
+$\bm{L} = L_1, L_2, \dots , L_N$ の$N$角形は存在するか.  
+&gt; 定理 : 一番長い辺が他の$N−1$辺の長さの合計よりも真に短い場合に限り、条件を満たす$N$角形が描ける。
+
+から, 最も長い辺とその他の辺の和を比較する.  
+その他の辺の和は, (全ての辺の和) - (最長辺)とすれば楽.
+
+### 解答
+
+\```rust
+fn main() {
+    let _ = read_one::&lt;usize&gt;();
+    let ln = read::&lt;usize&gt;();
+    let max = ln.iter().max().unwrap();
+    let sum = ln.iter().sum::&lt;usize&gt;() - max;
+    if max &lt; &sum {
+        println!("Yes");
+    } else {
+        println!("No");
+    }
+}
+\```
+
+## [C - Streamline](https://atcoder.jp/contests/abc117/tasks/abc117_c)
+$N$個の駒と数直線上に$M$個の座標が与えられる.
+最初に$N$個の駒を好きな座標に置いてから,
+- ある駒を1つ選び, その駒の座標を$+1$または$-1$する  
+
+操作を行い, $M$個全ての座標を訪れる為の操作の最小回数を求める.
+
+---
+初期配置にはコストがかからない.  
+
+`-90 -10 0 1 4`に対して2つ駒を置くとする. このとき移動コストは以下のようになる.
+
+&lt;div class="graph"&gt;
+  &lt;div class="edge"&gt;-90&lt;/div&gt;
+  &lt;div class="node"&gt;80&lt;/div&gt;
+  &lt;div class="edge"&gt;-10&lt;/div&gt;
+  &lt;div class="node"&gt;10&lt;/div&gt;
+  &lt;div class="edge"&gt;0&lt;/div&gt;
+  &lt;div class="node"&gt;1&lt;/div&gt;
+  &lt;div class="edge"&gt;1&lt;/div&gt;
+  &lt;div class="node"&gt;3&lt;/div&gt;
+  &lt;div class="edge"&gt;4&lt;/div&gt;
+&lt;/div&gt;
+
+$x_i$から$x_j$に移動する為の操作回数は$abs(x_i - x_j)$ だから, 移動コストが大きい座標$x_i, x_j$に配置すればその2点間の移動コストが節約できる.
+
+&lt;div class="graph"&gt;
+  &lt;div class="edge piece"&gt;-90&lt;/div&gt;
+  &lt;div class="node cut"&gt;80&lt;/div&gt;
+  &lt;div class="edge piece"&gt;-10&lt;/div&gt;
+  &lt;div class="node"&gt;10&lt;/div&gt;
+  &lt;div class="edge"&gt;0&lt;/div&gt;
+  &lt;div class="node"&gt;1&lt;/div&gt;
+  &lt;div class="edge"&gt;1&lt;/div&gt;
+  &lt;div class="node"&gt;3&lt;/div&gt;
+  &lt;div class="edge"&gt;4&lt;/div&gt;
+&lt;/div&gt;
+
+3つ目以降の駒や, 駒を座標の途中に置いた場合でも, 右端からその座標までの移動と, その座標から左端までをそれぞれの駒で行なえばよい.  
+したがって(駒数 - 1)個分だけ座標間の移動コストを取り除けばよい.
+
+### 解答
+
+\```rust
+fn main() {
+    let (n, m) = {
+        let i = read::&lt;usize&gt;();
+        (i[0], i[1])
+    };
+    let mut xm = read::&lt;isize&gt;();
+    xm.sort();
+    let mut cost = Vec::new();
+    for i in 0..m - 1 {
+        cost.push((xm[i] - xm[i + 1]).abs() as usize);
+    }
+
+    cost.sort();
+
+    for _ in 0..n - 1 { cost.pop(); }
+    println!("{}", cost.into_iter().sum::&lt;usize&gt;());
+}
+\```
+
+## [D - XXOR](https://atcoder.jp/contests/abc117/tasks/abc117_d)
+::: warning TODO
+  桁DPについて復習
+:::
+
+$\bm{A} = A_1, A_2, \dots , A_N$ と$K \geq 0$が与えられる.  
+$f(x) = \sum^{N}_{i}(X xor A_i) \; where \; x \leq K$  
+の最大値を求める.
+
+---
+
+\```
+3 7
+1 6 3
+\```
+
+上の入力例`1 6 3`を2進数で表してみる.
+
+\```
+0 1 1 0 # 6
+0 0 1 1 # 3
+0 0 0 1 # 1
+\```
+
+各々とのXORが最大になるようにするには, 各桁で`0/1`の少ない方を立てればいい.
+
+## 所感
+
+Dの方針が立ってから無限にバグらせてた.
+C迄のスピード感は良かったのでもったいなかった.
+
+[http://drken1215.hatenablog.com/entry/2019/02/03/224200](http://drken1215.hatenablog.com/entry/2019/02/03/224200) にある
+
+&gt; $X \leq K$ であるとは、上位ビットから見たときに$X$と$K$のビットが初めて一致しなかった桁が $d$であったとしたとき
+&gt; - $d$より上位の桁については、$X$は$K$と一致
+&gt; - $d$桁目については$X$は$0$で,$K$は$1$である
+&gt; - $d$より下位の桁については$X$はなんでもいい
+
+がわかりやすかった. 各桁のビット比較で大小比較が行えればデータをbit列のまま取り扱うことができ, bit - usize間の変換がいらず実装が楽になる.
+

Commits

Comments