GoでAtCoderをやる話

この記事は、and factory.inc Advent Calendar 2021の 15日目 の記事です。
昨日は、@hagmonさんの「【Flutter】アプリ起動時に未処理トランザクションを処理する方法」でした。

追記 (2023/12/06)

やるに当たってどんな関数を作っておくと良いかという視点で別の記事を書きました。こちらも参考になれば幸いです。
Goで競技プログラミングをするときに作っておくと便利な関数

追記 (2022/05/21)

手順について、今はより効率の良いやり方で進めているので書き直しました。

概要

この記事では業務とは離れてますが、趣味で取り組んでいるAtCoderの話についてまとめてみたいと思います。始めてから半年ほどで、最近やっと水色になれました！この記事ではどんな感じでやっているか、水色になるまで、やって良かったことなどを雑多にまとめていきます。

https://atcoder.jp/users/GoSagawa

なぜ今更競技プログラミングを始めたか

AtCoder自体は社内勉強会で皆で一回遊んだことがあり、存在自体は二年前くらいに知っていました。
ではなぜ今更かというと、正直半年前何でやり始めたかあまり覚えていないのですが、コロナ下で家でできる余暇をなんか一つ増やすかくらいな軽い気持ちであったように思います。数回やっていくうちに解けないのが悔しかったのと、面白くなってきたのとでハマっていった感じです。

どんな感じでやっているか

言語はGoで書いています。C++やPythonを使うのがおそらくベストなのではと思いつつ、Goで書くのが楽しいのでGoで書いてます。エディタはVimを使っています。すべてコンソール上で完結しておりtmuxで画面分割してやっています。実行やGitの操作含めて全部Vim内で完結できそそうなので最終的にはそうした方が早そうと思いつつ、普段の業務スタイルがこうだから（業務だと全てをVim内で完結させるのは大変)このようなスタイルになっています。

手順は以下のような感じです

1. ojを利用し、テストケースを取得。
2. AtCoderで問題を読む
3. 実装
4. ojでテスト
5. ojで提出
6. ファイルの移動とGitComit、テンプレートファイルの準備
7. 次の問題へ
   といった流れになります

実際に見ていただいた方が早いかと思うのですが、こんな感じです。
ABC231のCを解いてます。

進めるにあたってのTips

標準入力

まずプログラムを実行させる際には標準入力を行う必要があるのですが、これは手でやるのは実行するたびにコピペを強いられるので煩雑です。init関数で通常は標準入力であるものの、ローカルで実行時にはオプションを渡すことでinputというファイルをから取得するようにしています。
inputのファイルはojでテストケースをダウンロードしたときに一つ目のケースが入るようにしています。

func init() {
	sc.Buffer([]byte{}, math.MaxInt64)
	sc.Split(bufio.ScanWords)
	if len(os.Args) > 1 && os.Args[1] == "i" {
		b, e := ioutil.ReadFile("./input")
		if e != nil {
			panic(e)
		}
		sc = bufio.NewScanner(strings.NewReader(strings.Replace(string(b), " ", "\n", -1)))
	}
}

ホットリロードと他の言語の利用

画面の右下のペインではmain.goやinputのファイルを書き換えたときにホットリロードされるようになっていますが、これはシンプルにentrを使って以下のようなコマンドで実現しています。コマンド類は全てMakefileからシェルを呼び出すようにしており、内部では.modeというファイルから言語を判断して処理を分けています。現状はGoでもC++でも書けるようにしています。

shell/entr.sh

#!/bin/bash
mode=$(cat ./.mode)
j
if test "$mode" = "go" ; then
  find ./ -maxdepth 1  -name main.go -or -name input | entr -c ./shell/run.sh
fi

if test "$mode" = "cpp"; then
  find ./ -maxdepth 1  -name main.cpp -or -name input | entr -c ./shell/run.sh
fi

shell/run.sh

#!/bin/bash

mode=$(cat ./.mode)

if test "$mode" = "go" ; then
  go build main.go
  ./main i
fi

if test "$mode" = "cpp"; then
  g++ -D=__LOCAL -o main main.cpp
  ./main
fi

テストと提出

基本的にojの機能でテストと提出をするだけです。ソースをコピペして提出するのは地味に面倒なのでojを活用すると楽です。
なおGoをテストするときにはoj t -c "go run main.go"とせずにホットリロード時にビルドされたものを利用しています。こうしないとテスト時に毎回ビルドすることになるのでもたつきます。提出は通常だとダウンロードした問題をそのままojが送信してくれますが、URLも指定して送れるようににもしています。

shell/test.sh

#!/bin/bash

mode=$(cat ./.mode)
sendfile=""

if test "$mode" = "go" ; then
  oj t -c "./main"
fi

if test "$mode" = "cpp"; then
  g++ main.cpp; oj t 
fi

shell/submit.sh

#!/bin/bash

mode=$(cat ./.mode)

if test "$mode" = "go" ; then
  oj s main.go
fi

if test "$mode" = "cpp"; then
  oj s main.cpp
fi

shell/submiturl.sh

#!/bin/bash

mode=$(cat ./.mode)
echo -n URL?
read q

if test "$mode" = "go" ; then
  oj s $q main.go 
fi

if test "$mode" = "cpp"; then
  oj s $q main.cpp 
fi

Makefile

内容が重複していますがこれらのコマンドを駆使してます。

// Goを利用する
go:
	echo "go" > .mode

// C++を利用する
cpp:
	echo "cpp" > .mode

// 実行する
run:
	./shell/run.sh

// inputから入力を取らず標準入力で実行する。主にインタラクティブな問題に利用。
runwi:
	./shell/runwi.sh

// ベースファイルの取得
base:
	./shell/base.sh

// ファイルの移動
m:
	./shell/movefile.sh

// コンテスト名を指定してファイルを移動
mc:
	./shell/movefilecontest.sh

// entrでのホットリロード
entr:
	./shell/entr.sh

// contestのファイルにあるコンテストからダウンロード
d:
	./shell/download.sh

// URLからダウンロード
du:
	./shell/downloadurl.sh

// テスト
t:
	./shell/test.sh

// 提出
s:
	./shell/submit.sh

// URLで提出
su:
	./shell/submiturl.sh

// AtCoderへログイン
login:
	oj login https://atcoder.jp

GitHubの活用

私がAtCoderをやるときの全てのセットはgithub.com/gosagawa/atcoderにあります。なのでここからresultとか不要なものを消してもらえれば私と全く同じようにAtCoderをやることが可能です。問題を解き終わった際にはコマンドで次のテンプレートを用意すると同時にCommitしているのでコードが全て残ります。Gitで全部ひとまとめにしておくことにより、途中の状態を残したり、過去の自分のソースをGrepできたりして便利です。コンテスト中はもちろんpushしないようにしています。

フォルダ構成としては、以下のようになっています。

_example/　 ... 頻繁には使わないが、同じような問題が出たときに参考になりそうなソース
_result/    ... 今までの結果全て
_template/  ... 毎回利用するテンプレートファイル
shell/      ... Makefileの実行用のシェル
contest     ... _resultに保存する用の今参加しているコンテスト名、Gitにはコミットしません
input       ... インプット用のファイル、Gitにはコミットしません
main.go     ... 解いている問題のファイル、Gitにはコミットしません
Makefile    ... 実行であったり、解けたい問題を移動するコマンド
movefile.sh ... ファイルを移動してGitコミットするシェル

関数、コメント整備

頻繁に利用するものは全て関数としてまとめてます。ここを直していくのは自分の道具箱を作るようで非常に楽しい作業ですね。簡単な問題については用意しておいた関数を引っ張ってくるだけで一瞬で片付いたりします。以下ファイルで随時更新して行っていますが、数例ピックアップします。
https://github.com/gosagawa/atcoder/blob/master/_template/main.go

二分探索

以下のような中身になっています。

func bs(ok, ng int, f func(int) bool) int {
	if !f(ok) {
		return -1
	}
	if f(ng) {
		return ng
	}
	for abs(ok-ng) > 1 {
		mid := (ok + ng) / 2

		if f(mid) {
			ok = mid
		} else {
			ng = mid
		}
	}

	return ok
}

サンプルであげたABC231 Cは二分探索で解ける問題ですが、配列で特定の数値以上、以下、未満などを探す処理はよく出るので以下の関数を作っていて、Gif画像内でも実際に使ってます。

// find x of sl[x] < v. return -1 if no lowerbound found
func lowerBound(v int, sl []int) int {
	if len(sl) == 0 {
		panic("slise len is zero")
	}
	idx := bs(0, len(sl)-1, func(c int) bool {
		return sl[c] < v
	})
	return idx
}

// find x of v < sl[x]. return len(sl) if no upperbound found
func upperBound(v int, sl []int) int {
	if len(sl) == 0 {
		panic("slise len is zero")
	}
	idx := bs(0, len(sl)-1, func(c int) bool {
		return sl[c] <= v
	})
	return idx + 1
}

グラフとダイクストラ

グラフのインプットを取得してダイクストラをやるまでです。木とかグラフを扱う時はだいたいここの前半部分をコピーして調整するだけで済みます。

	v, e := ni2()
	edges := make([][]edge, v)

	for i := 0; i < e; i++ {
		s, t, c := ni3()
		s--
		t--
		edges[s] = append(edges[s], edge{to: t, cost: c})
		edges[t] = append(edges[t], edge{to: s, cost: c})
	}

	graph := newgraph(v, edges)
	dist := graph.dijkstra(0)

数字と文字の変換

数字と文字の変換は頻発に使う割には、strconv.Atoiでエラー処理をするのが毎回面倒くさいのでラップしてしまっています。

func atoi(s string) int {
	i, e := strconv.Atoi(s)
	if e != nil {
		panic(e)
	}
	return i
}

func itoa(i int) string {
	return strconv.Itoa(i)
}

遅延評価セグメント木

最初理解して書くまで苦労しましたが、作った後は汎用性が高くて便利です。範囲を更新する系の問題で重宝しています。

s := newlazystree(n,stmax,stadd)
s.set(i,x)
s.add(i,x)
s.rc(l,r,x)
result1 := s.query(l,r)
result2 := s.findrightest(l,r,x)
result3 := s.findlefttest(l,r,x)

水色になるまでやった事

今までのプログラミング経験から茶色まではすっといきましたが、そこから先はちゃんと勉強しないと難しいのではと思います。基本的に以下の記事が非常にわかりやすくまとめられており、これ通りに進めるのが良いのではと思います。まずはおすすめの100問を解き切りました。

レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】

合わせて以下の二つの本を使いながら理解を深めていきました。

問題解決力を鍛える！アルゴリズムとデータ構造 (ＫＳ情報科学専門書)

最初の100問を解いていくに当たっては以下の書籍が非常にわかりやすくよかったです。本と読み比べながら一つ一つ概念を理解して進めていきました。この本書いている内容は7,8割理解できているかと思います。理解できているというのは読めば納得できるというレベルで、全部の参考問題を解き切のはやってませんがそれも力がつきそうに思います。私は最初から理解しつつ全て読み切るという使い方をしました。

プログラミングコンテストチャレンジブック [第2版]　～問題解決のアルゴリズム活用力とコーディングテクニックを鍛える～

通称蟻本と言われる有名なプログラミングコンテストチャレンジブックはヘビーで初心者がいきなり読むと辛いのではと思います。おそらく理解できているのは50%くらいでなんでそうなるのかがわからんとつまづくところも多いです。この本を完璧に理解し切るのが次のステップな気がしています。この本は必要となるアルゴリズムが出て来た時にしっかりそこの部分を読み込んで理解するという使い方をしています。

100問を解いた後は以下に取り込みました。

競プロ典型 90 問

何を使えばいいか大方分かっている最初の100問と比較してこちらは非常に歯応えがありためになりました。
これをやった記録は以下個人ブログにまとめています。

競プロ典型 90 問をGoで解く

後は時間と余裕がある時はVirtualContestで実戦形式で解いてみたり、余裕がない時は
AtCoder Problemで一部の問題を解いたコンテストの他の問題を解いたりして数をこなしました。

やっててよかった事

楽しい

ただ趣味としてやっているだけなので気楽かつ楽しいです。元々パズルが好きでプログラムを始めた初期に大したものではないですがパズルを解くプログラムとかを作ったので何かここに来て原点回帰な気がしています。反面この楽しさは万人がそう思うものじゃないのではという感じがしています。形があるアウトプットを作るのが楽しいため競技プログラミングは楽しくないという意見も聞いたことがあります。私は反対で物を作りあげることより、何か身近にある問題をスマートに解決することに喜びを抱くタイプなんだろうなと改めて実感しています。

あと人って何でこんなに賢いのだろうかと感動することが多いです。自分が試行錯誤した上でどうしようもならなかった問題が思いもよらないスマートなアルゴリズムですっと解かれるのをみると人の叡智ってすげぇっと感動します。理解に苦しむアルゴリズムや数学の問題も多いですが、わかるものを増やしていきたいです。

コーディング速度やメンタル面の向上

問題をガンガン解いて、コードをガンガン書いていくことはいわば筋トレのようなもので逞しくコードが書けている感があります。意図せずWAやREを出した時や残り時間が少ない時に冷静になって対処を考えるのは、障害が起きて冷静に原因を分析し、最速で復旧を試みるのと近いところがあると思います。どんな時も焦らず対処ができる良い修練になっているのではと思います。

GitHubに簡単に草が生やせる

4月から一日もコミットを切らさないということを達成できています。完全に自己満足ですが、草が生えているのを眺めるのはいい気分になります。土日は少なくとも1問問題を解けばよく平日は業務でのコミットが入るので簡単に草をはやし続けられます。ここまで来ると記録を切りたくないので、コミットをせずに一日を終えようとするとハッとしてコードを書かなくてはという気分になります。毎日コードを書くよい習慣ができたなと思っています。

業務に役に立つか？

私自身採用担当として、面接の場に立つことが多いですが、そこではアルゴリズムの能力よりもWeb開発やDB,インフラについての知見を問うことが多いです。今のフェーズとして難しいアルゴリズムを利用して難しい問題を解くより、Web関連の様々な技術を利用して幅広く問題を解決していける人を求めています。ただ、採用面接の際にコーディング試験を行っているのですが、話す内容や人柄は非常に良さそうであるのに、コードがほぼかけず残念ながら採用不可とさせていただいている方が
少なからずいることは事実です。コードを書く力やアルゴリズムを理解する力自体は濃淡あれ業務でいきるのではと思います。

Goで競技プログラミングをやるのはどうなのか？

まだどの言語が最適か語れるレベルではないですが間違い無くベストではないでしょう。解答やサンプル、便利なライブラリはC++が主流です。ただ、感覚的には青くらいまではよほど特殊な言語を除いては言語の制約が致命的であることはなく、アルゴリズムを正しく理解して実装できるなら解くことは可能なのではと思っています。なのでまずは取り掛かりとして自分の好きな言語でやってみるというのは有りなんじゃないかと思っています。Go自体は遅くないですし、C++ともそこまでかけ離れておらずC++でのサンプルコードをGoに移植するのは今のところそこまで苦ではないです。エラーを出しにくい（コンパイル前に弾かれる)というのもプラス要素なのではと思います。

ただ青のレベルを超えていくと苦行です。ライブラリを全部自分でゴリゴリ書いていけないとまずそうなほか、うまくACできない時に既にACしているコードが少なかったり時にはなかったりするので参考にできるものがなく苦しんだりします。その点で青ぐらいが実質限界なんじゃないかなという感じがしています。

今後の話

今の肌感としては色別のレベルの問題で水色は半分以上は解ける、青はたまに解ける、黄はほぼ解けないという感じです。青問題への勝率はあげられそうという感じはあるので次は青まで頑張ってみたいです。Goで書いている人で青の人はごくわずか、黄色の人はいなさそうです。Goで書いていて、辛いなと思う部分も少しづつでだしており、Goで青まで行けたら満足でC++にするか、まったりと楽しもうかという思いでいます。ともあれしばらくはGoでがんがん競技プログラミングの問題を楽しんで解いていこうと思っています。来年は365日全てGitHubの草を生やすことを目論んでいます。