蟻本AtCoder版 練習帳 初級編 with Nim (DFS)

# TL;DR

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

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

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

**DFSです。**
DFSのNimの基本については、[ブログ](https://www.illumination27.com/)そのうちで書きます！

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

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

## [ATC 001 A 深さ優先探索](https://atcoder.jp/contests/atc001/tasks/dfs_a)

### 感想

DFSの典型的なやつ

```nim
# H*W二次元配列 boolはDefault=falseで初期化される
seen = newSeqWith(H, newSeq[bool](W))
```

### コード

```nim
import strutils, sequtils

const 
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]

let
    HW = stdin.readline().split().map(parseInt)
    H = HW[0]
    W = HW[1]

var
    field = newSeq[string](H)
    seen = newSeqWith(H, newSeq[bool](W))

for i in 0..<H:
    field[i] = stdin.readline()

proc dfs(h:int, w:int) =
    seen[h][w] = true

    for i in 0..<4:
        var
            nh = h + dx[i]
            nw = w + dy[i]

        if (nh < 0) or (nh >= H) or (nw < 0) or (nw >= W):
            continue

        if field[nh][nw] == '#':
            continue

        if seen[nh][nw]:
            continue

        dfs(nh, nw)

var
    sh = 0
    sw = 0
    gh = 0
    gw = 0


for h in 0..<H:
    for w in 0..<W:
        if field[h][w] == 's':
            sh = h 
            sw = w 
        elif field[h][w] == 'g':
            gh = h 
            gw = w 
        else:
            continue

dfs(sh, sw)

if seen[gh][gw]:
    echo "Yes"
else:
    echo "No" 
```

## [ARC 031 B 埋め立て](https://atcoder.jp/contests/arc031/tasks/arc031_2)

### 感想

連結成分の個数を求める問題っぽいやつ。
スタート地点を埋め立てて、その時の連結成分が1個ならOKみたいな感じ。

### コード

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

const 
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]

var
    field = newSeq[string](10)

for i in 0..<10:
    field[i] = stdin.readLine()



# どっかをoにしたあとそこからDFSして島の数が1ならOK、1じゃなければだめ
proc grid_dfs(h:int, w:int, field:seq[string]):seq[string] =
    var
        ret = newSeq[string]()

    for i in 0..<10:
        ret.add("x".repeat(10))
    
    proc dfs(h:int, w:int) =
        ret[h][w] = 'o'

        for i in 0..<4:
            var
                nh = h + dx[i]
                nw = w + dy[i]

            if (nh < 0) or (nh >= 10) or (nw < 0) or (nw >= 10):
                continue

            if field[nh][nw] == 'x':
                continue

            if ret[nh][nw] == 'o':
                continue
            
            dfs(nh, nw)
    
    dfs(h, w)

    return ret


var flag = false
block search:
    for i in 0..<10:
        for j in 0..<10:
            var
                tmp_result = grid_dfs(i, j, field)
            
            tmp_result[i][j] = 'x'
            
            if tmp_result == field:
                flag = true 
                break search

if flag:
    echo "YES"
else:
    echo "NO"
```

## [ARC 037 B バウムテスト](https://atcoder.jp/contests/arc037/tasks/arc037_b)

### 感想

絶対にもっといい解法があると思うので、ほかの人のコードを読みたい。
とりあえずTableが便利だった。大体辞書。procの引数のときにvarで入れるとエラーがでるっぽい？

```nim
import tables
# 空テーブルの作成
ex = initTable[int, string]

# Keyがあるかどうか
ex.hasKey(1)

# Iterator(pairs, keys, values)
for k, v in ex.pairs:
  echo k, v
```

dfsを使った連結成分の個数を求めるだけじゃなくて連結成分の中身を持ってきてその中身が木がどうかを判別する。無向グラフなので両方向に対してエッジを張ってあるので、最後にedge数は2で割る必要がある。

木なら$$Node-Edge=1$$なので判別自体は簡単。

### コード
```nim
import algorithm, tables, math, strutils, sequtils, sets, lists

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

var
    graph = initTable[int, seq[int]]()
    connect_graph = newSeq[seq[int]]()
    seen = initTable[int, bool]() 

for i in 1..N:
    graph[i] = newSeq[int]()
    seen[i] = false

var seen_result = seen

for rel in relation:
    graph[rel[0]].add(rel[1])
    graph[rel[1]].add(rel[0])

proc graph_dfs(i:int, graph:Table[int, seq[int]], seen:Table[int, bool]): Table[int, bool]=
    var ret = seen
    
    proc dfs(i:int) =
        ret[i] = true
        for v in graph[i]:
            if ret[v]: continue
            dfs(v)
    dfs(i)
    return ret

while true:
    var 
        cnt = 0
        
    for v in seen_result.values:
        if v:
            inc cnt 
    if cnt == seen.len():
        break

    var tmp = newSeq[int]()
    var tmp_result: Table[int, bool]

    for k, v in seen_result.pairs:
        if seen_result[k]:
            continue
        tmp_result = graph_dfs(k, graph, seen)

    for k, v in tmp_result.pairs:
        if tmp_result[k]:
            seen_result[k] = v
            tmp.add(k)

    connect_graph.add(tmp)

var tree_cnt = 0

for nodes in connect_graph:
    let node_cnt = nodes.len()
    var edge_cnt = 0
    for node in nodes:
        edge_cnt += graph[node].len()

    if (node_cnt - int(edge_cnt/2)) == 1:
        inc tree_cnt

echo tree_cnt
```