
Rustnの**HashMap**を使って同じ要素をカウントして多い順に並べてみます。

## Contents

## HashMapについて

ハッシュマップはキーとそれに紐づいた値の対応関係を保持した構造です。
他の言語ではハッシュテーブルや連想配列などとも呼ばれています。

- [std::collections::HashMap](https://doc.rust-lang.org/std/collections/struct.HashMap.html)
- [キーとそれに紐づいた値をハッシュマップに格納する - The Rust Programming Language 日本語版](https://doc.rust-jp.rs/book-ja/ch08-03-hash-maps.html?highlight=hashmap#%E6%96%B0%E8%A6%8F%E3%83%8F%E3%83%83%E3%82%B7%E3%83%A5%E3%83%9E%E3%83%83%E3%83%97%E3%82%92%E7%94%9F%E6%88%90%E3%81%99%E3%82%8B)

## 重複した要素のカウント

ベクトルにある数字をそれぞれカウントします。

```rust
use std::collections::HashMap;

fn main() {
    let vector = vec![1, 3, 4, 1, 2, 5, 2, 3, 4, 1, 3, 4, 1];
    // 要素ごとのカウント
    let mut hashmap = HashMap::new();
    for x in vector {
        let counter = hashmap.entry(x).or_insert(0);
        *counter += 1;
    }
    println!("{:?}", hashmap);
}
```

```txt:出力
{4: 3, 2: 2, 3: 3, 1: 4, 5: 1}
```

`let mut hashmap = HashMap::new();`でHashMapを初期化します。
後の処理で型が推測できます。

`.entry(x)`でキーを挿入しますが、`.entry(x).or_insert(0)`ではまだ存在しない場合にのみキーを挿入します。
`.or_insert(0)`は可変の値(`<K, V>`のV)の参照を返すため、`*counter += 1`のようにポインターで値を操作できます。

## 値の大きい順にソートする

ハッシュマップをカウントを降順にソートします。

```rust
// 先ほどカウントの続き

// カウント順にソート
let mut vector2: Vec<_> = hashmap.into_iter().collect();
vector2.sort_by(|x, y| y.1.cmp(&x.1));
println!("{:?}", vector2);
```

```txt:出力
[(1, 4), (3, 3), (4, 3), (2, 2), (5, 1)]
```

`hashmap.into_iter().collect();`でハッシュマップをタプルのベクトルに変換してから、タプルの２番目の要素を基準にソートします。
`sort_by()`は安定で最悪計算量が`O(n log n)`です。
ラムダ式みたいに`|x, y| y.1.cmp(&x.1)`とベクトルの要素を比較して整列します。
xとyを交換すると昇順になり、`y.0`と元キーだった要素でも比較ができる。

## ハッシュマップから最小（最大）の数を取り出す

`min_by`と`max_by`で最小と最大の要素をとりだせます。

```rust
// 最小を取得
let min = hashmap.iter()
  .min_by(|a, b| a.1.cmp(&b.1))
  .unwrap();
// (5, 1)


// 最大を取得
let max = hashmap.iter()
  .max_by(|a, b| a.1.cmp(&b.1))
  .unwrap();
// (1, 4)
```

## ハッシュマップを使ったAtCoderの問題

> **問題文**
>
> 高橋君は，$N$ 個のボールを持っています． 最初，$i$ 番目のボールには，整数 $A_i$ が書かれています．
> 高橋君は，いくつかのボールに書かれている整数を書き換えて，$N$ 個のボールに書かれている整数が $K$ 種類以下になるようにしたいです．
> 高橋君は，少なくとも何個のボールの整数を書き換える必要があるでしょうか？
>
> [ABC081 - C Not so Diverse](https://atcoder.jp/contests/abc081/tasks)

入出力や制約はAtCoderのページを見てください。

### 回答

クリックすると開きます。

<details><summary>回答と考え</summary>

この問題はハッシュマップでユニークな要素をそれぞれカウントして、数が小さい順に $K - Unique(Ai)$ 種類分の個数を合計した数が答えになります。

```rust
use std::collections::HashMap;
use std::collections::HashSet;

fn main() {
    proconio::input! {
        n: i32,
        k: i32,
        a: [i32; n]
    }
    // ユニークな数
    let uniq: HashSet<i32> = a.clone().into_iter().collect();
    let len = uniq.len() as i32 - k;
    if len <= 0 {
        println!("0");
        return;
    }
    // 要素ごとのカウント
    let mut map = HashMap::new();
    for x in a {
        let counter = map.entry(x).or_insert(0);
        *counter += 1;
    }
    // カウント順にソート
    let mut v: Vec<_> = map.into_iter().collect();
    v.sort_by(|x, y| x.1.cmp(&y.1));
    v.reverse();
    // println!("{:?}", v);
    let mut answer = 0;

    // 数が小さいものからk以下まで足し算
    for _ in 0..len {
        answer += v.pop().unwrap().1;
    }
    println!("{}", answer);
}
```

ユニークなボールの数は`HashSet`でわかる。

</details>


【Rust】HashMapで配列の同じ要素をカウントして多い順に並べる


Rustの数値型のベクトルをスペースやカンマなどの区切り文字を挟んだ文字列に変換(join)する書き方です。
Rustで競技プログラミングを始めたので必要としました。

`vec![1, 2, 3]`を`1 2 3`と出力させます。
イメージはPythonの`list.join(" ")`。

[playground](https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=09f79ca9485db69ad1b98a822ab4e5da)でコードを実行確認できます。

## Contents

## 構文

```rust
// to_string
Vec<T>.iter().map(|x| x.to_string()).collect().join(" ")

// format!
Vec<T>.iter().map(|x| format!("{}", x)).collect().join(",")
```

この構文でベクトルを区切り文字で結合した文字列へ変換できる。
`format!("{}", x)`は応用が利くため便利。

以下で例と解説をする。

### 整数型

整数型のベクトルの例です。

```rust:rust
// 整数型
let src: Vec<i32> = vec![-3, -2, -1, 0, 1, 2, 3];

// 要素を整数型から文字列型変換
let dst: Vec<String> = src.iter().map(|x| x.to_string()).collect();
// 文字列型vectorを区切り文字で結合
println!("{}", dst.join(" "));
```

```txt:出力
-3 -2 -1 0 1 2 3
```

要素が文字列の`Vec<String>`では区切り文字を指定して結合する`.join(" ")`が利用できます。
そのため、`Vec<i32>`を`.map()`で要素ごとに文字列へ変換して`Vec<String>`にしています。
区切り文字は`.join(",")`などと変更できます。

- `iter().map(|x| x.to_string())`は要素ごとに文字列へ変換する処理です。Rust版のラムダ式ですかね。
  - [std::iter](https://doc.rust-lang.org/std/iter/)
  - [std::iter::Map](https://doc.rust-lang.org/std/iter/struct.Map.html)
- `.collect()`は`Map`を`Vec<T>`に直すことができる。
  - [std::iter.collect](https://doc.rust-lang.org/std/iter/trait.Iterator.html#method.collect)
  - `std::iter::Map`は`std::iter`を継承しているっぽい。

### 浮動小数点型

浮動小数点型も同じです。

```rust:rust
// 浮動小数点型
let src: Vec<f32> = vec![-3.3, -2.2, -1.1, 0.0, 1.1, 2.2, 3.3];

let dst: Vec<String> = src.iter().map(|x| x.to_string()).collect();
println!("{}", dst.join(" "));
```

```txt:出力
-3.3 -2.2 -1.1 0 1.1 2.2 3.3
```

`.0`は省略されるようです。

### 論理値型

浮動小数点型は`true`, `false`を出力できます。

```rust
    // 論理値型
    let src: Vec<bool> = vec![true, false];

    let dst: Vec<String> = src.iter().map(|x| x.to_string()).collect();
    println!("{}", dst.join(" "));
```

```txt:出力
true false
```

## format

`format!`で要素を文字列にするときのカスタマイズが容易になります。

- [std::fmt](https://doc.rust-lang.org/std/fmt/)に例がたくさんあります。

### 0埋め, パディング

[std::fmt#sign0](https://doc.rust-lang.org/std/fmt/#sign0)

```rust
// 浮動小数点型 0パディング
let src: Vec<f32> = vec![-3.3, -2.2, -1.1, 0.0, 1.1, 2.2, 3.3];

let dst: Vec<String> = src.iter().map(|x| format!("{:05}", x)).collect();
println!("{}", dst.join(" "));
```

```txt:出力
-03.3 -02.2 -01.1 00000 001.1 002.2 003.3
```

`format!("{:05}", x)`が5桁の0埋めです。

その他のサイン。

```rust
assert_eq!(format!("Hello {:+}!", 5), "Hello +5!");
assert_eq!(format!("{:#x}!", 27), "0x1b!");
assert_eq!(format!("Hello {:05}!", 5),  "Hello 00005!");
assert_eq!(format!("Hello {:05}!", -5), "Hello -0005!");
assert_eq!(format!("{:#010x}!", 27), "0x0000001b!");
```

### fillalignment

[std::fmt#fillalignment](https://doc.rust-lang.org/std/fmt/#fillalignment)

```rust
assert_eq!(format!("Hello {:<5}!", "x"),  "Hello x    !");
assert_eq!(format!("Hello {:-<5}!", "x"), "Hello x----!");
assert_eq!(format!("Hello {:^5}!", "x"),  "Hello   x  !");
assert_eq!(format!("Hello {:>5}!", "x"),  "Hello     x!");
```

## 文字列型

文字列型の場合は既に要素が文字列であるため、変換が不要です。

```rust
let months = vec!["January", "February", "March", "April", "May", "June", "July",
          "August", "September", "October", "November", "December"];
println!("{}", months.join(", "));
```

```txt:出力
January, February, March, April, May, June, July, August, September, October, November, December
```

## タプルの場合

Rustのタプルは異なる型を納められます。
`map()`はジェネリックだったのと、整数型と浮動小数点型は`to_string()`を持つため混合していても良いかと考えてましたが、エラーが出ました。

```rust
let src = (500, 6.4, 1);
let dst: Vec<String> = src.iter().map(|x| x.to_string()).collect();

println!("{}", dst.join(" "));
```

```txt:出力
error[E0599]: no method named `iter` found for tuple `({integer}, {float}, {integer})` in the current scope
  --> src/main.rs:41:32
   |
41 |     let dst: Vec<String> = src.iter().map(|x| x.to_string()).collect();
   |                                ^^^^ method not found in `({integer}, {float}, {integer})`

error: aborting due to previous error
```

型を混合したものは`iter`で扱えないようです。

## おわり

- [playground](https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=09f79ca9485db69ad1b98a822ab4e5da)


【Rust】数値型のベクトルをスペース区切りの文字列に変換(join)する


配列の要素が辞書型の場合のソートの仕方をまとめました。
lambdaを使うと任意のkeyでソートできます。
書き方もシンプルです。

業務では、API連携で受け取ったデータを処理するときに使っています。


２次元配列のソートはこちらで解説しています。[２次元配列をソートした結果（昇順・降順・逆順） | Python](https://www.suzu6.net/posts/88-python-max-min)


動作確認：Python 3.7

### ソートする配列

本題の前にソートする配列の一例をお見せします。

```py
arr = [{'name': 'takahashi', 'age': 32}, {'name': 'kikuchi', 'age': 43}, {'name': 'watanabe', 'age': 22}]
```

このように、文字列と数値を持ったdictを要素に持つ配列です。

```py
arr = [
    {'name': 'takahashi', 'age': 32},
    {'name': 'kikuchi', 'age': 43},
    {'name': 'watanabe', 'age': 22}
]
```

## 要素がdict型の配列をソート sorted()

**lambda**を使うと**dict**型も任意のkeyでソートできる。

```python
arr = [
    {'name': 'takahashi', 'age': '32'},
    {'name': 'kikuchi', 'age': '43'},
    {'name': 'watanabe', 'age': '22'}]

# ageで昇順
print(sorted(arr, key=lambda x: x['age']))
"""
[{'name': 'watanabe', 'age': '22'}, {'name': 'takahashi', 'age': '32'}, {'name': 'kikuchi', 'age': '43'}]
"""

# nameで昇順
print(sorted(arr, key=lambda x: x['name']))
"""
[{'name': 'kikuchi', 'age': '43'}, {'name': 'takahashi', 'age': '32'}, {'name': 'watanabe', 'age': '22'}]
"""

```

sorted()の引数keyにdictのkeyを参照させます。
やり方は`key=lambda x: x['age']`とする。

### sort()

`sort()`も同様です。

```py
# ageで昇順
arr.sort(key=lambda x: x['age'])
print(arr)
"""
[{'name': 'watanabe', 'age': '22'}, {'name': 'takahashi', 'age': '32'}, {'name': 'kikuchi', 'age': '43'}]
"""
```

### 降順 

`reverse=True`で降順になります。

```py
# ageで降順
arr.sort(key=lambda x: x['age'], reverse=True)
print(arr)
"""
[{'name': 'watanabe', 'age': '22'}, {'name': 'takahashi', 'age': '32'}, {'name': 'kikuchi', 'age': '43'}]
"""
```

### あわせてどうぞ

２次元配列のソートの実行結果をまとめました。

[２次元配列をソートした結果（昇順・降順・逆順） | Python](https://www.suzu6.net/posts/88-python-max-min)

コピペで実行できるよう、Pythonの書き方をまとめてあります。

- [三項演算子の代わりにmax, minを使いすっきり書く | Python](https://www.suzu6.net/posts/73-sort-2d-list)
- [Python3の配列でよく使う小技のまとめ](https://www.suzu6.net/posts/60-python-list)
- [【Python3】２次元配列をうまいこと表示する](https://www.suzu6.net/posts/74-sort-2d-list-print)
- [階乗の計算速度を比較 | Python](https://www.suzu6.net/posts/43)

要素が辞書型dictの配列をソートする | Python


Atcoderのマラソン型コンテスト[北大・日立新概念コンピューティングコンテスト2018](https://atcoder.jp/contests/hokudai-hitachi2018)に６日目になってやっと参加しました。
現時点(2019-02-19 12:00)でコードを提出した人が100人に満たないようです。

参加の閾値を下がるかと思うので、最低限の点数が取れるPythonのコードをさらします。
品質に関しては灰色コーダーなので察してください。
ご自由にどうぞ。

## ソースコード

[北大・日立新概念コンピューティングコンテスト2018で正の点数が取りたい](https://qiita.com/nekomimimi/items/6c0a05bc60bcb5f3e975)を参考にさせていただきました。

```python


def _output(S, L, c, v):
    print(S, L)
    for i in range(L):
        print(len(v[i]), c[i], *v[i])


def _input():
    N, K = list(map(int, input().split()))
    v = [[] for i in range(K)]
    c = [0 for i in range(K)]
    for i in range(K):
        tmp = list(map(int, input().split()))
        c[i] = tmp[1]
        v[i] = tmp[2:]

    return N, K, c, v


def calc(N, K, c, v):
    v_res = []
    c_res = []

    total_c = 0

    for i in range(K):
        if len(v[i]) > 0 and len(v[i]) <= 2:
            v_res.append(v[i])
            c_res.append(c[i])
        else:
            total_c += max(0, c[i])
    v_res.append([])
    c_res.append(max(1, total_c))
    return N, len(v_res), c_res, v_res

def main():
    N, K, c, v = _input()
    S, L, c, v = calc(N, K, c, v)
    _output(S, L, c, v)


if __name__ == "__main__":
    main()
```

`_input()`と`_output()`で入出力をしている。
`calc()`のところで$g(X,W)$を作成しています。

参考によると次数が$0<d \le 2$はそのままにして、それ以外は$f(X) \le g(X,W)$となるように正の係数と定数の合計を定数として出力しています。

スコアはA,B,Cの合計で4.5E08ぐらいは取れました。

## これから

$2<d$の次数をどうにかしてスコアを伸ばしていきたい。
あと１週間あるのでゆっくり考えていきます。

Pythonで点数をとりたい。北大・日立新概念コンピューティングコンテスト2018


Numpyを使わなくても簡単に２次元配列のソートができます。
昇順`sort()`・降順`sort(reverse=True)`・逆順`reverse()`の関数を２次元配列に適用した結果を記載します。

lambda関数を使った応用も追加しました。

動作確認：Python 3.6

## 準備

ソートに利用する$6 \times 3$の２次元配列を用意しました。
以降はこの配列に対して実行します。

```python
arr = [[0, 10, 6], [5, 7, 4], [9, 6, 3], [6, 3, 6], [9, 2, 9], [0, 6, 9]]

print(*arr, sep='\n')
"""
[0, 10, 6]
[5, 7, 4]
[9, 6, 3]
[6, 3, 6]
[9, 2, 9]
[0, 6, 9]
"""
```

出力は`# => 出力` 複数行の場合は`"""\n出力\n"""`として表現していく。

結果を見やするため、配列を[アンパック](https://www.suzu6.net/posts/74-sort-2d-list-print)して表示しています。


## 2次元配列をソート

### sort()

```python
arr = [[6, 10, 6], [3, 4, 9], [5, 7, 4], [9, 6, 3], [6, 3, 6], [9, 2, 9], [0, 6, 9], [7, 4, 4], [2, 1, 10], [8, 9, 3]]

arr.sort()

print(*arr, sep='\n')
"""
[0, 6, 9]
[0, 10, 6]
[5, 7, 4]
[6, 3, 6]
[9, 2, 9]
[9, 6, 3]
"""
```

`sort()`で２次元配列もソート出来ます。
特に指定もなく、１番目の要素を基準に並べている。

中身を確かめている時に気づいたが、２、３番目の要素もちゃんとソートされている。
ありがたい。

### sorted()

同様に`sorted()`を使ってもソート出来ます。

```python
arr = [[0, 10, 6], [5, 7, 4], [9, 6, 3], [6, 3, 6], [9, 2, 9], [0, 6, 9]]

arr = sorted(arr)

print(*arr, sep='\n')
"""
[0, 6, 9]
[0, 10, 6]
[5, 7, 4]
[6, 3, 6]
[9, 2, 9]
[9, 6, 3]
"""
```

### 降順 sort(reverse=True)

降順も同じように可能です。

```Python
arr = [[0, 10, 6], [5, 7, 4], [9, 6, 3], [6, 3, 6], [9, 2, 9], [0, 6, 9]]

arr.sort(reverse=True)

print(*arr, sep='\n')

"""
[9, 6, 3]
[9, 2, 9]
[6, 3, 6]
[5, 7, 4]
[0, 10, 6]
[0, 6, 9]
"""
```

１番目の要素から基準にして、降順となっています。

`arr = sorted(arr, reverse=True)`も同じ結果になります。

### 逆順 reverse()

２次元配列でもちゃんと逆順になります。

```python
arr = [[0, 10, 6], [5, 7, 4], [9, 6, 3], [6, 3, 6], [9, 2, 9], [0, 6, 9]]

arr.reverse()

print(*arr, sep='\n')
"""
[0, 6, 9]
[9, 2, 9]
[6, 3, 6]
[9, 6, 3]
[5, 7, 4]
[0, 10, 6]
"""
```

`arr = reversed(arr)`も同様。

## keyを指定してソートする

**lambda**を使うと指定した要素を基準にソートすることもできる。

### ２番目の要素を基準に昇順

引数**key**にlambdaを使って要素を割り当てる。

```python
arr = [[0, 10, 6], [5, 7, 4], [9, 6, 3], [6, 3, 6], [9, 2, 9], [0, 6, 9]]

# ２番目の要素で昇順
arr.sort(key=lambda x: x[1]) 

print(*arr, sep='\n')
"""
[9, 2, 9]
[6, 3, 6]
[9, 6, 3]
[0, 6, 9]
[5, 7, 4]
[0, 10, 6]
"""
```

このとき、１、３番目の要素は比較されない。
２番目の要素が同じ数値の時は、初期の並び順に依ります。

### あわせてどうぞ

- [Python3の配列でよく使う小技のまとめ](https://www.suzu6.net/posts/60-python-list)
- [【Python3】２次元配列をうまいこと表示する](https://www.suzu6.net/posts/74-sort-2d-list-print)
- [階乗の計算速度を比較 | Python](https://www.suzu6.net/posts/43)

２次元配列をソートした結果（昇順・降順・逆順） | Python


Pythonの２次元配列を`print()`で表示するコツを紹介します。
numpyを使わなくてもできます。

動作確認：Python 3.6

## ランダムな値の２次元配列の宣言

表示するランダムな２次元配列を用意します。
内包表記で２次元配列を宣言して、`random.randint()`で指定範囲のランダムな整数を用意しました。

出力は`# => 出力`、複数行の場合は`"""\n出力\n"""`として表現しています。

```python
import random

h = 10
w = 3
arr = [[random.randint(0, 10)] * w for _ in range(h)]

print(arr)
# => [[6, 10, 6], [3, 4, 9], [5, 7, 4], [9, 2, 3], [6, 3, 6], [9, 6, 9], [0, 6, 9], [7, 4, 4], [2, 1, 10], [8, 9, 3]]
```

そのままだと１行で出力されるため見づらいですね。

## *でアンパッキングする

*(アスタリスク)を添えると配列をアンパックできます。
どういうことかというと、下のように要素を分解してくれます。

```python
print(arr[0], arr[1], arr[2], arr[3], ....)

# 上と同じで要素を分解する
print(*arr)
```

`for文`など使うよりもスッキリしますね。
アンパッキングすると要素の間の文字列（**separator**）を指定できるのでこれを利用します。
改行を**separator**に指定。

```python
# 改行して２次元配列を表示
print(*arr, sep='\n')

""""
[6, 10, 6]
[3, 4, 9]
[5, 7, 4]
[9, 2, 3]
[6, 3, 6]
[9, 6, 9]
[0, 6, 9]
[7, 4, 4]
[2, 1, 10]
[8, 9, 3]
""""
```

## かっこやセミコロンをなくす

要素だけ表示するにはこのように書きます。

```python
for a in arr:
    print(*a)
"""
6 10 6
3 4 9
5 7 4
9 2 3
6 3 6
9 6 9
0 6 9
7 4 4
2 1 10
8 9 3
"""
```

## カンマ区切りのcsvにする

```python
for a in arr:
    print(*a, sep=',')
"""
6,10,6
3,4,9
5,7,4
9,2,3
6,3,6
9,6,9
0,6,9
7,4,4
2,1,10
8,9,3
"""
```

### こちらもどうぞ

- [Python3の配列でよく使う小技のまとめ](https://www.suzu6.net/posts/60-python-list)
- [【Python3】２次元配列とdictのソートの方法](https://www.suzu6.net/posts/74-sort-2d-list)
- [階乗の計算速度を比較 | Python](https://www.suzu6.net/posts/43)

【Python3】２次元配列をうまいこと表示する


[前回](https://www.suzu6.net/posts/64-atcoder-bc116)に続いて2回目のコンテスト。
ABC問題くらいはいけるだろうと参戦したらCでダメでした。
情けない。。。

言語は**Python3.4**です。

## コンテスト

全国統一プログラミング王決定戦の予選です。

2019-01-27(日) 21:00 ~ 2019-01-27(日) 23:00

[AtCoder 全国統一プログラミング王決定戦予選/NIKKEI Programming Contest 2019](https://atcoder.jp/contests/nikkei2019-qual)

### 成績

![result](/images/posts/72/score.png)

順位は2216位。
始まって１時間後から参加したのでしょうがないね。

## 提出したコードとどう考えたか

解説を見るか同じ言語の回答を見れば良いものですが、備忘録のため提出したコードをどう考えて書いたかのメモしておく。
コメントはあとでつけました。

### A - Subscribers

[問題](https://atcoder.jp/contests/nikkei2019-qual/tasks/nikkei2019_qual_a)

アンケート結果から購読者の重複数の最大と最小を考える問題。
最大はAかBの小さい方。
最小は$A + B − N$か0の大きい方です。

```python
N, A, B = list(map(int, input().split()))

Max = A if A < B else B
Min = (A + B) - N 
Min = max(Min, 0)

print(Max, Min)
```

なぜ、3項演算子のような書き方をしたのか。
`min()`でよかった。


#### 解説をみて

Pythonの回答があった。

```python
N, A, B = map(int, input().split())
print(min(A, B), max(0, A + B - N))
```

すごくスマートです。

### B - Touitsu

[問題](https://atcoder.jp/contests/nikkei2019-qual/tasks/nikkei2019_qual_b)

３つの文字列を一文字ずつ入れ替えて同じになるまでの操作回数を求める問題。

```python
N = int(input().strip())
A = input().strip()
B = input().strip()
C = input().strip()


count = 0
for a, b, c in zip(A, B, C):
  if a is b:
    if a is c:
      continue
    else:
      count += 1
  else:
    if b is c:
      count += 1
    elif a is c:
      count += 1
    else:
      count += 2

print(count)
```

`zip()`を使って文字列をいっぺんに扱えたことはよかったが、判定式がグダグダ。

#### 解説をみて

`set()`で重複しない文字の数を求めればよかったのか。

リファクタリング

```python
N = int(input().strip())
A, B, C = input(), input(), input()

count = 0
for arr in zip(A, B, C):
  count += len(set(arr)) - 1

print(count)
```

## C - Different Strokes

[問題](https://atcoder.jp/contests/nikkei2019-qual/tasks/nikkei2019_qual_c)

自分の幸福度と相手の幸福度の差が一番大きくなるように交互に選ぶいじわるな問題。
一緒に幸福度を高める道はなかったのか。。。

```python
N = int(input().strip())
arr = []
for n in range(N):
  A, B = list(map(int, input().split()))
  arr.append([ A - B , A, B]) # ここを間違えた。

# １つめの要素をキーにして降順ソート
arr = sorted(arr, reverse=True)
# それぞれの幸福度
ta = sum([a[1] for a in arr[::2]])
ao = sum([a[2] for a in arr[1::2]])
print(ta - ao)
```

AとBの差が大きなものから選んでいけば良いかと考えていた。
２次元配列のソートはとても便利だ。
例題と半分のケースは通ってしまうので固執してしまった。

ここで時間終了。

#### 解説をみて

AとBの差ではなく和の降順だったようだ。
色々と試せばよかった。

## おわりに

散々な結果になってしまった。
地道に解ける問題を増やすしかない。


AtCoder 全国統一プログラミング王決定戦予選/NIKKEI Programming Contest 2019の記録 | Python


気になっていたAtCoderのコンテストに初参加しました。
まだまだひよっこですが、今後の成長のためにも復習を兼ねて記録していきます。

言語は**Python3.4**です。

## コンテスト

2019-01-20(日) 21:00 ~ 2019-01-20(日) 22:40

[AtCoder Beginner Contest 116](https://atcoder.jp/contests/abc116)

### 成績

![result](/images/posts/64/score.png)

順位は665位で上から40％ぐらいの位置についた。
BC問題に時間がかかってD問題は集中力が切れてしまった。

## 提出したコードとどう考えたか

解説を見るか同じ言語の回答を見れば良いものですが、備忘録のため提出したコードをどう考えて書いたかのメモしておく。
コメントはあとでつけました。

### A - Right Triangle

[問題](https://atcoder.jp/contests/abc116/tasks/abc116_a)

直角三角形の面積を計算する問題。
$\angle ABC = 90^\circ$は問題文からわかる。
３辺の長さを受け取り、面積を出力する。
入力の順序からどの辺の長さか決まっているので、$AB \times BC / 2$で良い。

```python
ab, bc, ca = list(map(int, input().split()))

S = ab * bc / 2
print(int(S)) # 割り算すると.0がつくため整数にして出力。
```

#### 解説をみて

間違ってなかった。

### B - Collatz Problem

[問題](https://atcoder.jp/contests/abc116/tasks/abc116_b)

とある規則を持った数列の繰り返しが出現する箇所を特定する問題。
数列の作成はすぐに浮かんだが、条件を理解することに手間取ってしまった。
同じ数値が初めて現れる番号を出力すれば良い。

```python
def f(n):
    # 数列の規則
    if n % 2 == 0:
        return int(n / 2)
    else:
        return 3 * n + 1
 
if __name__ == "__main__":
    s = int(input())
 
    a = s
    arr = [s]
    for i in range(1000000): # m < 1000000となるので
        a = f(a)
        if a in arr:
            # 同じ数値が現れたた出力
            print(len(arr) + 1)
            break
        # 数列の格納
        arr.append(a)
```

#### 解説をみて

`4 → 2 → 1 → 4`のループに必ずなる**Collatz problem**らしい。
`4`が出現した`m+3`で求まる。

リファクタリング

```python
def f(n):
    # 数列の規則
    if n % 2 == 0:
        return int(n / 2)
    else:
        return 3 * n + 1
 
if __name__ == "__main__":
    s = int(input())
    if s == 2 or s == 1:
        # 2と1もループになる。
        print(4)
        exit()
    for m in range(1, 1000000): # m < 1000000となるので
        if s == 4:
            print(m + 3)
            break
        s = f(s)
```

配列をもたずに判定するように書き換えたが、
メモリ消費も実行時間も変わらなかった。。。。

## C - Grand Garden

[問題](https://atcoder.jp/contests/abc116/tasks/abc116_c)

花を指定の高さまで水をあげて育てる最小手数を求める問題。
水をやると高さが+1。
花は並んでおり、隣り合う範囲はまとめて水をやれる。

高さ配列の要素を最小値で引いていけば、0の箇所で配列を分割できると考えた。
手数はその最小値分足していく。
分割した配列を同様に処理する。
これを再帰的に解いていく。


```python
count = 0


def mizu(h):
    global count
    # 終端処理
    if len(h) is 0:
        return
    if len(h) is 1:
        count = count + h[0]
        return
    # その範囲の最小値
    m = min(h)
    count = count + m
    # 残りの高さ
    h = [i - m for i in h]
    while 0 in h:
        # （最小値だった）0の箇所で分割
        mizu(h[:h.index(0)])
        h = h[h.index(0)+1:]
    mizu(h)

if __name__ == "__main__":
    N = int(input())
    h = list(map(int, input().split()))
    mizu(h)
    print(count)
```

#### 解説をみて

小難しい証明がなされていた。。。
ただ、考え方は間違っていなかったようだ。

### D - Various Sushi

[問題](https://atcoder.jp/contests/abc116/tasks/abc116_d)

満足度を最大化する寿司の組み合わせを求める、ナップサック問題の一種。
$1 \leqq K \leqq N \leqq 10^5$であり全探索では時間がかかりすぎるので工夫がいる。

今週中には解く。。。

## 初めて参加してみて

[Paiza](https://paiza.jp/challenges/info)や[HuckerRank](https://www.hackerrank.com/)でちょこちょこ練習していたため、
Beginner Contestなんて楽勝だろうww　と高を括って過去問も解かずに挑戦して玉砕しました。

悔しいので、過去問を解きつつ来週のコンテストに向けて勉強する！
