※この記事は競技プログラミング Advent Calendar 2020の14日目です。
タイトルの通り、先日AtCoderで緑になりました。
緑になった直後に茶色に逆戻りしたので危なかったですが、
なんとかすぐ戻しました。
昨日のABC185でやらかしてまたまた危ないところではありましたが…。
プロフィール
自分がなぜAtCoderを始めたのかとか、ここまで何をやったのかを記しておきます。
競技プログラミングのことについて書くのは初めてですね。
前提
- 35歳(始めたときは34歳)のクラウドインフラエンジニアとかSREとかそのへんのエンジニア
- 普段はAWSばっかり触ってます。
- 仕事ではあまりコードは書かない
- 必要な範囲でBashとかYAMLとかHCL(ほぼTerraform)とかは書きますが、あとはおまけ程度。読もうと思えば、というくらい。
- 学生の頃は理系
- どことは言いませんが、成績が悪かったので情報工学科を選べず…。
- 数学は理系の学生としてはそれほど得意でもなし(主観)
- 多分、同大学の一般受験の理系の学生の中ではかなり下の方
- 腐っても理系の学生だったので何もわからないわけではないです
- なお、今はだいぶ時間が立ったので公式や定理はだいぶ忘れている
なぜ始めたのか
↑に書いたとおりで、仕事ではあまり積極的にコードは書かない感じだったので何かしらコードを書くきっかけが欲しかったからです。
あと、Qiitaトレンド入りしたけんちょんさんの記事を見て面白そうだなと思ったので。
一応元々Paizaとか今はなきCodeIQとかでたまーに遊んではいました。
競技プログラミングのデファクトはC++、AtCoderを見ると時点はPythonとかだと思いますが、
コードを書くことでなるべく仕事の方でもプラスにしたかったので、
同じく仕事でも書きたいなあと思ってたGolangを選択しました。
TerraformとかDockerとかもGolang製ですし、そのへんのコードを読みやすくもなるだろうなあという打算もありました。
あと、そう思っていた矢先にコロナで緊急事態宣言みたいになって週末何もできない日々が続いたのでちょうど時間を使えたというのはありますね。
ここまでにやったこと
一番最初にまずABC151に出てみたんですが、
考える以前にまず入力を受け取って処理して、みたいな基本的なことをGolangで行うところでつまづきました。
どの言語でやるにしても、基本的な入出力のやり方をまず押さえる必要があるので、
ググって出てきたやつを色々参考にしました。
fmt.Scanで読み込むとforで回したときにそこそこ遅いのでbufioを使うとか。
Go 言語で標準入力から読み込む競技プログラミングのアレ — 改訂第二版
その後けんちょんさんのAtCoder に登録したら次にやること ~ これだけ解けば十分闘える!過去問精選 10 問 ~を元にした、
AtCoder Beginners Selectionをやりました。
その後はABCに参加しつつ、AtCoder ProblemsのRecommendationで出てきた問題を埋めていって、みたいな感じです。
解説で出てきた手法をググってみたりとか。
最初にあたった壁は探索アルゴリズムで、
bit全探索、深さ優先探索、幅優先探索あたりはこれまたけんちょんさんの記事を読んで勉強しました。
DFS (深さ優先探索) 超入門! 〜 グラフ・アルゴリズムの世界への入口 〜【前編】
DFS (深さ優先探索) 超入門! 〜 グラフ・アルゴリズムの世界への入口 〜【後編】
BFS (幅優先探索) 超入門! 〜 キューを鮮やかに使いこなす 〜
スタックとキューを極める! 〜 考え方と使い所を特集 〜
ビット演算 (bit 演算) の使い方を総特集! 〜 マスクビットから bit DP まで 〜
Golangでスタックやキューをどう実装するかを見るとスライスを使って実装する例ばかり出てきますが、
自分の場合dequeで前に値突っ込むときにTLEしちゃったのでスライスではなくcontainer/listを使っています。
Doubly Linked Listのライブラリですがそれほど違和感なく使えています。
他にも二分探索の具体的な実装方法に悩んだりしましたが、
(多分)有名なこの記事を読んだりとか、
二分探索アルゴリズムを一般化 〜 めぐる式二分探索法のススメ 〜
そもそもGoのライブラリ見てたらsort.Searchで二分探索できるじゃん、
とかがわかったりしました。
今あたっている壁はDPで、中々漸化式に落とすことができないのでちょっと問題を集中的に解きたいと思います。
蟻本は買いましたが割と早々に難しくてよくわからなくなったので一旦後回し。
螺旋本はAOJやりながら進めたりもしてましたが、まだ最初の方です。
それをしてるうちにけんちょんさんの本(問題解決力を鍛える!アルゴリズムとデータ構造)が発売されたので、今はそれを読み進めています。
十分時間が取れなくてゆっくりですがDPのところを何度か読んだりしてます。
ちょうど編集距離のところを読んでたから、それをそのまま実装すればよかった昨日のEとかはできなきゃいけなかったんだろうな…。
やってるうちに茶色diffの問題がだいぶ埋まったので、いっそのこと全部埋めちゃうかと思って先日茶色を埋めきりました。
これから
緑になったところでまた壁をちょっと感じているので、
前述の本を読み進めたり、足りないなと思ったところを補いながら継続していきたいなと思います。
その他のこと
競技プログラミングと自分の仕事との関連は?
仕事で活かすことが目的の一つと書いてるけど、実際どうだったのか。
ぶっちゃけると今の所それほど活かせていませんw
というのも、仕事でGo書いたりする機会は今全然ないからですね。
ただGoで書かれたOSSのコードをちょっと読んだりとかに抵抗がなくなったり、
なんかあったらプルリクしようかなあ、みたいな気持ちは自然に生まれるようになりました。
なんやかんやで基本ライブラリ見たりスライスの扱いに慣れたり、単純に実装することそのものに慣れたりというのは良かったと思います。
もっとも、競技プログラミングやってると絶対に使う機会のないライブラリはたくさんあるので偏りはありますけど。
まあ、面白くてやってる部分もあるのでこれについては100%仕事のためというわけではないですが。
アルゴリズムをどうこう、みたいな仕事は自分みたいな仕事だと直接生きる機会は少ないと思います。
ただ、クエリをチューニングしたりとか、ボトルネック調査して解消したりみたいな機会は無限にあるので無駄になることはないでしょう。
直近で一番書いてるの多分HCL(Terraform)なのでそれでそんな大量計算する処理は出てこないですが、
前述の通りTerraformはGolang製なのでところどころGoっぽい型の使い方とかがある気がします。
競技プログラミングやっててインフラやりたいみたいな人は中々出てこない気がしますけど、全然人がいなくて困ってるみたいな話しをかなり聞くんで興味があればぜひ手を伸ばしてみてください。
インフラが専門じゃなくても、あまり良く知らない状態でとりあえずサーバ構成を適当にやった結果大きな負債が残って今に至る、
みたいな状態を自分はめっちゃよく見てきた(そしてそれをどうにかしたいみたいな仕事が沢山)ので、
そっちの道を進むのでなくてもぜひ知っておいたほうがいいところではあります。
サーバレスやコンテナの文脈を踏まえて、だんだんどこまでをインフラというかが難しくなってきてはいますけどね。
Golangでやってみてどう?
上の方の方々はほとんどC++で、次点がPython、みたいな感じなので、ものによっては「これどうやってGoで実装するんだろう」みたいなやつがあったりします。
ただ、割とC++と似たような書き方ができることが多いので今のところはなんとかなってます。
最近の困りごとはACLをどうやって実装しようかということですね。
modintとかは(他人のコードを参考にして)実装したんですが、
言語として演算子のオーバーライドを提供していないので、
他の言語でやられているようなmodintの実装ができず、
メソッドとして実装するという手段と取らざるを得ないのでそこが苦しいです。
わからないときに強めの方の回答を参考にさせてもらうことがちょこちょこあるんですが、
Goの場合はABCでも難易度が上がると一気に回答者が減るのが見てすぐわかります。
まあ、積極的に選ぶ感じではないんでしょうね、やっぱり。