社内へ競プロ文化を広めるべく整理してたものですが、
せっかくなのでオープンなコミュニティに投稿しよう！と久しぶりの投稿です。
（枠的な理由でアドベントカレンダー参加できなかった腹いせでもあります。）
５行で要約
- 限られた実行環境で、決まった時間以内に実行可能なコードをかく
- お題は、有名なアルゴリズム！と言うよりも、その場での論理的思考力を問われるものが多い
- 解放によって計算量がN倍違う！みたいなことはザラにあるので論理的な設計力が身に付く
- 特A級問題はそうでもないけど、一定の問題までは超プロエンジニアじゃなくても解けたい
- 僕個人は競プロやり始めてからだいぶレベル上げできた（気がする）
僕自身とこの記事について
筆者はかっちりした競技プログラマーじゃないので、atcoderはスコアついてないよ。
でも、codewarsは4kyuまではちょっと空いた時間でぽちぽちいきました。
（それ以上は結構時間がかかる問題が多く・・・）
最近は土日にまとまった時間取れそうな感じになってきたので、atcoderもやっていこうと思ってる次第です。
この記事は、どちらかと言うと「競プロやってない人」むけなので、
細かいところは厳密には違ったり、話のフローを優先した表現になっていたります。
なので、何かあれば、競プロ玄人の方々においては、優しく補足いただけると幸いです。
「競技プログラミング」とは
一言で言ってしまうと、
「実行環境に制限がある状態」で、「論理的思考が必要な問題をとく」ための
「ソースコードをかく」というルールの遊び？勉強？スポーツ？です。
具体的には
- 実行環境に制限がある状態
- atcoderなら「実行時間制限:2sec/メモリ制限:1024MB」など
- 論理的思考が必要な問題
- ボードゲーム（将棋とかチェスとか）とか、マルバツの陣取りゲームなど
マルバツの陣取りゲームって「三目並べ」って言うんですね。知りませんでした
な感じです。
たいていの問題は、
愚直な回答だとタイムアウトし、よりベターな回答出ないと処理成功しない。
みたいな感じになっていたります。
具体的にはどういうのやるの？
問題
atcoderの以下の過去問を例に解説していきます。
https://atcoder.jp/contests/abc139/tasks/abc139_c
(AtCoder Beginner Contest 139より)
左右一列にN個のマスが並んでいます。
左から i番目のマスの高さは Hiです。
あなたは好きなマスに降り立ち、右隣のマスの高さが今居るマスの高さ以下である限り右隣のマスへ移動し続けます。最大で何回移動できるでしょうか。
僕は、この問題を読んだときざっくり以下のような感じで脳内変換しました。
ズラーっとビルが並んでいて、右隣のビルが、今いるビルと同じ高さ以下なら移動できる。
どこか好きなビルから移動開始したとき、最大でどのくらい移動できる？
ので、問題のイメージとしては以下の画像のような感じでしょうか。
単純な解法
もっとも単純な解き方としては、
マス１に降りたときの移動距離は？・・・Xで、
マス２に降りたときの移動距離は？・・・Yで、
・
・
・
と全てのマスに対して、そのマスをスタート地点とした場合の移動可能距離を全て計算し、
その後に、その計算した移動可能距離のうち最大のものを答えとして回答すれば良いですよね。
（pythonで書いた場合のソースコードはこちらに載せています。）
無事に問題が解けそうですね。よかったよかった。
終わり。
とはならないのが競技プログラミングです。
前述したように競技プログラミングには、「実行環境や実行時間に制限」があります。。
たとえば今回の問題では、問題ページの「制約」に記載がある通り、
N（マスの個数）は最大で、１０の５乗個＝100,000個です。
N＝10万として入力された場合は、この解法では規定時間内に処理が完了できません。
ので、この解法は不正解です。
より良い解法を探す
最初の解法でダメなら、より良い解法を探しましょう。
「改善」するには「現状のダメなところ」を探す必要があります。
察しの良い方なら先ほどの時点で気づいているかもしれませんが、
最初の解法では、移動可能距離を計算すること自体が無駄な箇所が存在しています。
特定のマスに注目した場合に、そのマスが左隣から移動可能なマスの場合は、
そのマスからスタートするよりも、左隣のマスからスタートした方が、
移動距離が「絶対に」大きくなることに気づいたでしょうか。
つまり、「全てのマス」について移動可能距離を計算する必要がなく、
「左から移動できないマス」についてだけ、移動可能距離を計算すれば良いことになります。
最適な解法
左から移動できないマス」についてだけ、移動可能距離を計算すれば良い
ので、左から順番にマスを見ていき、
移動できなかったときに、そのマスまで移動できた距離を確認して、
それが今までで一番大きかったら最大値として保存しておく。
で、最後にその値を答えとして回答する。と言うことをすれば良いです。
動き的には以下の画像の感じになります。
（pythonで書いた場合のソースコードはこちら）
論理設計（解法）でどのくらい違うの？
計算量という概念が存在します。
ざっくり言うと問題を解くためのマジックパワー（MP）だと思ってもらえればよいです。
(TP/PP派の方は、それぞれしっくりくる方に読み替えてください）
同じ威力の技が二つあった場合に、たいていの人はよりMP消費が少ない技を使うんじゃないでしょうか。
計算量の導出方法などは割愛しますが、今回の問題ではNの最大個数ケースの「N＝10万」だったときに、
以下の画像の通りに、だいぶ計算量に差があります。
厳密にはそんなことはないのですが、めちゃくちゃざっくりとしたイメージとしては、
最初の解法よりも最適な解法の方が、１００万倍処理が速いな感じです。
つまり
普段何気なく処理を書いていて、処理速度のボトルネックになっていたような箇所が、
意外と論理設計を見直すとめちゃくちゃ早く終わるようになる処理だっった！
みたいなことに気付けるようになるかもしれません。
ので、競技プログラミングをやって論理的思考力を鍛えることは、
エンジニアにとって一定意味がありそうな感じがしてもらえると嬉しいです。
興味を持っていただいた方は、以下の記事を読んで競技プログラミング始めてみてください！
それでは！！