初めての方は初めまして、既に会っているかたはこんばんは、とまとです。 この記事は主に、大学からプログラミングを始める方、 もしくは競技プログラミングというものをやりたい方を想定しています。
勢いで作ったタイトルが長すぎてタイトルじゃなかったので、短くしました
そういえば長いタイトルって、深夜アニメなどで流行ってましたよね
- 競技プログラミングとは？
- 実践
- practice contest(練習)
- 実際のコンテスト(A問題)
- ここから本番
- 実際のコンテスト(B問題)
- 実際のコンテスト(C問題)
- 実際のコンテスト(D問題)
- メリット
- 就活に使える
- 頻繁に大きい大会がある
- 類が友を呼ぶ
- 参加した大会の感想
- ICPC予選
- DDCC本選
- CODE_THANKS_FESTIVAL
- まとめ
1.競技プログラミングとは？
唐突ではありますが、 「プログラミングの勉強はどのようにやっていますか（or予定ですか）？」
例えば、本を読んだり、サイトを漁ったり、実際に何かを作ってみたりという方法があるかと思います。 その辺りの記事は先駆者がかなり多いため、ここでは紹介しません。 代わりに、「競技プログラミングをする」という方法をここでは提案してみます。
競技プログラミングとは？という人のため、とりあえずWikipediaから引用します。
競技プログラミングでは、参加者全員に同一の課題が出題され、 より早く与えられた要求を満足するプログラムを正確に記述することを競う。 コンピュータサイエンスや数学の知識を必要とする問題が多く、 新卒学生の採用活動などに使われることもある。 多くのコンテストでオンラインジャッジが採用されている。
「何言ってるの？わかんない」という人のために語弊を恐れずに言えば、 大学入試の数学のイメージにかなり近いです。 大学入試で頭を抱える方も居るかもしれませんが、ちゃんと違うところはあります。
大学入試は時に他人から押し付けられてやることがありますが、 競技プログラミングは基本的にやりたい人だけがやるものです。 苦手だとか嫌だとか思ったら、すぐにやめられます（だから気軽に始めたりやめたりしましょう）。
2.実践
さて百聞は一見に如かずということで、実際にやってみましょう。
注意事項 ・言語はC++,Python3を使っていきます（理由は私がいつも使っていて慣れてるから）。 ・これ以外の言語を使う方は、具体例が無いときがあるため適宜読み替えてください。 ・「プログラミングのソフトなど全然入れてないよ！」という方は、 paiza.ioというサイトの利用をお勧めします。 ・ここでは問題を解くためのコードを公表しますが、AtCoderのルールの一つ 「コンテスト中にネット上での問題のネタバレはご遠慮ください」に則って行っています。 （現在はコンテストは終わってるので公表可能）
2.1.practice contest(練習)
さて今回は、「問題文が日本語&開催頻度が高め」な、AtCoderを題材とします。 まず初めにAtCoder内にpractice contestというものがあるので、 そちらでAtCoderでの競プロで最低限必要な部分について理解しておきましょう。 AtCoderで検索して、以下のようなサイトへ行きましょう。 そして、赤色で囲まれてる所をクリックしてください。
その後の画面で「practice contestに参加する」をクリックするとログインか新規登録を求められます。 初めての方はアカウントの登録をしましょう。 それらが終わったら、問題タブを押して、はじめてのあっとこーだーという問題を開きましょう。 （下の方は「インタラクティブ問題」という問題に遭遇したときに開けばいいので、今は良いです）
さて、これで練習問題が表示されると思うので、 問題文と入出力例を一通り目を通していきましょう。 要約すると以下のような感じですね。
以下のような感じで入力が行われます。 ここで、a,b,cは整数で、1以上1000以下。 sは文字列で、1文字以上100文字以下です。 a b c s 出力は、a+b+cとsを空白区切りで1行に出力すること。 そして出力の末尾には改行を入れましょう。
簡単に思うでしょうか？難しいと思うでしょうか？ ここで重要なことは以下の6つです ・整数の入力をする方法 ・スペースで区切られた整数を入力する方法 ・文字列を入力する方法 ・数字の足し算をする方法 ・空白で区切って出力する方法 ・改行する方法
1つ1つは簡単なように見えますが、これはマリオの1-1のようなものです。 マリオの1-1では、ちょっと考えるだけでも、以下のようなことを教えてくれます。 ・移動の方法・ジャンプの方法・左には戻れない事実・右に進めば良いという目標 ・コインの存在と取得方法・敵（クリボー）の存在・敵の倒し方・通常ブロックを壊すという手段 ・ハテナブロックというブロックの亜種の存在・アイテム（キノコ）の存在 ・アイテムの効果（1回ぶつかっても死なない）・画面外（下）への落下は死ぬということ ・アイテムがあっても落下は死ぬということ・残機の存在・（土管を始めとする）隠し通路の存在 ・ファイヤーフラワーという攻撃手段・ノコノコという別の敵の種類と特徴 ・ノコノコの甲羅で攻撃という手段・ノコノコの甲羅で自爆する可能性 ・ゴールのポールは出来るだけ上にくっついた方が良いということ ・ゴールまでの時間が早い方が良いということ その他色々
これと同じように、一見簡単に見えても、 実際にやってみると意外と自分の知らないことがあったりするものです。 なおAtCoderではググるのはＯＫとなっているので、色んなサイトを見て回って、解き方を考えましょう。 （要約：とりあえずpractice contestで丁度いい出力を得られるコードを書いてみよう） 全く分からないor初めてプログラミングをする方は、速攻で読み進めてください。
どうですか？上手くいきましたか？ 上手くいった方は、これ以上細かいことは抜きにして実際のコンテストをやってみましょう。 上手くいかなかった方は、問題文のあるページを読み進めると解答例があるので、それを理解してから進めましょう。 分からない関数などは、大抵ググれば解説してくれるサイトがあるのでググりましょう。 ざっくり言って、 C++では入力:cin, 出力:coutという関数 pythonでは入力：input, 出力:printという関数でなんとかなるというイメージで大丈夫です。
なお、このPythonは2系ですので、3系はちょっとだけ関数が変わります。 1.raw_input() → input() 2.print 出力内容 → print(出力内容) という風に書き換えてください。 （解説などは、解答例がサイトにあるのでそれで終わりです）
2.2.実際のコンテスト（A問題）
さて、さっそくコンテストの問題を解いてみましょう。 一昨日の16日には実際にコンテストが開催されているので、それを利用しましょう（いわゆる過去問です）。 下のような画面のページに戻って、今度は緑の方のリンクをクリックしてください。 そこから問題文タグに行きましょう。すると4つほど問題名が並んでいると思います。
下に行くほど難しくなるのですが、まずは一番上、Round Up the Meanという問題から行きましょう。 内容は主に以下の通り
問題 1以上100以下の整数が2つ与えられます。それをa,bとします。 その平均値をxとします。 xの小数点以下を切り上げて得られる整数を出力してください。 入力は以下の形式です、 a b
具体的なイメージは、その下にある入力例と出力例を見ましょう。 入力：1 3 出力：2 「1,3の平均値は2.0であり、小数点以下を切り上げて得られる整数は2です」
入力：7 4 出力：6 「7,4の平均値は5.5であり、小数点以下を切り上げて得られる整数は6です」
先程のpractice contestを超えた方は、恐らくできるのではないでしょうか？ 早速やってみましょう。 また、サイト下部に言語を選ぶところとソースコードをコピペするところがあります コードを書き終わったら、そこで自分の使用言語を選んで、ソースコードをコピペしましょう。 提出ボタンを押した後、結果がACになっていたらクリアです。 CEやWAなどが出たり、ACの意味が知りたい人は、 サイト下端にある用語集のリンク先に色々書いてあるので、それを参照しましょう。
～～このあと解説～～
どうですか？ ちゃんと「切り上げ」出来ましたか？間違えて切り下げしちゃうことはよくあると思います。 さて一般的な解法ですが、上の方にある問題タグの辺りに「解説」っていうのがあるので見てみましょう。 ここではPDFで解答例へのリンクがありますね。それで解答例が見れます。
（D問題の解説などを見ればわかりますが、難易度が上がると 解答例が無くなって文章だけになるのでご注意を）
なぜ1を足すのか疑問に思った方は、「四捨五入 アルゴリズム」でググるなどがお勧めです。 （ちなみに私は、a+bの結果が偶数か奇数かで場合分けしました。 四捨五入のアルゴリズムなんて知らねぇよって方はこちらがお勧め。 偶数なら小数点以下切り捨ての値と同じだし、 奇数なら小数点以下切り上げの結果、切り捨てより1だけ大きいですからね。 予備知識無くても直感的に書きやすいコードだと個人的に思ってます）
Python3
2.3.ここから本番
Ａ問題をやってきましたが、コンテストの基本的な流れは、つまりは以下のような感じです。
問題文などに色んな情報が乗ってるので読む ↓ 分からないことがあったらググる ↓ コードを書く⇔ググる ↓ 提出する ↓ AC(正解)だったら次の問題へ ACじゃなかったら、原因を見つけてデバッグなどする。
さて、最低限の知識は恐らくここまでで大丈夫です。 ここからが、少しずつ複雑なアルゴリズムなどを利用したものとなります。 既に慣れている方はここからが本番ですね。
とりあえず、B,C,D問題も解いていってみましょう。 何度も言いますが、AtCoderではググるのはＯＫなので、自由にググりながら考えてみましょう。 目標の時間などが欲しい方は、順位表のタグをクリックして順位表を見ながら考えてみましょう。
Let's coding!
～～ここからは解説～～
2.4.実際のコンテスト(B問題)
ここは分量を控えないと幾らでも増えて「このアドカレ長すぎ」ってなるので、
追記：結局長くなりましたごめんなさいorz
シンプルに要点を絞って解説をしていきます。
なお、AtCoderの問題文や解説は読んだものとします（長くなっちゃうので）
まずはB問題です。 s'とt'はそれぞれ自由に並べ替えられますよね？ ということは、s'が辞書順で限界まで前に来るように、 t'が辞書順で限界まで後ろに来るようにすれば、 一番s'<t'を満たしやすいです。
逆に、これが満たせなかったら、他の全部の場合でs'<t'満たせません。 これは、辞書順で前の方をX軸負の方向、後ろの方をX軸正の方向として、 X軸を一度書いてみると分かりやすいかもしれません。 s'を可能な限り負の方向に動かして、t'を可能な限り正の方向に動かす。 それでs'<t'が満たせないなら、絶対にs'<t'には出来ないです。よね？
実はこれ、貪欲法と呼ばれるれっきとしたアルゴリズムなんです。 一番都合の良い状況を、貪欲なまでに選んでいくイメージです。
実際にどのようなコードを書けばいいのかは、先ほどと同じく解法を参照してください。 （今回は特に別解とかもないので私はコード載せないです） 特に着目してほしいのは、C++でもPythonでも、sortという関数を使用している点です。 つまりは学校とは違って、C++やPythonに最初から搭載されているものは大体使っていいんです！ やったね！sortのアルゴリズムの実装とかをさせられないよ！ （つまりは、どういう関数が言語に標準搭載されているかを知らないと不利になりますが、 裏を返せば、都合の良い関数の存在を知る機会になるのでやったね！）
2.5.実際のコンテスト(C問題)
さて次はC問題です。 こちらも貪欲法で解けるのですが、どうでしょうか？ 具体例をもとに考えていきましょう。 a1~aNの中に、3が含まれているとします。 ・もし3が1,2個含まれていたら全部取り除く必要がありますね。 ・もし3が3個以上含まれていたら、 1.全部取り除く 2.3個になるまで取り除く の2択がありますが、当然2番目の選択肢を選ぶ方が好ましいですよね （取り除く個数を最小にしたいので）
一般化すると、以下のようになります。 a1~aNの中に、i という数字が含まれている。 ・もしi未満なら、全部取り除く ・もしi以上なら、iになるまで取り除く
これをするにはどうすればいいでしょうか。 つまりは、数列aの中に、どの数字が幾つ含まれているのかが知れれば良いですよね？ そこでお勧めなのが、C++ではmap,Python3ではdictというものです。 一般に、連想配列という名前で呼ばれています。 （これは競プロじゃなくても結構使えるので覚えましょう！ 競プロやっぱやらない人でも、覚えておきましょう！）
連想配列は、簡単に言うと辞書の索引とページみたいな感じです。 通常の配列は、indexが0から始まる連番で情報を格納させられますが、 連想配列は、indexを自由な数字や文字で作れて、情報が格納されます。
具体的には、C++は公式解説にあるコードを見ましょう。 Pythonは存在しないので私のを使います。
Python3
2.6.実際のコンテスト(D問題)
この問題が解ければ、とりあえず脱初心者と言っても良いのではないでしょうか。
ちなみにAtCoder社長のchokudaiさんの話を元に考えると、
恐らくこれが解けてくれば、IT企業での就活に使えるぐらいになってきます。
(大手になるほどこの基準はもっと上がります。なお、私は時間内に解ききれませんでしたorz)
Ｃ問題に比べ十分難しいので、Ｃ問題が解けなかった方はこの項を飛ばすことをお勧めします。
なお、この原稿提出〆切が近いのでかなり巻きで進めていきます。
この問題ですが、最初はX軸正の方向を見てますが、その後はTの命令毎に90度回転します。 これってつまり、移動の方向っていうのが、X軸方向→Y軸方向→X軸方向→Y軸方向→・・・（正負は自由に決められる） という感じに、Ｔの命令毎になっていくのではないでしょうか？
つまりは入力例1を具体例に考えると、FTFFTFFFという文字列では、x軸正の方向に1進んだ後は、 y軸正or負の方向に2マス進める。 x軸正or負の方向に3マス進める。 ということと考えられますね。
一般化すると、i個(i≧2)の"T"の直前に"F"がn個あるとすると、 ・y軸正or負の方向にnマス進める(iが偶数のとき) ・x軸正or負の方向にnマス進める(iが奇数のとき) となりますね（上の具体例をもとにすると多分こんな感じって雰囲気はあるでしょう）
あとは、それを全通り試していきます。貪欲法です。 そして、最終的に目的地にたどり着く場合があればYesを出力、無ければNoを出力しましょう。 ただ、素直にやると凄い回数の計算になるので工夫しましょう。
まずx軸方向の移動だけを考えます。 配列dx[t]には、t回目のx軸正or負の方向への移動のときの移動量を格納します。
そして、1次元目を時間軸、2次元目を座標とする配列を考えます。 仮に、bool型で dpX[t][pos]という配列を作ります。 なおtは、過去の移動回数とします。 そして、過去の移動回数がtのときにあるx座標posに居ることが可能な時trueを代入します。
次に、tがある数値のときに、あるx座標posに居ることが可能だったとします。 その場合t+1のときには、pos+dx[t],pos-dx[t]に移動することが可能ですよね？
と、そういう感じで進めていきます。y座標でも同様です。 そして最終的に、目標の場所にx座標、y座標両方の側面から見て移動可能なら、 結果として移動できると考えられます（どういう動きをすると移動可能かはわかりませんが）。 ちなみにこのアルゴリズムは、動的計画法と呼ばれます。 動的計画法の定義は、Wikipediaでは以下の通り
定義 細かくアルゴリズムが定義されているわけではなく、下記2条件を満たすアルゴリズムの総称である。 1.分割統治法：部分問題を解き、その結果を利用して、問題全体を解く 2.メモ化：部分問題の計算結果を再利用する
まず、分割統治法を使用していますね。 移動回数がt回のときの部分問題を解いてから、 その結果を利用してt+1回のときの部分問題を解いて。 それを繰り返すことで問題全体を解いているためです。
次に、メモ化も使用していますね。 二次元配列dpXとdpYに対して、部分問題の計算結果を代入し、それを再利用しているためです。
以上から、ここまでの話は動的計画法というアルゴリズムを使っていたということになります。 このアルゴリズム、結構奥が深すぎて色々応用効くので、覚えておいて損はないですよ。
さて、細かい解説はこんな感じです。よく分かんなかったという人も分かったという人も、 公式の解説があるので見ておいてくださいね。 解答例は公式解説に無いので、C++で解く場合を乗せておきます。 （Pythonでは何か上手くいかなかったので載せられないです。ごめんなさい）
さて、以上で拙い解説ではありますが、一通りコンテストの解説をしてきました。 競プロをしたときの感じなどが得られたでしょうか？ 実際にはスピードと正確性を競う戦いとなるため、もっと面白くなります。 PUBGみたいな感じです。 そのため今のタイミングで面白くなくても、 コンテストにリアルタイムで一度参加してみると意外と面白いと思えるかもしれません。
3.メリット
長々とした記事ですが、ここまで読んでくれてありがとうございます。 まだ続きます。提示するのは手段だけではなく、メリットもないとね。 ここでは競プロのメリットについて話させていただきます。 最初は言語理解というメリットを提示しましたが、 「何か言語理解ってぼんやりしてやる気が出ない」みたいな人へ。 安心してください、もうちょっとはっきりしたメリットもありますよ。
3.1.就活に使える
競プロは競という漢字があるように、競います。つまり成績が出ます。 AtCoderであれば、レーティングというもので自分の実力が数値化されます。 そこで実際に良い数字を出せば、それで就活のときにアピールが出来ます。 （私はまだ学生なので就活はしてませんが、 大学での成果物を何か出せってインターンなどで言われているのを見るので、 多分就活も同じです。成果物としてレーティングを提示しましょう。 あ、「レーティングだけじゃ、相手がAtCoderを知らないと御社に伝わらない」？ なら次の項目でどうでしょう）
3.2.頻繁に大きい大会がある
競プロというのは、競技である以上大会があります。 特に有名なところを上げると、 Google Code Jam(毎年4月くらいに予選)や、 ICPC（毎年7月くらいに予選） CODE FESTIVAL(毎年9~10月くらいに予選)などがあります。 他にも有名なのはありますが、これについては上げるときりがありません。 このサイトが詳しいので、調べたい方は以下のリンク先へ。 強くなるためのプログラミング -様々なプログラミングコンテストとそのはじめ方-
これらは基本的に予選→本選の順番で行われます(本選は複数回にわけることも)。 予選を勝ち抜くのは難しいですが、実際に勝ち抜ければ「○○という大会で本選出場」という、 かなりインパクトのある肩書を振り回すことができます。
（後ここだけの話、本選がオフライン、つまりは大会の会場に集まる形式の場合、 それなりに高い確率で、昼食や夕食が出ます。会場までの交通費や宿泊費が出ることも。 つまりは無料で美味しいご飯が食べられたり、会場の近くで遊ぶこともできます。 それだけを目的とするのは憚られるかもしれませんが、モチベーションの一つとしてどうでしょうか）
3.3.類が友を呼ぶ
大学では、沢山の人脈を作りたいって人がいるかもしれません。 （大学では、意外と友達と会う機会が少なかったりしてさみしくなるかもしれません。） そのときに、競プロに打ち込んでいると、主にSNSから色んな人と触れ合うことができます。
4.参加した大会の感想
実際にどうこうメリット言っても説得力に乏しいので、実際の経験を元に説得力を付け加えようと思ってました。 （結果、お食事メリットにばかり説得力付いてしまった） ここまでで色々書きすぎて色々ヤバい（語彙力）ので、短く終わらせようと思います（これ言ったの何回目だ）。
4.1.ICPC予選
ICPCというのはそもそも、三人一組で一台のPCを使うという変わった形式で行われるコンテストです。 （基本的に所属大学の研究室などに頼み込んで、大学の一室でコンテストを行う感じです） ICPCの正式名称が International Collegiate Programming Contest つまりは国際大学対抗プログラミングコンテストというものでして、その名の通り、大学同士が競プロで戦います。 この大会の良いところは、複数人で問題を解くという、いわゆるペアプロの経験が積める点は大きいです。 （ペアプロは二人一組なので厳密には違うのですが）
これにより、独りよがりなコードを書きがちな人のコードが、良い方向に矯正されやすくなります。 ちなみに私は、殆ど他の人にコードの提案をしまくっていたので、コードはあまり書いてません。 本選には出られませんでしたが、現在では読みやすいコードを考える習慣は身についてきています。 来年には本選に出場したいものですが、1つの大学での出場枠が凡そ決められているためかなり難しいです。頑張りたい。
4.2.DDCC本選
DDCCというとよくわかりにくいですが、Discovery Channel主催のコンテストです。 主に新卒向けのコンテストではありますが、新卒じゃなくても順位さえ取れば出場出来る仕組みです。 なおICPC予選とは違い、参加者全員が同じ会場に行って競プロをします。 （会場の食事やお菓子がおいしかったです。大きなケーキとかチョコフォンデュとか凄い。 お寿司もある。黒い桶?に入ってる系の結構本格的なもの。しかも昼食と夕食両方にでる。）
本選というネームバリューで、結構自慢できました、はい。 就活はまだなのでその価値は未知数ですが、少なくとも話や自慢のタネとしてはかなり強かったです。 さてその本選の結果というものですが、初めて本選に出られたこともあって、会場の空気に頭が正常に働きませんでした。 （他の参加者の早すぎるタイピング音に圧倒される。コワイ、コワスギル。 あれほど耳栓をしたいと思うことはそうそうない） 順位は散々なものでしたが、ある意味その後の予行練習になりました。 来年も本選に出て、マシな順位が取りたいです。
4.3.CODE_THANKS_FESTIVAL
リクルート主催のコンテストです。実はCODE_FESTIVALというものがあります。 そちらは本選で、学生参加者上位100人が参加できる2日連続で行われる大会です。 今年の難易度はとてつもなく高く、参加できた時点で恐らく大手企業の就活でも十分通用します。 （というかリクルート主催だから、ほら… ね？） 残念ながら私はそちらには参加できず、本選に行けなかった人たちの中での学生参加者上位100人が参加できる一日で行われる大会の方に参加しました。 ですが、色んな人と話す機会を設けてくれたり、太鼓の達人を設置したりと面白かったです。
（こちらもとても食事やお菓子が美味しかったです。食べられる食事の量などは、絶対こっちの方が多い。 というか、お菓子やジュースに至っては、後ろに数万円分は置かれてましたよね？気のせい？ 昼食は3種類の弁当から1つ選択で、焼き肉弁当選びました。ロケ弁？というやつでした。美味しかった。 夕食は更に種類も量も豊富で最高。当然かのように、デザートも沢山出てくる。 最後には、お菓子が余ったからと掴み放題すらやってしまう。コカ・コーラ2Lを持ち帰った人すら居てマジヤバイ。）
この大会では、タイピング音への耐性はDDCCに比べて付いてはいましたが、 序盤でコード書き間違えまくったりして結局散々な結果でした。 あと、DDCCよりも自分の知識と経験が足りないのが原因の順位だということが如実に表れてしまったので結構悔しいです。 xor&DPやbitDP,LCAやUnionFind...色々理解してなかったの辛い… ちゃんと勉強してきます。 そして来年には、THANKSの付いてない方（本選）に出場したいです。
5.まとめ
ここまで色々書いてきましたが、 結局はやりたいことをやってプログラミング能力を上げるのが一番です。 既に他に何かやりたいことがある人は、そちらを優先しましょう。 私にとってのそれが競プロだっただけです。
もし競プロをやりたい方はぜひ始めましょう。 そうでなくても、今プログラミングでやりたいことが見つからなかったり、 もしくはいつか、少し気分転換にプログラミングで別の事をしたくなったときでも、 是非競プロの世界に足を踏み入れてみてはどうでしょうか？ 予想を超える新しい世界が広がっているかもしれませんよ。
これで今日のアドカレは終了です。 明日はまつりさんの記事「アナログ画材紹介」です。
