AtCoderに登録したら解くべき精選過去問10をKuinで解いてみた

# はじめに
誰もやってなさそうな言語で競プロをやるシリーズ第6弾[^6th]、AtCoder Beginners Selection の問題[^abs]を、プログラミング言語「Kuin」で解いてみました。

競プロを知っている方を想定したKuinの布教記事となります。（解法の詳細はだいぶ端折っているので [本家様](https://qiita.com/drken/items/fd4e5e3630d0f5859067) etc.を御覧ください。）

[^abs]: [AtCoder に登録したら次にやること ～ これだけ解けば十分闘える！過去問精選 10 問 ～](https://qiita.com/drken/items/fd4e5e3630d0f5859067)(@drken さん) にて紹介されている過去問題

[^6th]: 過去の記事は https://github.com/Yukishita26/abs-solve にまとめてあります。

# Kuinとは
Kuin はくいなちゃん [Twitter@kuina_ch](https://twitter.com/kuina_ch) が作ったプログラミング言語です。
Windowsでの利用に特化していますが、高速で動作しゲームやソフトウェア作成向けの機能が充実しています。付属のエディタの機能も充実しており、オートコンプリート・コード整形・lintやGUI作成機能も備えています。
コードは機械語にコンパイルできるほか、C++やJavascriptにトランスパイルすることも可能です。

慣習を脇においた「適切さ」を優先するところがあるので他のプログラミング言語に慣れた方は、記号の使い方などで真新しさを感じることもあるかもしれません。（代表的なものとして代入演算子が`::`で等値比較演算子が`=`であったり、要素数演算子`^`やディープコピー演算子`##`などが定義されています）

# ジャッジ方法
kuincl.exeを使ってソースコードをWindows実行ファイル(.exe)にコンパイルすることができます。

```
$ kuincl.exe -i source.kn
$ out.exe < input.txt > output.txt
```

これで動作確認が可能です。
[Ioのときのように](https://qiita.com/Mopepe51/items/1dbc7edcfe339a9ed284#%E3%82%B8%E3%83%A3%E3%83%83%E3%82%B8%E6%96%B9%E6%B3%95)Ubuntuのtimeコマンドを使って実行時間・使用メモリのベンチマークを行いたかったのですが、Windows用に開発されているためか、うまくWSL上で動作させられませんでした[^wsl]。

[^wsl]: timeコマンドから認識されないようで実行時間が0sになってしまう。

このため今回はすべてコマンドプロンプト上でPoweshellの`Measure-Command`を利用して実行時間だけ計測しています。
kuinを展開したフォルダ直下にソースコードと`testcases/<hoge>/in/<fuga>.txt`の形でテストケースを用意し、以下のようなバッチで各問題の実行時間を計測しました[^bat]。（メモリ使用量の測定はいまいちよくわからなかったので今回は測定していません。）

[^bat]: バッチ変数をPowershellに渡す方法は次の記事を参考にしました。https://qiita.com/nya193/items/c93ed6624e60acbb297c 使用しているkuinclのコンパイラオプションは、-i:インプットファイルの指定、-o:出力ファイル名の指定、-q:詳細出力の抑制(無いとコンパイル時間等が出力される)。

```bash:tester.bat

@echo off
for /l %%I in (0,1,10) do (
  echo %%I >> resout.txt
  kuincl.exe -i _%%I.kn -o %%I.exe -q
  for %%F in (./testcases/%%I/in/*.txt) do (
    set COM="(Measure-Command {./%%I.exe}).TotalSeconds"
    echo %%F >> resout.txt
    powershell -C %COM% < ./testcases/%%I/in/%%F >> resout.txt
  )
)
```

また、C++に翻訳したコードを生成することもできるので、これをジャッジに提出して正誤判定を行います。

```
$ kuincl.exe -i source.kn -e cpp
```

なお生成されるコードは非常に長い(Hello worldでも56kBほど)のでこれは本記事中には載せず、提出へのリンクのみを貼っておきます。

# 解法
## 0. [practice contest A - Welcome to AtCoder](https://atcoder.jp/contests/abs/tasks/practice_1)
AtCoderではKuinを提出することはできませんが、yukicoderではジャッジしてもらえます。
[標準出入力サンプルも用意されている](https://yukicoder.me/wiki/stdio)のでこれを参考に解いてみましょう。

```js

func main()
	var a: int :: cui@inputInt()
	var b: int :: cui@inputInt()
	var c: int :: cui@inputInt()
	var s: []char :: cui@inputStr()
	do cui@print("\{a + b + c} \{s}\n")
end func
```

変数定義は`var`文、式の実行は`do`文で行います[^teisuu]。
前述の通り代入は`::`で行います。宣言と同時に代入することも可能です。
`cui@inputInt`などで入力、`cui@print`で出力が行なえます[^cui]。
`\{hoge}`で文字列補間が使えます。

[^cui]: KuinはGUI用の機能も充実しているのでCUI用の出入力などの機能はライブラリ`cui`にまとめられています。

[^teisuu]: 定数定義文`const`も存在します。ここでの定数とはコンパイル時に値が決定できるもので、他の言語での「書き換え不能変数」とは違うので上の例などでは使えません。

<details><summary>ローカルテスト結果</summary><div>ex1.txt: 16.1933 ms
ex2.txt: 16.3697 ms
</div></details>

提出結果(c++)
https://atcoder.jp/contests/abs/submissions/17189264
AC / 実行時間 9 ms / メモリ 4008 KB

## 1. [ABC 086 A - Product](https://atcoder.jp/contests/abs/tasks/abc086_a)

```js

func main()
	var a: int :: cui@inputInt()
	var b: int :: cui@inputInt()
	do cui@print((a % 2 = 0 | b % 2 = 2) ?("Even\n", "Odd\n"))
end func
```

条件演算子 `hoge ?(fuga, piyo)`が使えます。
Cライク言語ユーザーは等値比較演算子`=`や論理和`|`（ついでに論理積`&`も）で記号を2つ重ねないことに注意が必要です。ビット演算はビット型(`bit8`～`bit64`)に定義された`.and`、`.or`、`.xor`などを使います。

<details><summary>ローカルテスト結果</summary><div>0_000.txt: 16.0082 ms
0_001.txt: 15.5848 ms
1_002.txt: 16.1465 ms
1_003.txt: 15.5806 ms
1_004.txt: 15.2418 ms
1_005.txt: 15.0334 ms
1_006.txt: 16.4136 ms
</div></details>

提出結果(c++)
https://atcoder.jp/contests/abs/submissions/17181226
AC / 実行時間 5 ms / メモリ 4064 KB

## 2. [ABC 081 A - Placing Marbles](https://atcoder.jp/contests/abs/tasks/abc081_a)

```js

func main()
	var s: []char :: cui@inputStr()
	var r: int :: 0
	for i(0, ^s - 1)
		if(s[i] = '1')
			do r :+ 1
		end if
	end for
	do cui@print("\{r}\n")
end func
```

文字列はcharの配列として扱われています。配列の長さは要素数演算子`^`で取得できます。
演算とともに代入を行う`:+`なども使用できます。

(式ではない)if文は`if(<条件式>) …… end if`のように書きます。
ループはforブロック`for <ラベル名>(<初期値>, <終値>) …… end for`のように書きます。ループインデックスはラベル名でアクセスできます。

<details><summary>ローカルテスト結果</summary><div>00_example_01.txt: 15.5508 ms
00_example_02.txt: 15.5958 ms
01.txt: 15.1361 ms
02.txt: 15.4223 ms
03.txt: 14.896 ms
04.txt: 15.388 ms
05.txt: 16.2408 ms
06.txt: 15.8458 ms
</div></details>

提出結果(c++)
https://atcoder.jp/contests/abs/submissions/17189336
AC / 実行時間 9 ms / メモリ 4008 KB

## 3. [ABC 081 B - Shift Only](https://atcoder.jp/contests/abs/tasks/abc081_b)

```js

func main()
	var n: int :: cui@inputInt()
	var a: []int :: #[n]int
	for i(0, n - 1)
		do a[i] :: cui@inputInt()
	end for
	var r: int :: 0
	while loop(true)
		for i(0, n - 1)
			if(a[i] % 2 = 0)
				do a[i] :/ 2
			else
				break loop
			end if
		end for
		do r :+ 1
	end while
	do cui@print("\{r}\n")
end func
```

3行目の`#`はインスタンス生成演算子です。`#[n]int`で長さ $n$ の配列が生成されます。一般に`#<クラス名>`でクラスのコンストラクタが呼び出されます。
配列はいつも通り`[]`でインデックスアクセスができます。

whileもforやifと同様に「ブロック」です。ブロックにはラベルを付与することができ、`break <ラベル名>`で指定したループを抜けることができます。多重ループを抜けるときなどに便利です。（というより`break`はどのループを抜けるのか混乱しないようという設計思想の下、ラベル指定が必須です。）

<details><summary>ローカルテスト結果</summary><div>1.txt: 15.0416 ms
2.txt: 15.8243 ms
3.txt: 16.3574 ms
4.txt: 15.2948 ms
5.txt: 16.2805 ms
6.txt: 15.0073 ms
7.txt: 15.0716 ms
sample1.txt: 14.871 ms
sample2.txt: 16.3661 ms
sample3.txt: 15.2757 ms
</div></details>

提出結果(c++)
https://atcoder.jp/contests/abs/submissions/17189348
AC / 実行時間 6 ms / メモリ 4044 KB

## 4. [ABC 087 B - Coins](https://atcoder.jp/contests/abs/tasks/abc087_b)

```js

func main()
	var a: int :: cui@inputInt()
	var b: int :: cui@inputInt()
	var c: int :: cui@inputInt()
	var x: int :: cui@inputInt()
	var r: int :: 0
	for i(0, a)
		for j(0, b)
			for k(0, c)
				if(500 * i + 100 * j + 50 * k = x)
					do r :+ 1
				end if
			end for
		end for
	end for
	do cui@print(r.toStr() ~ "\n")
end func
```

これまでに出たループや条件分岐で解くことができますね。

文字列の結合には配列連結演算子`~`を用います（※文字列は`char`の配列です）。
文字列埋め込み `"hoge\{fuga}piyo"` はコンパイル時に `"hoge" ~ (fuga).toStr() ~ "piyo"` に展開されるようになっているので `"\{r}\n"` は `r.toStr() ~ "\n"` と等価です。

<details><summary>ローカルテスト結果</summary><div>01.txt: 15.152 ms
02.txt: 16.3965 ms
03.txt: 16.9342 ms
04.txt: 15.6138 ms
05.txt: 15.4071 ms
06.txt: 15.896 ms
07.txt: 15.8762 ms
08.txt: 15.8977 ms
09.txt: 15.8002 ms
10.txt: 15.8662 ms
sample01.txt: 18.0017 ms
sample02.txt: 16.0997 ms
sample03.txt: 15.2114 ms
</div></details>

提出結果(c++)
https://atcoder.jp/contests/abs/submissions/17189355
AC / 実行時間 7 ms / メモリ 4104 KB

## 5. [ABC 083 B - Some Sums](https://atcoder.jp/contests/abs/tasks/abc083_b)

```js

func ketanowa(n: int): int
	var r: int :: 0
	while(n > 0)
		do r :+ n % 10
		do n :/ 10
	end while
	ret r
end func

func main()
	var n: int :: cui@inputInt()
	var a: int :: cui@inputInt()
	var b: int :: cui@inputInt()
	var r: int :: 0
	for i(0, n)
		var k: int :: @ketanowa(i)
		if(a <= k & k <= b)
			do r :+ i
		end if
	end for
	do cui@print("\{r}\n")
end func
```

各位の桁の和を求める関数`ketanowa`をグローバルに定義しています。
今までも`main`の定義をしていましたが、同様に`func <関数名>() …… end func`で関数を定義できます。引数がある場合はカッコの中に変数名と型を、戻り値がある場合はカッコの後に型を適宜追加します（なお、戻り値は1つしか置けないため複数の値を返すにはクラスを作るか参照渡しで変数に格納して返します）。戻り値は`ret`文で返します。
グローバルに定義したメンバーは名前空間の識別子`@`をつけてアクセスします。（実は、これまでに出てきている`cui@print`なども組み込みライブラリ`cui`の関数を呼び出しています。）

関数は関数の中でも定義可能で、上の例は以下のように書くことも可能です。

```js:ローカル呼び出しでは@は不要

func main()
	func ketanowa(n: int): int
		var r: int :: 0
		while(n > 0)
			do r :+ n % 10
			do n :/ 10
		end while
		ret r
	end func
	
	var n: int :: cui@inputInt()
	var a: int :: cui@inputInt()
	var b: int :: cui@inputInt()
	var r: int :: 0
	for i(0, n)
		var k: int :: ketanowa(i)
		if(a <= k & k <= b)
			do r :+ i
		end if
	end for
	do cui@print("\{r}\n")
end func
```

<details><summary>ローカルテスト結果</summary><div>01.txt: 15.642 ms
02.txt: 15.5034 ms
03.txt: 15.7701 ms
04.txt: 17.3547 ms
05.txt: 15.6381 ms
06.txt: 14.809 ms
07.txt: 15.4684 ms
08.txt: 15.407 ms
s1.txt: 16.4384 ms
s2.txt: 15.5856 ms
s3.txt: 15.5003 ms
</div></details>

提出結果(c++)
https://atcoder.jp/contests/abs/submissions/17189361
AC / 実行時間 7 ms / メモリ 4056 KB

## 6. [ABC 088 B - Card Game for Two](https://atcoder.jp/contests/abs/tasks/abc088_b)

```js

func main()
	var n: int :: cui@inputInt()
	var as: []int :: #[n]int
	for i(0, n - 1)
		do as[i] :: cui@inputInt()
	end for
	do as.sort()
	do as.reverse()
	var alice: int :: 0
	var bob: int :: 0
	for i(0, n - 1)
		if(i % 2 = 0)
			do alice :+ as[i]
		else
			do bob :+ as[i]
		end if
	end for
	do cui@print("\{alice - bob}\n")
end func
```

配列には`.sort`や`.reverse`等の関数がちゃんと定義されています（どちらも破壊的に動作します）。

<details><summary>ローカルテスト結果</summary><div>ex1.txt: 15.6015 ms
ex2.txt: 16.1399 ms
ex3.txt: 15.735 ms
random.txt: 15.6676 ms
</div></details>

提出結果(c++)
https://atcoder.jp/contests/abs/submissions/17189366
AC / 実行時間 8 ms / メモリ 3936 KB

## 7. [ABC 085 B - Kagami Mochi](https://atcoder.jp/contests/abs/tasks/abc085_b)

```js

func main()
	var n: int :: cui@inputInt()
	var dic: dict<int, int> :: #dict<int, int>
	for i(0, n - 1)
		do dic.add(cui@inputInt(), 1)
	end for
	do cui@print("\{^dic}\n")
	
end func
```

組み込みに`set`はありませんが、`dict`は実装されています[^dict]。配列などと同様に、`#`でからのdictインスタンスを生成し、辞書のキーがuniqueになることを利用して重複を除いた要素数を数えます。`^`で要素数を取得できるのが地味に便利です。

[^dict]: 二分木による順序付き辞書の実装のようです。https://twitter.com/kuina_ch/status/934744578623549440

<details><summary>ローカルテスト結果</summary><div>ex1.txt: 15.418 ms
ex2.txt: 16.8473 ms
ex3.txt: 16.1546 ms
random.txt: 15.7159 ms
</div></details>

提出結果(c++)
https://atcoder.jp/contests/abs/submissions/17189377
AC / 実行時間 7 ms / メモリ 4096 KB

## 8. [ABC 085 C - Otoshidama](https://atcoder.jp/contests/abs/tasks/abc085_c)

```js

func main()
	var n: int :: cui@inputInt()
	var y: int :: cui@inputInt()
	var r: []char :: "-1 -1 -1\n"
	for i(0, n)
		for j(0, n - i)
			var k: int :: n - i - j
			if(10000 * i + 5000 * j + 1000 * k = y)
				do r :: "\{i} \{j} \{k}\n"
			end if
		end for
	end for
	do cui@print(r)
end func
```

計算量の評価としては変わらないので $i$,$j$ を全部探索して最後に見つけたものを出力するようにしていますが、最初に見つけたところで終わりにしても大丈夫ですね。すなわち`do r :: "\{i} \{j} \{k}\n"`の後に`break i`とすれば一気にループを抜けて終了できます。

<details><summary>ローカルテスト結果</summary><div>ex1.txt: 15.3308 ms
ex2.txt: 15.2477 ms
ex3.txt: 15.6103 ms
ex4.txt: 15.8087 ms
</div></details>

提出結果(c++)
https://atcoder.jp/contests/abs/submissions/17189384
AC / 実行時間 12 ms / メモリ 4044 KB

## 9. [ABC 049 C - Daydream](https://atcoder.jp/contests/abs/tasks/arc065_a)

```js

func main()
	var s: []char :: cui@inputStr()
	do s.reverse()
	var i: int :: 0
	while(i < ^s)
		if(i + 5 <= ^s & s.sub(i, 5) = "maerd")
			do i :+ 5
		elif(i + 7 <= ^s & s.sub(i, 7) = "remaerd")
			do i :+ 7
		elif(i + 5 <= ^s & s.sub(i, 5) = "esare")
			do i :+ 5
		elif(i + 6 <= ^s & s.sub(i, 6) = "resare")
			do i :+ 6
		else
			do cui@print("NO\n")
			ret
		end if
	end while
	do cui@print("YES\n")
end func
```

部分列を取得するには`.sub(<最初の要素>, <要素数>)`とします。
なお、`.reverse()`は破壊的変更なので`"dream".reverse()`のようにリテラルに適用することはできないようです。

提出結果(c++)
https://atcoder.jp/contests/abs/submissions/17249024
AC / 実行時間 19 ms / メモリ 4304 KB

置換で解くこともできます。若干実行時間が伸びました。

```js

func main()
	var s: []char :: cui@inputStr()
	do s :: s.replace("eraser", "!")
	do s :: s.replace("erase", "!")
	do s :: s.replace("dreamer", "!")
	do s :: s.replace("dream", "!")
	do s :: s.replace("!", "")
	do cui@print((s = "" ?("YES", "NO")) ~ "\n")
end func
```

<details><summary>ローカルテスト結果</summary><div>subtask0_0.txt: 15.7474 ms
subtask0_1.txt: 15.7052 ms
subtask0_2.txt: 15.5059 ms
subtask1_0.txt: 26.8615 ms
subtask1_1.txt: 27.3676 ms
subtask1_10.txt: 27.3824 ms
subtask1_11.txt: 27.0066 ms
subtask1_12.txt: 26.6381 ms
subtask1_13.txt: 27.8573 ms
subtask1_14.txt: 26.9656 ms
subtask1_15.txt: 29.2764 ms
subtask1_2.txt: 26.1822 ms
subtask1_3.txt: 26.7093 ms
subtask1_4.txt: 26.1842 ms
subtask1_5.txt: 27.0042 ms
subtask1_6.txt: 26.8214 ms
subtask1_7.txt: 26.9937 ms
subtask1_8.txt: 27.4786 ms
subtask1_9.txt: 26.8033 ms
</div></details>

提出結果(c++)
https://atcoder.jp/contests/abs/submissions/17189389
AC / 実行時間 189 ms / メモリ 4504 KB

## 10. [ABC 086 C - Traveling](https://atcoder.jp/contests/abs/tasks/arc089_a)

```js

func main()
	var n: int :: cui@inputInt()
	var pre_t: int :: 0
	var pre_x: int :: 0
	var pre_y: int :: 0
	var f: bool :: true
	for i(0, n - 1)
		var t: int :: cui@inputInt()
		var x: int :: cui@inputInt()
		var y: int :: cui@inputInt()
		var dt: int :: t - pre_t
		var dl: int :: (x - pre_x).abs() + (y - pre_y).abs()
		if(dl > dt | dl % 2 <> dt % 2)
			do f :: false
		end if
		do pre_t :: t
		do pre_x :: x
		do pre_y :: y
	end for
	do cui@print((f ?("Yes", "No")) ~ "\n")
end func
```

`.abs()`や`.sign()`など、数学的な関数の一部は数値型に直接定義されています。
その他三角関数などは`lib`ライブラリ中に定義されています。

<details><summary>ローカルテスト結果</summary><div>0_000.txt: 15.3021 ms
0_001.txt: 15.669 ms
0_002.txt: 15.408 ms
1_003.txt: 15.8834 ms
1_004.txt: 15.1959 ms
1_005.txt: 15.4048 ms
1_006.txt: 17.8164 ms
1_007.txt: 15.1639 ms
1_008.txt: 15.3718 ms
1_009.txt: 16.0719 ms
1_010.txt: 15.4211 ms
1_011.txt: 17.1718 ms
1_012.txt: 15.4525 ms
</div></details>

提出結果(c++)
https://atcoder.jp/contests/abs/submissions/17189677
AC / 実行時間 91 ms / メモリ 4004 KB


# その他の機能
せっかくオブジェクト指向言語なのに全くクラスを使っていないのでみんな大好き[^uft]Union-Find Tree(Disjoint set)を例にクラスの使い方を見てみましょう。
丁度いいところに[うってつけの問題](https://atcoder.jp/contests/practice2/tasks/practice2_a)ができたのでこちらでテストします。
継承のテストのためにあえて経路圧縮のみのバージョン`UnionFind`とrank管理も足したバージョン`UnionFindFast`を定義してみました。

[^uft]: 諸説あります

```js:UnionFindTree.kn

class UnionFind()
	var tree: []int
	var n: int
	+func initialize(n: int)
		do me.n :: n
		do me.tree :: #[me.n]int
		for i(0, me.n - 1)
			do me.tree[i] :: i
		end for
	end func
	+func root(a: int): int
		if(me.tree[a] = a)
			ret a
		else
			do me.tree[a] :: me.root(me.tree[a])
			ret me.tree[a]
		end if
	end func
	+func is_same(a: int, b: int): bool
		ret me.tree[me.root(a)] = me.root(b)
	end func
	+func unite(a: int, b: int)
		do me.tree[me.root(a)] :: me.root(b)
	end func
end class


func main()
	class UnionFindFast(@UnionFind)
		var rank: []int
		+*func initialize(n: int)
			do super(me, n)
			do me.rank :: #[me.n]int
			for i(0, me.n - 1)
				do me.rank[i] :: 1
			end for
		end func
		+*func unite(a: int, b: int)
			var ra: int :: me.root(a)
			var rb: int :: me.root(b)
			if(ra = rb)
				ret
			elif(me.rank[ra] < me.rank[rb])
				do me.tree[ra] :: rb
			else
				do me.tree[rb] :: ra
				if(me.rank[ra] = me.rank[rb])
					do me.rank[ra] :+ 1
				end if
			end if
		end func
	end class
	
	var n: int :: cui@inputInt()
	var q: int :: cui@inputInt()
	var uf: UnionFindFast :: #UnionFindFast
	do uf.initialize(n)
	for(0, q - 1)
		var t: int :: cui@inputInt()
		var u: int :: cui@inputInt()
		var v: int :: cui@inputInt()
		if(t = 0)
			do uf.unite(u, v)
		else
			do cui@print("\{uf.is_same(u, v) ?(1, 0)}\n")
		end if
	end for
end func
```

+ クラスの定義は`class <クラス名>(<継承元>) …… end class` (継承元を与えない場合はデフォルトで`kuin@Class`を継承する)
+ グローバルでもローカルでも定義可能。入れ子もOK。関数と同様、グローバルで定義したものは`@`で呼び出す。
+ publicなメンバーは`+`をつける。何もつけないとprivateになる。
+ 自分のメンバーにアクセスするときは自分のインスタンス`me`から。
+ 関数をオーバーライドするときは`*`をつける。
+ オーバーライド元の関数は `super(me, <引数1>, …)`で実行できる。
+ コンストラクタは`ctor`。これをオーバーライドすることで初期化処理を定義できる。(オーバーロードはできないので今回は不使用。)
+ コメントは`;`または`{}`。`;`は行頭でしか使えない。`{}`は入れ子にすることができる。

設問はUnionFindの機能そのまま、クエリごとにuniteまたはis_sameの判定を行うというものです。

提出結果 to [AtCoder Library Practice Contest A - Disjoint Set Union](https://atcoder.jp/contests/practice2/tasks/practice2_a) (c++)
https://atcoder.jp/contests/practice2/submissions/17254345
AC / 実行時間 242 ms / メモリ 6680 KB

# あとがき
以上、Kuinで「精選過去問10」+α を解いてみました。正誤判定についてはコンパイラを全面的に信用することにしてC++版の提出で代えさせて頂きましたが、とりあえず通っているので良しということにします。
記号の使い方なんかは結構好み(等値比較が`=`なところとか)なので機会があればまた使っていきたいと思います。