MIS.W 公式ブログ

早稲田大学公認、情報系創作サークル「早稲田大学経営情報学会」(MIS.W)の公式ブログです!

競技プログラミングを始めよう【アドベントカレンダー10日目】

みなさんおはこんばんちは。ラブクラフト全集が読みづらくてなかなか進まない、48代phoneです。今回は競技プログラミングの話をすることになってしまったのでその話をします。

対象は「プログラミング多少したことあるけど競技プログラミングとか知らねぇ」みたいな人ですかね。プログラミングしたことなくても多少知識があれば読めるとは思いますが、プログラミングってそもそもなんだろうってレベルの人だと読めない可能性があります。

もともとは違うことを書きたかったのですが、担当に「あなた技術力あるんだから書いてよ」と言われたので、こうなってしまいました。無念。それ故今回は脱線が予想されますがご了承ください。

競技プログラミングとは

「とは」って言っても大したものじゃないので簡単に言うと、webでやるアルゴリズムの試験です。うわあ味気ない。どの辺が試験かって言うと、制限時間があって、問題が何問かあって、各問に対して配点があり、点数を競う、ってところですかね。試験じゃないところは、大会の形式によっては人のプログラムの穴をついたり、公式のプログラムの穴を見つけたり、っていうのもアリますが、私はあんまりやってません。

時間・問題・配点に関しては大会によって違うのでなんとも言えませんが、3時間4問とかが個人的には相場ですかね。もちろんもっと長かったり短かったり、もっと多かったり少なかったりいろいろありますが。

逆に問題の形式は、私の知る限りではおおよそ同じ形式です。問題文/入力/出力/入力例/出力例、からなる仕様書のようなものが問題です。あぁ、なんか文が冗長。

説明がそろそろ思いつかないので例題出します。


問題文

電話くんはやる気の問題で2つの値の足し算ができない無能になりさがってしまいました。電話くんを解雇して代わりにa,bの和を求めましょう。

入力

a b

2つの整数 a,b (0≦a,b≦1000000) が空白区切りで与えられる。

出力

a,b の和を出力せよ。

入力例1

1 1

出力例1

2

入力例2

837428 232987

出力例2

1070415

競技プログラミングの問題は、こんな感じで問題が出ます。例題は足し算ですが、例えばどれだけ多くの床を通れるかとか、トランプでゲームをした時の期待値とか、単に数列のn項目を求めろとか、そういう問題が出ます。

これに対してソースコードを提出すると、正誤が返ってきます。基本的に問題には複数のデータセットと呼ばれる入力と出力の組み合わせが出題側に存在し、その入力をプログラムに与えたときに出力が一致しているか、で判定がされます。

基本的には全てあっているのでなければ誤答として扱われますが、問題によっては正誤だけでなく途中点が与えられたりします。と言っても、単に正答できたデータセットの数だけ点数が入るのではなく、「(0≦a,b≦100000)のデータに正解した場合○○点」みたいな限定的な途中点です。これがなぜ起きるかというと、問題によっては、入力の範囲が広くても平気なアルゴリズムと、そうでないアルゴリズムの複数の回答が考えられるからです。

例えば、さっきの問題は入力が(0≦a,b≦1000000)なので平気ですが、これが(0≦a,b≦2100)とか言われると、足し算の問題から文字列と超大数処理の問題に変わったりします。

言い忘れてたけど、実行時間にもよく制限がかかります。確か1秒とか2秒とか、十分な時間が与えられるのですが、これもアルゴリズムによっては遅いの速いのあったりするので、ちゃんと速い方を使ってねor考えてね、的な。

意外とここまで脱線ないな。面白くない。

 さっそく始めよう

いきなりって思った?俺も思った。世の中案外そういうものよ。

で、どう始めるかというと。さっきからなんどか「大会」という言い方をしていると思いますが、実際大会形式で開かれることがほとんどです。というかそれ以外知りません。なので、そういう大会に参加すればもう競技プログラミング経験者です。

紹介、と言っても俺がしってるのはAtCoderTopCoderICPCぐらいです。AtCoderは多い時で週1,少なくても月1開催、TopCoderはよく知らない、ICPCは年1です。

Googleで大会の名前を調べて適当にアカウント登録して、公式の発表する日時に「参加するやで」って言ってネットからソースコード出せばそれが参加です。大会によってはちゃんとお名前書いてチームつくってっていうのもありますが。

レベル的には、AtCoderBeginnerContest<AtCoderRegularContest<ICPCTopCoder じゃないかな、と思いますが、TopCoderは英語だったからよくわかんないしICPCは本戦行けてないしあぁ話すの辛くなってきたやめようかな。

アルゴリズム」がなんとなくわかるのであれば、AtCoderRegularContestをとりあえずやってみるのをおすすめします。なによりアレはとくになにもかかってないし参加もハイパー楽なので、3時間プログラミングすることを苦に思わないのであれば損はしません。私は苦なので2時間ぐらいで大体見切りをつけてほかのことを始めています。

「プログラミングを最近始めました><。if文はさっき知りました!」って人でも参加できるレベルがAtCoderBeginnerContestです。「いやif文はわかるだろアホかよ」って思ったらもうARCでいいと思います。つうか俺AtCoderしか知らないなって書いてて思った。読んでても思った?

こんなクソ雑な説明じゃなくてもっと大会を知りたければ、「TopCoder部」ってのがどっかにあったので、ググるとそれっぽいのが見つかります。競技プログラミング初心者にも優しかったと思うので、そういうの自分で探してみるといいかも。

最後に

俺はAtCoderしか知らなかったしなんで俺が競プロについて書いてんのかわかんないし説明は雑だし思ってたより脱線はしなかったね。やめだ!こんな話はやめだ!おしまい!