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

はじめに

誰もやってなさそうな言語で競プロをやるシリーズ第6弾¹、AtCoder Beginners Selection の問題²を、プログラミング言語「Kuin」で解いてみました。

競プロを知っている方を想定したKuinの布教記事となります。（解法の詳細はだいぶ端折っているので 本家様 etc.を御覧ください。）

Kuinとは

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

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

ジャッジ方法

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

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

これで動作確認が可能です。
IoのときのようにUbuntuのtimeコマンドを使って実行時間・使用メモリのベンチマークを行いたかったのですが、Windows用に開発されているためか、うまくWSL上で動作させられませんでした³。

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

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

AtCoderではKuinを提出することはできませんが、yukicoderではジャッジしてもらえます。
標準出入力サンプルも用意されているのでこれを参考に解いてみましょう。

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文で行います⁵。
前述の通り代入は::で行います。宣言と同時に代入することも可能です。
cui@inputIntなどで入力、cui@printで出力が行なえます⁶。
\{hoge}で文字列補間が使えます。

ローカルテスト結果

ex1.txt: 16.1933 ms ex2.txt: 16.3697 ms

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

1. ABC 086 A - Product

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などを使います。

ローカルテスト結果

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

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

2. ABC 081 A - Placing Marbles

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のように書きます。ループインデックスはラベル名でアクセスできます。

ローカルテスト結果

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

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

3. ABC 081 B - Shift Only

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はどのループを抜けるのか混乱しないようという設計思想の下、ラベル指定が必須です。）

ローカルテスト結果

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

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

4. ABC 087 B - Coins

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" と等価です。

ローカルテスト結果

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

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

5. ABC 083 B - Some Sums

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の関数を呼び出しています。）

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

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

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

ローカルテスト結果

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

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

6. ABC 088 B - Card Game for Two

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等の関数がちゃんと定義されています（どちらも破壊的に動作します）。

ローカルテスト結果

ex1.txt: 15.6015 ms ex2.txt: 16.1399 ms ex3.txt: 15.735 ms random.txt: 15.6676 ms

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

7. ABC 085 B - Kagami Mochi

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インスタンスを生成し、辞書のキーがuniqueになることを利用して重複を除いた要素数を数えます。^で要素数を取得できるのが地味に便利です。

ローカルテスト結果

ex1.txt: 15.418 ms ex2.txt: 16.8473 ms ex3.txt: 16.1546 ms random.txt: 15.7159 ms

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

8. ABC 085 C - Otoshidama

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とすれば一気にループを抜けて終了できます。

ローカルテスト結果

ex1.txt: 15.3308 ms ex2.txt: 15.2477 ms ex3.txt: 15.6103 ms ex4.txt: 15.8087 ms

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

9. ABC 049 C - Daydream

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

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

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

ローカルテスト結果

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

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

10. ABC 086 C - Traveling

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ライブラリ中に定義されています。

ローカルテスト結果

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

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

その他の機能

せっかくオブジェクト指向言語なのに全くクラスを使っていないのでみんな大好き⁸Union-Find Tree(Disjoint set)を例にクラスの使い方を見てみましょう。
丁度いいところにうってつけの問題ができたのでこちらでテストします。
継承のテストのためにあえて経路圧縮のみのバージョンUnionFindとrank管理も足したバージョンUnionFindFastを定義してみました。

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 (c++)
https://atcoder.jp/contests/practice2/submissions/17254345
AC / 実行時間 242 ms / メモリ 6680 KB

あとがき

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

1. 過去の記事は https://github.com/Yukishita26/abs-solve にまとめてあります。 ↩

2. AtCoder に登録したら次にやること ～ これだけ解けば十分闘える！過去問精選 10 問 ～(@drken さん) にて紹介されている過去問題 ↩

3. timeコマンドから認識されないようで実行時間が0sになってしまう。 ↩

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

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

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

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

8. 諸説あります ↩