LoginSignup
2
1

More than 3 years have passed since last update.

@Mopepe51(雪下)

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

Last updated at Posted at 2020-10-10

はじめに

誰もやってなさそうな言語で競プロをやるシリーズ第6弾1、AtCoder Beginners Selection の問題2を、プログラミング言語「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上で動作させられませんでした3。

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

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文で行います5。
前述の通り代入は::で行います。宣言と同時に代入することも可能です。
cui@inputIntなどで入力、cui@printで出力が行なえます6。
\{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は実装されています7。配列などと同様に、#でからの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

その他の機能

せっかくオブジェクト指向言語なのに全くクラスを使っていないのでみんな大好き8Union-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. 諸説あります ↩

2
1
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
2
1