競技プログラミングをゆる~くやりはじめた
もともと競技プログラミングや数学があまり得意な方ではなかったなんですが、N高等学校で競技プログラミングを教えるということもあるし、N高生には競技プログラミングがまじで得意な生徒さんやら、アドバイザーのドワンゴ社員もいるのでこれはチャンスと思い自分もゼロから競技プログラミングをはじめてみることにしました。
競技プログラミングといいつつ、かなりゆるくやっていこうと決意。たぶん、競技ゲーみたいに勝負と思ってやると心折れそうだったので、低い山から自分なりの目標を持ってやるということで、まずはAtCoder Beginner Contest(通称ABC)の001からはじめて見ることにしました。
開発環境整備
言語は、競技プログラミングのプログラミング言語はほとんどの人がC++を利用しているということで、自分もC++ではじめることにしました。思えば、CとかJavaとかはそこそこ書いたりするのですが、C++をしっかり書き始めるのははじめてなので環境整備から。
最初CLionとかのIDEを使って書こうと思っていたのですが、ほとんどの参加者がエディタでやるということで、自分もUbuntuのg++とVimでやることにしました。
構成は、VirtualBoxとVagrantをインストールして、そこにUbuntu16を入れ、そこでg++とVimをインストールして使っています。そのへんの構成の構築はQiitaにも書いたとおりです。
エディタは、VS Codeでもよかったのですが、生放送配信とかする時に VS Codeの画面がうまくキャプチャできなかったのでVimではじめたというのが理由です。なお.vimrcはこちら。
VimのC++の環境を整備して思ったのは、vim-clangというプラグインで利用できる、clang-formatが思いのほか便利ということ。このVimでもVS Codeと遜色なくコーディングすることができました。
あと、大会によってはエディタでないと困ることもあるようなので予めVimやEmacsなどのコンソールエディタに慣れておくのは結構良さそうです。
というわけで実際にここまで説いた問題のメモをまとめていきます。 コード自体は、GitHubのsifue/cpp-studyにまとめてあります。
ABC 001
まず、最初の001で結構な洗礼をうけましたw
A問題
これに関しては、C++の標準入力と標準出力の行い方の手習いという感じでした。特に難なく終了。
B問題
突然長いif文をかかなきゃいけなくなり苦戦。そもそもC++の標準出力のフォーマットの仕方がわからなかったのですが、 C++ の iostream フォーマット指定早見表 のおかげでなんとかなる。
C問題
巨大なswitch文とif文を書くことになり心が折れる。
0~31までの数を。"N"とかの文字列に変換するところなどでバグを埋め込んでしまい、その修正に結構時間をかけてしまうということをしました。
得られた教訓としては、できるだけデータ構造にぶっこんでswitchとかifとか長いの書かないほうがよいということです。最期は <
を <=
にし忘れていたという凡ミスでした。
D問題
境界値が重要ということを思い知らされた問題。 60分と0分って同じなんですが、処理の過程でやりやすくするためにどちらかに統一しないとミソ。データのマージ自体はまあ職業プログラマなら約やっていると思うのでアルゴリズムに関しては特に何か気になることはありませんでした。 ただ、この問題もバグでひたすら苦しんでいました。 C++ の iostream フォーマット指定早見表 が神でした。
ABC 002
突然問題がストーリー形式になって、なぜか楽しみながらできるようになりました。 やはり面白い問題文のほうがやる気がでますw
A問題
if文がかければ大丈夫な問題でした。
B問題
とりあえず配列に文字を全部突っ込んでチェック。 この時に久しぶりに配列を使ってみて便利ー、と思っていたのがD問題で罠でした。
C問題
精度に気をつけなきゃいけない問題でしたが、なんとか正解。 ただ、intとdoubleの計算時の変換などは、ある程度CとJavaで知識があったから良かったものの、intをdoubleで四則演算するとdoubleになっちゃうなんていう情報は、プログラミング初心者は知らないだろうなぁと思いつつ。 多分このへんでC++の文法の本を読み始めたいとおもう問題に作ってるあるのだなぁと思いました。
D問題
ドハマリしました。 最初は議員の関係の表を作って、その一つの関係から探索して最大を探すような貪欲法的プログラみムを書いていたのですが、なぜかWrong Answer。ちゃんとだめなパターンが入っているようです。 で、結局最後は全パターンを調べるということで深さ優先探索で全パターンを作ってACとなりました。 まあ計算できる計算量なら最初から全探索したほうがよいということでしょうか。 あとここではじめて再帰が必要になったりして、だんだん競技プログラミングらしくなってきたなというふうに感じました。
あと最初2次元配列で実装したのですが、関数での引き渡しの際は参照渡ししても二次元配列の二次元目は固定長でなくてはならず、結局ポインタ操作になってしまう非常に面倒くさいことになったので、コンテナを使ったほうが良いということを学びました。
以上のサイトのAPIリファレンスが神でした。とりあえず存在するコンテナを一通り確認して、サイトの右上にあるカスタム検索でvector、set、map、pair、priority_queue、queue、stackなんかを探して使うことに。
なお、C++のデータ構造、代入し直した瞬間にコピーになるので、関数とかで&をつけて参照渡ししたいときだけは気をつける必要がありそう。とはいえ、参照渡ししないといけないほどシビアになることはまだなさそう。
ABC 003
だんだん難しくなりつつあることに怯えながらのチャレンジ。
A問題
合計して割るだけ。for文がかければなんとか。 なおintとdoubleの変換もあり。
B問題
過去の教訓から配列ではなく、setを使って排除。 コンテナの便利さを感じた瞬間でした。
C問題
priority_queueとstackを使って処理。とにかくC++のコンテナが偉大。 ただ最後は精度の問題があってハマったので、long doubleという型を初めて使いました。
D問題
3日悩んで結局解けず。先程回答を見ました。 1000000007という素数が出てきてなんとなくmodule演算をしてほしいのだなぁと思いつつ。やっていたのですが、配置で壁に沿ってなくてはいけないという部分が難しすぎて断念。 module演算に関しては、
にまとまっていて、ありがたいなぁと思いつつこれを使って計算。ただここに載っているフェルマーの小定理、理解しておらず。
これは部分点だけとれて満足すればよかったのかもしれないと思いつつ。なお、解説を見てもいまいちわからないという状態。解答を見ると、
というのを使って解いていたということが判明。 パスカルの三角形って使えるのか…ということにもびっくりしつつ、フェルマーの小定理も使えるようにして、再度100点の問題だけ説いてみようかなという感じです。
とりあえず、答え見たので答えどおりに実装してみたいところ。
ABC 065
たまたま夜にやっていたので、これにもチャレンジ。
A問題
if文を使った数値判定。
B問題
mapを利用してパスを消しながら検索していくというスタイルで解く。 やはりC++はコンテナが優秀。
C問題
ちょうどABC003のD問題で調べていたmodule演算がそのまま使えたので適用。 ただ、掛け算のときはintからあふれるのでその部分にハマり、最終的に型をlong longにして解決。
D問題
結局未実装なので、どこかで解きたい。 全探索すると10000!というでかい数になってしまうので、結局全パスから最も離れている2点を探して、それを両端として片方から貪欲法で道をなぞっていくのがよいかなとおもったりしつつ、実装はしていない。 他にも罠がありそう。ただ絶対値で係船できるのでC++の複素数ライブラリを使うと実装量が減らせそうだなぁと思ったりしてました。
おわりに
とりあえず、ここまで解いたABCの問題のメモをまとめてみました。まだ解けてないD問題が003と065とあるので、これからやってみたいところ。
だんだん数学的なテクニックが必要とされてきてるので、ある程度やって無理だったら答えを見ながら実装して学んでいくというスタイルでも良いのかなぁと思いました。
これらかも、ゆる~く競技プログラミングをやっていきたいなと思います。