40代から始める競技プログラミング with Kotlin

はじめに

本記事は、NewsPicks Advent Calendar 2022 の 12/13 公開分の記事になります。

この記事は初心者向けの記事となっております。

kkto81 と申します。主にバックエンドの開発を担当しております。

本日13日は Advent Calendar も中間折り返し地点、と言うことで一息入れて、初心者向けの話題をゆるりと書いてみたいと思います。
タイトルの「40代から始める」は「誰でも気軽に始められる」と置き換えてもらっても大丈夫です。

タイトルの通り、私自身まともに競技プログラミングを始めたのは 40 代からなので、経験を踏まえながら、なるべく初学者の方にも分かりやすく、1 人でも多くの方に学習方法の一つの選択肢としての競技プログラミングを楽しんでもらえればと言う気持ちで書いております。（学習は楽しむことが大事！）

今回は国内では最も有名な競技プログラミングサイトである AtCoder を題材に、NewsPicks のバックエンド開発、Android 開発でも用いられている Kotlin を用いて競技プラグラミングを楽しむための情報をお届けします。

環境構築について

競技プラグラミングを気軽に始めると言う意味ではブラウザさえあれば可能です（練習コンテスト）ので、まずはと言う意味では悪い選択肢ではありません。

※ 練習コンテストで [提出] タブを開き、言語を選択、ソースコードを記載すれば可能。

がしかし、ブラウザでは普段開発で利用するような多くの機能が利用できずにフラストレーションが溜まってしまいます。

以下に記載する手順を行うことで、基本的な作業は全てローカルの好きな IDE 経由で行うことが出来るようになり、競技プラグラミングを楽しむための敷居がグッと下がりますので、これから始める方は是非お試しください。
作業自体は 10 分程度で可能です。（Windows の場合の WSL のインストールを除けば）

環境構築手順（Mac編）

大雑把に、以下の手順で行ないます。

1. atCoder のアカウント作成
2. online-judge-tools のインストール
3. atcoder-cli のインストール
4. kotlin のインストール
5. エイリアスの設定

1. atCoder のアカウント作成

AtCoderから、アカウントの新規登録を行います。

2. online-judge-tools のインストール

online-judge-tools をインストールします。

既に Python（pip3） が使える環境であれば、以下のコマンドのみで可能です。

インストール

pip3 install online-judge-tools

pip3 がインストールされていない場合、以下のサイトなどを参考に、Python 3 系をインストールしてみてください。
https://www.python.jp/install/macos/install_python.html
一例としては、Homebrew を利用して、以下コマンドでインストール可能です。

brew install python3

ログイン

oj login -u ${USERNAME} -p ${PASSWORD} "https://atcoder.jp/"

コマンド例
oj login -u sample_user_name -p sample_password "https://atcoder.jp/"

動作確認

oj login --check "https://atcoder.jp/"

3. atcoder-cli のインストール

atcoder-cli をインストールします。

インストール

npm install -g atcoder-cli

npm がインストールされていない場合、Node.js をインストールする必要があります。
一例としては、Homebrew を利用して、以下コマンドでインストール可能です。(上記公式サイトのインストーラを利用しても可能です。)

brew install node

ログイン

acc login

動作確認

acc session

4. kotlin のインストール

以下（atCoderで利用されているバージョン）から kotlin をダウンロードして、bin にパスを通します。
https://github.com/JetBrains/kotlin/releases/tag/v1.3.71

bin にパスを通すための一般的な方法は、
シェルが zsh の場合、~/.zshrc に、シェルが bash の場合、~/.bash_profile に、以下を追記することです。

コマンド例（パスは kotlin を配置したパスに置き換えてください）

export PATH=/Users/sample_user_name/kotlin/kotlinc/bin:$PATH

また、zsh or bash の確認は、以下コマンドの出力結果で可能です。

echo $SHELL

5. エイリアスの設定

この手順は任意ですが、私が設定しているものをサンプルとしてご紹介します。（利用方法は後ほど）
こちらも利用するシェルによって、~/.zshrc や ~/.bash_profile に設定することで利用することが可能になります。

alias ktest='kotlinc Main.kt && oj t -c "kotlin MainKt" -d ./tests/'
alias ksub='acc submit Main.kt -- -l 4032'
alias kcp='cp ../../template_kotlin/MainTemplate.kt Main.kt'
alias kopen='code Main.kt'

環境構築手順（Windows編）

大雑把に、以下の手順で行ないます。

1. WSL のインストール
2. WSL への接続
3. 環境構築手順（Mac編）と同様の手順実行

1. WSL のインストール

Windowsの環境構築はいくつかの方法がありますが、ここでは一例として、WSL を利用した方法をご紹介します。Windows で Linux 系 OS を動かす環境を構築するのが簡単だと思いますので、ご自身の好きな方法でお試しください。

公式サイト などを参考に、WSL をインストールします。
基本的には、PowerShell で以下コマンドを実行して、再起動後に Ubuntu のユーザ名とパスワードを設定するくらいです。

wsl --install

2. WSL への接続

VSCode を利用します。

図を参考に、WSL の拡張機能をインストールします。

図の左下の部分をクリックすると、WSL に接続することが出来ます。
「新しいWSLウィンドウ」などで接続すると、通常の Linux と同様にシェルが利用可能になります。

3. 環境構築手順（Mac編）と同様の手順実行

ここから先は、上記 3. 環境構築手順（Mac編）と同様となりますので、そちらを参照ください。

使い方

ここでは　AtCoder　の簡単な問題を VSCode を利用して 1 問解くまでのフローを解説します。

私の GitHub リポジトリ にサンプルを載せてありますので、よければ以下で取得して試してみてください。

git clone https://github.com/kkto81/atcoder_sample.git

1. フォルダを開く

上記サンプルフォルダを開きます。

２. 問題番号を確認する

AtCoder の問題番号を取得します。
以下サイトは、過去問がまとまっていて大変便利です。
https://kenkoooo.com/atcoder/#/table/

問題番号は ABC などで始まるもの、例としては 「ABC281」などです。

3. CLI で問題情報を取得する

以下のコマンドで問題情報を取得します（ABC281 の場合の例です）

acc new abc281

そのまま確定（Return or Enter キー）で、最も簡単な A 問題の情報が取得されます。

4. 問題のフォルダに移動する

カレンとディレクトリを問題のフォルダに切り替えます。

cd abc281/a

5. テンプレートをコピーしてファイルを開く

ここでは環境構築で設定した、以下のエイリアスを利用しています。

alias kcp='cp ../../template_kotlin/MainTemplate.kt Main.kt'
alias kopen='code Main.kt'

kcp && kopen

6. ブラウザで問題を読み、回答コードを書く

問題
https://atcoder.jp/contests/abc281/tasks/abc281_a
ここではあえて回答例は載せませんので、是非解いてみてください。
サンプルコードでは変数 n に問題の数値が読み込まれますので、plintln を使って標準出力に回答を出力します。
どうしても分からない場合は、過去問であれば上記問題ページの「提出結果」から、他人のコードも全て参照することが可能です。

7. テストする

以下のコマンドで、tests フォルダ内の sample-xx.in と sample-xx.out の組み合わせて、標準入力/標準出力をテストできます。
問題取得時にサンプルケースがダウンロードされますが、自身で好きなケースを追加することももちろん可能です。

ktest

テストに成功すると、図のように各テストケースに対して、SUCCESS AC が表示されます。

8. 回答を提出する

以下のコマンドで、回答したコードを提出することが出来ます。（環境設定で設定したエイリアスを利用）
実際には、より多くのエッジケースを含めたテストケースが実行され、正解/不正解が判定されます。

ksub

提出して間違いないか確認メッセージが表示されます。
画面の指示に従って「abca」とタイプします。

自動的にブラウザが開き、詳細な結果が表示されます。
もしも AC とならなかった場合、再度コードを修正して再提出可能です。

9. 次の問題を解く

以下のコマンドで次の問題を取得します

cd .. && acc add

次の問題を選択すると、選択した問題の情報が取得可能です。
同様の手順で、引き続き問題を解いて行きます。
（これで基本的な流れは完了です！）

一歩だけ先へ

ここまでの手順を行なっていただければ、問題を解く環境は整ったはずですので、気軽に楽しんでいただく分には問題ないかと思います！

しかし、競技プラグラミングを実際に始めて見ると、

• もっと効率的に問題を解きたい！
• 用意されているライブラリが使いづらい...
• ライバルよりも少しでも先に行くにはどうしたら...

なんて思うこともあるかも知れません。

競技プラグラミングで最も使用されている言語は、C++ で、AtCoderの公式解説も C++ で行われています。
言語にはそれぞれメリットデメリットがあり、あらかじめ用意されているライブラリでも、他の言語にはあるけど、Kotlinには...という場面にも出くわすはずです。

そこでこのセクションでは、Kotlin の機能の一つである拡張関数を利用して、少しだけ効率的に問題を解けるようになるための道標をご紹介します。

拡張関数とは？

Kotlin では、拡張 (extension) の機能を使って、クラスに新しい関数を追加することが出来ます。
【参考】
https://dogwood008.github.io/kotlin-web-site-ja/docs/reference/extensions.html

概念理解のため getFirstValue を実装してみる

このメソッドは理解促進のためのもので、何の役にも立ちません！

fun <T> List<T>.getFirstValue(): T {
    // 空のリストだとエラーになります！
    return this.get(0)
}

// 単純に最初の値が表示されます
println(listOf(1, 2, 3).getFirstValue())
>> 1

C++ の標準関数 lower_bound を実装してみる

例として、誰もが必ずぶつかるであろう二分探索関連問題で利用する、lower_bound を List に追加してみたいと思います。
lower_bound の概要は、「ソート済み範囲に対して指定された要素以上の値が現れる最初の位置のイテレータを取得する。」ですが、今は処理の内容は気にせず、「List に機能(関数）を追加する」部分にだけ着目いただければと思います。

fun <T : Comparable<T>> List<T>.lowerBound(value: T): Int {
    var min = 0
    var max = this.size
    while (min < max) {
        val mid = (min + max) shr 1
        if (this.get(mid) < value) {
            min = mid + 1
        } else {
            max = mid
        }
    }
    return max
}

上記コードをサンプルコード内の、Main.kt 内にコピー＆ペーストしていただくだけで、List に対して lower_bound が利用可能になります。

汎用的な関数であれば、今回のサンプルの例では MainTemplate.kt 内に追加することで、kcp && kopen した段階から利用可能となります。効率化のために作成した関数を追加して行きましょう！

ここでは、> や < などの演算子で比較可能な、Comparable インタフェースを実装した型の List で、lower_bound を利用可能としています。

// 引数に渡された値以上の値を持つ要素の最小の index を返します
println(listOf(1, 1, 2, 2, 2, 3).lowerBound(2))
>> 2
println(listOf(3, 4, 4, 4, 6, 8).lowerBound(5))
>> 4

恐らく今はこんなの何の役に立つんだ！と思うかも知れませんが、すぐに役に立つ日が来るはずです！

まとめと学習ガイド

少し長くなってしまいましたが、ここまでお付き合いいただきましてありがとうございました。
皆さまの快適な競プロライフの一助になれば幸いです。

また、以下におすすめの学習方法などを載せておきますので、もし興味があれば学習してみてください。

• けんちょんさんをフォローする。（競技プログラミングに関する有用な記事をたくさん投稿してくださってます！）
• AtCoder に登録したら次にやること ～ これだけ解けば十分闘える！過去問精選 10 問 ～を読んでみる。
• Kotlin公式の競プロについてのページを読んでみる。
• 世界で闘うプログラミング力を鍛える本　を Amazon でポチってみる。