蟻本AtCoder版 練習帳 初級編 with Nim (bit全探索編)

# TL;DR

静的型付け言語の勉強がしたい&競プロに興味があるということで、最近Ver1.0.0がリリースされたNimを使って蟻本の勉強がしたくなりました(ver1.0.2になりましたね 2019/10/31現在)。Nimな理由はほかの人と違ってかっこいいという中二病感及びPython likeでかけてなおかつ早いというのが非常に魅力的だったからです。

そして、蟻本を買ったけどPOJにはNimがないしよくわからないのでAtCoderで類題解こうと思いました。

ということで、これは、
AtCoder 版！蟻本 (初級編)をNimで解いていくだけの日記帳です。

**bit全探索編です。**
bit全探索のNimの基本については、[ブログ](https://www.illumination27.com/nim%E3%81%A7bit%E5%85%A8%E6%8E%A2%E7%B4%A2/)で書いてます！

[日記帳リスト 随時更新]

- [気楽にウォームアップ](https://qiita.com/illumination-k/items/b3e6f30d5b98e3058611)
- [bit全探索](https://qiita.com/illumination-k/items/cc0e4542e7829db1ad63)
- [DFS](https://qiita.com/illumination-k/items/4ffc9d8792ac4fe69a7b)

## [ABC 045 C たくさんの数式](https://atcoder.jp/contests/arc061/tasks/arc061_a)

### 感想
bit全探索を覚えました。後で記事を書こうと思っています。bit全探索考えた人頭良すぎますね。
追記： [bit全探索記事](https://www.illumination27.com/nimでbit全探索/)書きました。ブログ作ったのでそっちです。
最後の文字列処理が思い浮かばなかったのでかっこいい書き方が知りたい。

```nim
import strutils
 
let
    S = stdin.readLine() 
    L = S.len() - 1
var
    sum_value = 0
 
block bit_search:
    var bit = 0
    while (bit < (1 shl L)):
        var vec = newSeq[int]()
        for i in 0..<L:
            if (bit and (1 shl i)) != 0:
                vec.add(i)
        inc bit 
        
        if vec.len() == 0:
            sum_value += parseInt(S)
        else:
            var tmp = 0
            for i in vec:
                sum_value += parseInt(S[tmp..i])
                tmp = i + 1
            sum_value += parseInt(S[tmp..L])

    echo sum_value
```

---

## [ABC 079 C - Train Ticket](https://atcoder.jp/contests/abc079/tasks/abc079_c)

### 感想
100%普通に全探索したほうが早い。
int(char)は文字コードで変換してる？かなんかでparseInt($char)ってしないとダメなところで時間がかかった。もう少しきれいに書けないものか。

```nim
import strutils
import algorithm

let
    S = stdin.readLine() 
    L = S.len() - 1

block bit_search:
    for bit in 0..(1 shl L):
        var 
            ans = 0
            vec = newSeq[int]()
        for i in 0..<L:
            if (bit and (1 shl i)) != 0:
                vec.add(i)

        var op_vec = newSeq[string](3)
        op_vec.fill("+")

        if vec.len() == 0:
            for s in S:
                ans += parseInt($s)
        else:
            ans += parseInt($S[0])
            for i in vec:
                op_vec[i] = "-"
            for op_loc in 0..2:
                if op_vec[op_loc] == "+":
                    ans += parseInt($S[op_loc + 1])
                else:
                    ans -= parseInt($S[op_loc + 1])
 
        if ans == 7:
            echo S[0], op_vec[0], S[1], op_vec[1], S[2], op_vec[2], S[3], "=7"
            break bit_search
```

---

## [ABC 104 C - All Green](https://atcoder.jp/contests/abc104/tasks/abc104_c)

### 感想
bit全探索の応用版みたいな感じ？最初に完全に説く問題を全探索して、次に点数の高いほうから説く問題を選ぶ感じ。最後にcountdown使うの思い浮かばなくてどうしようかなあと思っていたけど賢さが足りなかった。


```nim
import strutils, algorithm, sequtils

let
    DG = stdin.readline().split().map(parseInt)
    D = DG[0]
    G = DG[1]

var
    res = 1000000
    pc = mapIt(0..<D, stdin.readLine().split().map(parseInt))
    p_seq = newSeq[int]()
    c_seq = newSeq[int]()

for vec in pc:
    p_seq.add(vec[0])
    c_seq.add(vec[1])

for bit in 0..<(1 shl D):
    var
        ans = 0
        num = 0

    for i in 0..<D:
        if (bit and (1 shl i)) != 0:
            ans += p_seq[i]*(i+1)*100 + c_seq[i]
            num += p_seq[i]
    if ans >= G:
        res = min(num, res)
    else:
        for i in countdown(D-1, 0):
            if (bit and (1 shl i)) != 0:
                continue
            else:
                for j in 0..<p_seq[i]:
                    if ans >= G:
                        break
                    ans += 100*(i + 1)
                    num += 1
                        

    res = min(num, res)
    
echo res
```

---

## [ARC 029 A - 高橋君とお肉](https://atcoder.jp/contests/arc029/tasks/arc029_1)

### 感想
部分集合とその全体の集合に対する補集合をとって、その中での合計値を比べて大きい方がかかる時間。
部分集合の合計時間を、すべて同一の肉焼き機で焼いたときにかかる時間から引けば補集合ができる。

```nim
t_seq = newSeqWith(N, stdin.readLine.parseInt())
```

でうまいこと列をとれるらしい。

```nim
import algorithm, tables, math, strutils, sequtils, sets, lists

let
    N = stdin.readLine.parseInt()
    t_seq = newSeqWith(N, stdin.readLine.parseInt())
    t_sum = sum(t_seq)
var
    min_time = 1000000000

block bit_search:
    for bit in 0..<(1 shl N):
        var
            time = 0
            vec = newSeq[int]()

        for i in 0..<N:
            if (bit and (1 shl i)) != 0:
                vec.add(i)

        if vec.len() != 0:
            for v in vec:
                time += t_seq[v]
        else:
            continue

        let tmp_time = max(time, t_sum - time)

        if tmp_time < min_time:
            min_time = tmp_time


echo min_time
```

## [ABC 002 D - 派閥](https://atcoder.jp/contests/abc002/tasks/abc002_4)

### 感想
bit全探索すごい。
N < 12なのでかなり無理やり感がぬぐえないが、派閥を構成しうる組み合わせを全列挙して、その場合に必要な関係がすべて提示された関係に含まれていればその部分集合の配列長をMaxに設定して、Maxを出力。

```nim
import strutils, sequtils


let
    NM = stdin.readline().split().map(parseInt)
    N = NM[0]
    M = NM[1]
    relation = newSeqWith(M, stdin.readline().split().map(parseInt))

var max_cnt = 0

block bit_search:
    for bit in 0..<(1 shl N):
        var 
            vec = newSeq[int]()

        for i in 0..<N:
            if (bit and (1 shl i)) != 0:
                vec.add(i)
        
        vec = vec.map(proc (x:int): int = x+1)

        block search_relation:
            var flag = true
            for v1 in vec:
                for v2 in vec:
                    if v1 < v2:
                        let rel = @[v1, v2]
                        if rel in relation:
                            continue
                        else:
                            flag=false
                            break search_relation
            if flag:
                max_cnt = max(vec.len(), max_cnt)

echo max_cnt
```