when NimMajor <= 0 and NimMinor <= 18: import future else: import sugar # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # from typetraits import arity from sequtils import map, mapIt, newSeqWith, toSeq from strutils import split, parseInt, parseFloat, parseBool, parseEnum, parseBiggestInt when NimMajor == 0 and NimMinor >= 14: from strutils import parseBiggestUInt import macros from terminal import setForegroundColor, ForegroundColor, resetAttributes proc warn(message: string) = when not defined release: stderr.setForegroundColor(fgYellow) stderr.write("注意: ") stderr.resetAttributes stderr.writeLine message when not declared parseBiggestUInt: proc parseBiggestUInt(s: string): uint64 = uint64(parseInt(s)) when not declared SomeFloat: type SomeFloat = float | float64 | float32 when not defined nimHasRunnableExamples: template runnableExamples*(body: untyped) = discard proc parseT(s: string; T: typedesc): auto = ## `parse` 系関数のジェネリック版 ## `T` が `SomeOrdinal | SomeFloat` (subranges を含む) でない場合,そのまま `s` を返す runnableExamples: doAssert parseT("12", int) == 12 doAssert parseT("12", uint) == 12 doAssert parseT("12", int64) == 12 doAssert parseT("12", float32) == 12.0 doAssert parseT("Yes", bool) == true when T is SomeSignedInt: cast[T](parseBiggestInt(s)) elif T is SomeUnsignedInt: cast[T](parseBiggestUInt(s)) elif T is SomeFloat: cast[T](parseFloat(s)) elif T is enum: parseEnum[T](s) elif T is bool: parseBool(s) elif T is char: s[0] else: s proc unpackWithParse*(input: openArray[string]; T: typedesc[tuple]): T = ## 文字列配列を `T` で指定された `tuple` に `parse` しながら変換する runnableExamples: let t = unpackWithParse(@["1", "1", "1", "1", "1"], 4, tuple[a: int8, b: uint32, c: float64, d: bool]) doAssert int8 is t.a.type and t.a == 1 doAssert uint32 is t.b.type and t.b == 1 doAssert float64 is t.c.type and t.c == 1.0 doAssert bool is t.d.type and t.d == true doAssert tuple[a: int8, b: uint32, c: float64, d: bool] is t.type var i = 0 for x in result.fields: if i > input.high: warn "元の配列の長さが " & $T.arity & " 未満だから,一部デフォルト値になってるよ" break x = parseT(input[i], x.type) i.inc result proc input(T: typedesc[string]): string = stdin.readLine proc input(T: typedesc[SomeOrdinal | SomeFloat | char]): auto = input(string).parseT(T) proc input(T: typedesc[seq[string]]): auto = input(string).split proc input(T: typedesc[seq[char]]): auto = toSeq(input(string).items) proc input[E: SomeOrdinal | SomeFloat](T: typedesc[seq[E]]): auto = input(seq[string]).mapIt(it.parseT(E.type)) proc input(T: typedesc[tuple]): auto = input(seq[string]).unpackWithParse(T) proc toTupleType(parTuple: NimNode): NimNode {.compileTime.} = ## `nnkPar` で表現されてる名前付きタプルを `tuple[]` 形式に変換する ## `nnkPar` が名前付きタプルじゃない場合は,そのまま返す runnableExamples: static: doAssert((quote do: (a: int, b: float)).toTupleType == (quote do: tuple[a: int, b: float])) doAssert((quote do: (a, b: int)).toTupleType == (quote do: tuple[a, b: int])) doAssert((quote do: (int, int)).toTupleType == (quote do: (int, int))) doAssert((quote do: ()).toTupleType == (quote do: ())) if parTuple.len == 0 or parTuple.findChild(it.kind == nnkExprColonExpr) == nil: # () or (T, U, ...) result = parTuple else: result = newTree(nnkTupleTy) var identDefs = newTree(nnkIdentDefs) for field in parTuple: if field.kind == nnkIdent: # (a, b, ..., x: T) の a, b, ... 部分 (x 以外) identDefs.add(field) field.copyChildrenTo(identDefs) if field.kind != nnkIdent: # (..., x: T, y: ...) の x: T 部分 identDefs.add(newEmptyNode()) result.add(identDefs) identDefs = newTree(nnkIdentDefs) proc seqInputCall(bracketTree: NimNode): NimNode {.compileTime.} = ## `seq[N, seq[M, ..., [seq[T]]...]]` を `newSeqWith(N, newSeqWith(M, ..., input(seq[T])...))` にする if bracketTree.kind != nnkBracketExpr: case bracketTree.kind: of nnkPar: # x: (Field0: ...) result = newCall("input", bracketTree.toTupleType) else: # x: T result = newCall("input", bracketTree) else: case bracketTree.len: of 2: # seq[N, ... seq[T] ...] の seq[T] if bracketTree[^1].kind == nnkBracketExpr: error("seq[seq[T]] みたいな書き方はできないって言ったでしょ! seq[N, seq[T]] みたいに書き直してっ") result = newCall("input", bracketTree) of 3: # それ以外 (seq[N, ...]) result = newCall("newSeqWith", bracketTree[1], seqInputCall(bracketTree[^1])) else: error("変な入力があるよ") proc appendedProcCallBlocks(procCalls: NimNode; i: int): NimNode = ## `procCalls[i]` の関数呼び出しを ## .. code-block:: Nim ## block: ## var it = procCall(...) ## という形に変換しながらつなげていく ## 最後だけは ## .. code-block:: Nim ## block: ## var it = lastProcCall(...) ## it ## というようにして `it` を返すようにする let it = ident("it") let procCall = procCalls[i] result = newStmtList(quote do: var `it` = `procCall` ) if i == procCalls.len - 1: # 最後の要素だけは it を返すようにする result.add(it) else: result.add(appendedProcCallBlocks(procCalls, i + 1)) result = newBlockStmt(result) proc inputsImpl(pre, post: NimNode): NimNode {.compileTime.} = ## pre で指定された変数に post の結果を入れる # input() 部分の生成 var inputCall: NimNode case pre.kind: of nnkPar: # (x, y, ...): ... result = newTree(nnkVarTuple) pre.copyChildrenTo(result) result.add(newEmptyNode()) case post[0].kind: of nnkPar: # (x, y, ...): (T, T, ...) inputCall = newCall("input", post[0].toTupleType) of nnkTupleTy: # (x, y, ...): tuple[Field0: ...] inputCall = newCall("input", post) else: # (x, y, ...): T var parTupleTy = newTree(nnkPar) for _ in 0.. 1: let it = ident("it") var itStmts = when NimMajor == 0 and NimMinor < 17: newStmtList(quote do: (var `it` = `inputCall`)) # 入力の読み込み else: newStmtList(quote do: (var `it` {.used.} = `inputCall`)) itStmts.add(appendedProcCallBlocks(post, 1)) # 関数の適用 result.add(newTree(nnkStmtListExpr, newBlockStmt(itStmts))) # 結合 else: result.add(inputCall) # 結合 macro inputs*(body: untyped): untyped = ## 入力を受け取る ## 宣言の後に `it` を用いた式を(`y` みたいに用いなくてもいいんだけど)いくつでもかくことができ, ## その返り値が変数の値となる ## 式中で型が変わってもいい(下の例の `u`, `y` とか見たいな感じ) ## ## .. code-block:: Nim ## inputs: ## a: int ## b: string ## c: (x: char, y: float) ## d: tuple[x: char, y: float] ## e: (u, v: BiggestInt) ## f: tuple[u, v: int] ## g: seq[int] ## h: seq[a, seq[int]] ## i: seq[a, (s, t: int)] ## (j, k, l): int ## (m, n): (char, float) ## o: seq[a, string] ## (p): int ## q: seq[int]; it.sorted(system.cmp) ## r: seq[float]; it.sorted(cmp).filterIt(it > 0) ## s: seq[char] ## t: seq[2, seq[a, int]] ## u: string; parseInt(it); abs(-it) ## (_, v): (a: char, b: char) ## (w, x): tuple[a, b: char] ## y: int; "hoge" expectKind(body, nnkStmtList) result = newTree(nnkStmtList) var letSection = newTree(nnkLetSection) for decl in body: case decl[0].kind: of nnkIdent: # x: ... letSection.add(inputsImpl(decl[0], decl[1])) of nnkPar: expectMinLen(decl[0], 1) if decl[0].len == 1: # (x): ... これは x: ... と同じ扱いにしたい letSection.add(inputsImpl(decl[0][0], decl[1])) else: # (x, y, ...): ... letSection.add(inputsImpl(decl[0], decl[1])) else: expectKind(decl[0], {nnkIdent, nnkPar}) result.add(letSection) # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # proc `ceilDiv`*[T](x, y: T): T = x div y + ord(x mod y != 0) proc `//=`*(x: var SomeInteger; y: SomeInteger) = x = x div y proc `%=`*(x: var SomeInteger; y: SomeInteger) = x = x mod y proc `?=`*[T](x: var T; y: T) = x = max(x, y) # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # from sequtils import concat template flatten*[T](s: seq[T]): untyped = when T is seq: flatten(s.concat) else: s proc flatten*[T](s: seq[T]; recLevel: static[Natural]): auto = when recLevel == 0: s elif T is seq: flatten(s.concat, recLevel - 1) else: s # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # proc withIndex*[T](s: openArray[T]): seq[tuple[i: int, v: T]] = (0..s.high).mapIt((it, s[it])) # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # template countIt*[T](a: openArray[T]; pred: untyped): int = var result = 0 for it {.inject.} in items(a): if pred: result.inc result # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # from sequtils import newSeqWith, allIt template newSeqWithImpl[T](lens: seq[int]; init: T; currentDimension, lensLen: static[int]): untyped = when currentDimension == lensLen: newSeqWith(lens[currentDimension - 1], init) else: newSeqWith(lens[currentDimension - 1], newSeqWithImpl(lens, init, currentDimension + 1, lensLen)) template newSeqWith*[T](lens: varargs[int]; init: T): untyped = assert(lens.allIt(it > 0)) newSeqWithImpl(@lens, init, 1, lens.len) # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # template stderrEcho*(x: varargs[string, `$`]) = for v in x: stderr.write(v) stderr.writeLine "" template stderrEcho*[T](x: seq[seq[T]]) = for v in x: stderrEcho v template stderrEcho*(x: seq[string]) = for v in x: stderrEcho v # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # from sequtils import newSeqWith type UnionFind* = object par: seq[int] # x が根のときその木のサイズ, そうじゃないとき par[x] = xの親 UnionFindRef* = ref UnionFind UnionFindTypes = UnionFind | UnionFindRef proc initUnionFind*(n: int): UnionFind = UnionFind(par: newSeqWith(n, -1)) proc newUnionFind*(n: int): UnionFindRef = UnionFindRef(par: newSeqWith(n, -1)) proc findRoot*(this: var UnionFindTypes; x: int): int = if this.par[x] < 0: return x else: this.par[x] = this.findRoot(this.par[x]) return this.par[x] proc find*(this: var UnionFindTypes; x: int): int = this.findRoot(x) proc size*(this: var UnionFindTypes; x: int): int = -this.par[this.findRoot(x)] proc unite*(this: var UnionFindTypes; x, y: int): bool {.discardable.} = var xr = this.findRoot(x) yr = this.findRoot(y) if xr == yr: return false if this.size(xr) < this.size(yr): swap(xr, yr) this.par[xr] += this.par[yr] this.par[yr] = xr return true proc union*(this: var UnionFindTypes; x, y: int): bool {.discardable.} = this.unite(x, y) proc same*(this: var UnionFindTypes; x, y: int): bool = this.findRoot(x) == this.findRoot(y) proc isSame*(this: var UnionFindTypes; x, y: int): bool = this.same(x, y) # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # inputs: N: int bridges: seq[N - 1, tuple[u, v: int]] var uf = newUnionFind(N) for bridge in bridges: uf.union(bridge.u, bridge.v) if N <= 2: echo "Bob" quit() if uf.par.countIt(it < 0) == 1: echo "Bob" else: echo "Alice"