蟻本AtCoder版 練習帳 初級編 with Nim （特殊な状態の列挙、貪欲法）

TL;DR

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

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

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

特殊な状態の列挙

ABC 054 C One-stroke Path

nextPermutationすればいけた。計算量見積もれる力が必要。

あとリスト内包表記を覚えた

import future

let v = lc[ x | (x <- 1..10, x mod 2 == 0), int]

echo v

# @[2, 4, 6, 8, 10]

回答はこんな感じになった。bit全探索とか再帰とかでうまく解けるのだろうか。1スタート固定なので順列生成を2からやったくらいが工夫した（）点。

import strutils, sequtils, tables, future, algorithm

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]]()
    v = lc[ x | (x <- 2..N), int]
    perm = newSeq[seq[int]]()

while true:
    perm.add(v) 
    if v.nextPermutation() == false:
        break

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

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


var 
    cnt = 0

for p in perm:
    var 
        start = 1
        flag = true
    for i in 0..<p.len():
        if p[i] in graph[start]:
            start = p[i]
        else:
            flag = false
            break

    if flag:
        inc cnt

echo cnt

JOI 2009 予選 D カード並べ

Pythonなら秒で解けそう...

nimの他の人のページ(barnybug/nim-combinatorics)からcombinationの実装を借りてきた。

よくわからないって書いてたけどnextPermutaionはソートしてから使わないと全列挙されないらしい。中身を知らないからこうなる。
combinationの実装とかについては別に記事でも書こうかなと思っている。ムダに長いコードになってしまった。あとsugarを読み込ませようとしてCEした。悲しい。

import strutils

iterator combinations*(m:int, n:int): seq[int] =
    var c = newSeq[int](n)
    for i in 0..<n:
      c[i] = i
    
    block outer:
        if n == 0: break outer
        
        while true:
            yield c

            var i = n - 1
            inc c[i]

            if c[i] <= m - 1: continue

            while c[i] >= m - n + i:
                dec i
                if i < 0: break outer
            
            inc c[i]
            while i < n - 1:
                c[i+1] = c[i] + 1
                inc i


iterator combinations*[T](ys: openarray[T], n: int): seq[T] =
    let m = len(ys)
    var rs = newSeq[T](n)

    for c in combinations(m, n):
        for i in 0..<n:
            rs[i] = ys[c[i]]

        yield rs

iterator permutations*[T](ys: openarray[T]): seq[T] =
    var
        d = 1
        c = newSeq[int](ys.len)
        xs = newSeq[T](ys.len)
    
    for i, y in ys: xs[i] = y
    yield xs
    
    block outer:
        while true:
            while d > 1:
                dec d
                c[d] = 0
            while c[d] >= d:
                inc d
                if d >= ys.len: break outer
        
            let i = if (d and 1) == 1: c[d] else: 0
            swap xs[i], xs[d]
            yield xs
            inc c[d]

let
    n = stdin.readline.parseInt
    m = stdin.readline.parseInt

var
    cards = newSeq[string]()
    comb = newSeq[string]()

for i in 0..<n:
    cards.add(stdin.readline)


for c in combinations(cards, m):
    for p in permutations(c):
        var str = ""
        for s in p:
            str = str & $s
        
        if str in comb: continue
        else: comb.add(str)

echo comb.len()

yukicoder No.133 カードゲーム

ほんとにこれ通るの？みたいな全列挙。全部の出し方をpermutationで出力してその中で勝てるかどうか判定しただけ。

import strutils, sequtils, algorithm

let N = stdin.readline.parseInt

var
    A = stdin.readLine.split.map(parseInt).sorted()
    B = stdin.readLine.split.map(parseInt).sorted()
    aPerm = newSeq[seq[int]]()
    bPerm = newSeq[seq[int]]()
    cnt = 0
    general_aWin = 0

while true:
    aPerm.add(A)
    if A.nextPermutation() == false: break

while true:
    bPerm.add(B)
    if B.nextPermutation() == false: break

for a in aPerm:
    for b in bPerm:
        inc cnt
        var
            aWin = 0
            bWin = 0
        for i in 0..<N:
            if a[i] > b[i]:
                inc aWin
            else:
                inc bWin

        if aWin > bWin:
            inc general_aWin


echo general_aWin/cnt

貪欲法

JOI 2007 予選 A おつり

高い硬貨から使えばいい。

import strutils

const coins = @[500, 100, 50, 10, 5, 1]

var 
    N = stdin.readline.parseInt
    change = 1000 - N
    cnt = 0

for c in coins:
    while change >= c:
        var tmp = change div c
        cnt += tmp
        change = change - c * tmp

echo cnt

区間スケジューリング

KUPC 2015 A 東京都

区間スケジュール要素がいまいちわからなかった。単純に全探索っぽいことしてしまった。

import strutils, sequtils, algorithm

let
    T = stdin.readline.parseInt
    S = newSeqWith(T, stdin.readLine)

for s in S:
    var 
        ans = 0
        idx = 0
    while idx + 4 < s.len():
        if s[idx..<idx+5] == "tokyo" or s[idx..<idx+5] == "kyoto":
            inc ans
            idx += 5
        else:
            inc idx
    echo ans

ABC 103 D - Islands War

これが区間スケジューリングかという感じだった。tupleでSortしたければsortByItでソートできる。(a, b)の戦争のときにbを昇順に並べて、その中でbに一番近い橋を壊していく。もし壊さなくても大丈夫ならスルーする。答えを見た。

import strutils, sequtils, algorithm

type
    Relation = tuple[a: int, b:int]

let
    NM = stdin.readLine.split.map(parseInt)
    N = NM[0]
    M = NM[1]
    
var
    relations = newSeq[Relation]()
    last_broken_bridge = -1
    ans = 0

for i in 0..<M:
    var
        ab = stdin.readLine.split.map(parseInt)
        r: Relation = (a: ab[0], b: ab[1])
    
    relations.add(r)

relations = relations.sortedByIt(it.b)

for relation in relations:
    if last_broken_bridge < relation.a:
        last_broken_bridge = relation.b - 1
        inc ans

echo ans

辞書順最小

ABC 076 C Dubious Document 2

基本的に?は最終的にaで埋めれば良い。あとできるだけ後ろの方にTをあてはめたほうが辞書順最小になる。T=aaaaaみたいなaだけの文字列ならどこでもいいが、そうじゃなければ前の方にaを入れるべきなので。仮にそうだとしたら全部aでreplaceするのと同じ。

import strutils
 
let
    S = stdin.readLine
    T = stdin.readLine
 
var
    ans = ""
 
for i in 0..S.len()-T.len():
    let substr_S = S[i..i+T.len()-1]
 
    var flag = 0
    for j in 0..<T.len():
        if (substr_S[j] == T[j]) or (substr_S[j] == '?'):
            inc flag
 
    if flag == T.len():
        ans = S[0..<i] & T & S[i+T.len()..<S.len()]
        ans = ans.replace(sub='?', by='a')
 
if ans == "":
    ans = "UNRESTORABLE"
 
echo ans

ABC007 B 辞書式順序

aだったら-1、それ以外ならaを出力するだけ

let A = stdin.readLine

if A.len != 1:
    echo "a"
else:
    if A == "a":
        echo -1
    else:
        echo "a"