競技プログラミング in Go #1
背景
2年半くらい前に少しやって以来あまりできていない。たまに思い立ったように問題を解いたり蟻本を読んでみたりするものの、以前の内容を憶えておらず同じような内容を初見の顔をして勉強していることが多い。
まずはこの現状を打破して継続できるようにしたい。そもそもではあるが、最強最速アルゴリズマーになってアルゴリズムを仕事にするのは力量的にも難しいため、教養と知的好奇心と趣味としての競プロを楽しんで続けられるようにしていきたい。
なんで続かなかったんだろう...
自分なりに考えてみると、理由がいくつかありそうだ。
まず、C++を使っていた。私はC++を普段仕事や趣味で使っていなかった*1。使っていた理由は、競プロの解説や解答例でC++が使われることが多いからだ。けれど、時間を置くとすぐにわからなくなり毎回調べていた。問題を解くということに集中するためにはC++は扱う技量が足りていなかった。
また、競プロの優先順位をなかなか上げられなかった。他にも知らなきゃいけないことが多かったのだ。仕事で活かせる機会が少ない*2競プロに大きく時間を割くことができなかった。
継続のために
まず言語はGoにしようかなと思っている。Goは個人的に触っており、コーディングテストでも毎回選択している*3。そのため、Goで競プロに慣れておくメリットは大きいかなと思っている。Rustを使うことも検討したけれど、業務で使う可能性を考えるとRustよりもGoの方が高いかなぁ、と思う。まだまだ求人少ないし。
また、何を考えてどう解き、解説に何が書いてあるのか、そして時間を置いてもう一度解く必要があるのか、という当たり前のことができていなかった。理解より解くことが目的化していたからこそ中途半端になっていた。ここの思考を記録して整理しておく必要性を感じた*4。管理内容は後述する。
競プロにおけるGo
微妙らしい。
これ理由はけっこう簡単で、いくつか問題解いてみると分かるんだけど、強い型付けなのがかなり辛くって、キャストとかを超明示的に書かないといけない部分が多すぎるんだよね。実装速度がとにかく出ない。
— chokudai(高橋 直大)🍆 (@chokudai) March 7, 2017
go言語競プロだと厳しいって言ったけどtouristならtargetキープできる程度には使えると思うし、コンテストで競い合う向きじゃないけど、それがメインウェポンだと楽しめないってほどではない、くらいの印象。
— chokudai(高橋 直大)🍆 (@chokudai) March 7, 2017
これはたしかにそうで鬱陶しさや足りない機能が目立ってしまう。
例えば、未使用変数がワーニングじゃなくてエラーになるとか、タプルがないこととか、min/maxの関数がないとか。探せばたくさんある。
精選10問
なんやかんやあるけれど、とりあえず解いていこう。
思い立った時に毎回お世話になっている気がするが、drkenさんの記事を参考に解いていく。
今回はこれをGoで解いた。
Placing Marbles
Submission #19666903 - AtCoder Beginner Contest 081
Card Game for Two
Submission #19669348 - AtCoder Beginner Contest 088
Kagami Mochi
Submission #19669660 - AtCoder Beginner Contest 085
学び
知っていると思っていたようなことも競プロをやると厳密な理解を求められるのでよりクリアになった。
- breakで抜けるスコープは1つなので大域脱出したいならラベルを使う
- 数値のstringをループで回してruneを操作する場合、内部では文字コードになってしまうが、
'0'を引くことで数値を得られる sort.Xxxに渡す関数であるfunc (i, j int) boolのiとjはインデックスのため、比較を行う場合はfunc (i, j int) bool { v[i] > v[j] }のように書く- Goの配列のインデックスに負数は不可（Pythonとは違う）
管理方法
前述した思考の記録は、神ツールであるNotionを使っている。聖書や古事記などまだ印刷技術がなかった時代に書かれたもの大半はNotionで進捗管理されていたと言われている。そのくらい強力なツールだ。
こんな感じで復習できるようにまとめつつ思考過程と解説を載せている。初めはScrapboxで関連問題が表示されるようにしていたけれど、Notionの使い勝手の良さに負けてしまった。まだまだ改善の余地がありそうなので、もっと上手く管理したい。
結び
失踪せずに#2を書きたい。次回は蟻本の全探索の部分和問題とLake Counting問題の類題を解いていく。
コンテストは出れる時に出る。寝たい。
