徒然々草

あぁ、今日も一日、無駄にしてしまったかもしれない。

C++で競技プログラミング入門


この記事はC++er Advent Calender 2016 9日目(別のタブで開かれます)の記事です。

まず初めに

まずはお詫び
実はこっそり、Advent Calenderの日付を書き換えました。というのも、登録するときは日曜日だから時間あるだろうと思ったのですが、僕は学生なので期末試験と被ってしまって書く時間が取れませんでした。

すみません。

ただ、明後日(2016/12/11 Sun)の情報オリンピックの予選には間に合わせたかったので、今書いています。情報オリンピック向けの話も最後の方でします。

このサイトは初心者による、初心者のための、初心者のサイトです。内容については保証できませんし、ツッコミどころ満載なのかもしれませんが悪しからず。

しかし、対象としてはC++の基本構文と関数ぐらいがわかっている程度の人向けです。

また、このサイトではC++を使っていきますが、他の言語であってもある程度はわかると思います。

実ははてなブログをまともに書くのこれが初めてだったりもします。

競技プログラミングとは

特定の問題が与えられて、それに対して最適なアルゴリズム、より少ないメモリ、より少ない時間で解けるプログラムを書くことを目指します。
世界中で行われていて、例えば、TopCoderというようなとても大規模なサイトもあり、そのサイトの中でレッドコーダーなんていう愉快な魔法使い(上位数%の天才)たちがいたり。僕はあんまりTopCoderには参加しませんが。

競プロなんて呼ばれたりすることも。

初めの一問

こんな問題があります。

Ants

長さLcmの棒があり、その上に蟻がn匹いて、その蟻たちは端からx0, x1, x2...xncmの場所にいます。蟻たちは初め左右のどちらを向いているかはわからず、1cm/secの速さで棒の上を移動します。蟻たちはぶつかるともと来た方向に戻ります。蟻たちが棒のはじまでくると蟻たちは棒から落ちます。

全ての蟻たちが落ちるまでにかかる時間を求めなさい。(秒)

制約: 1 <= L <= 10^6, 1 <= n <= 10^6, 0 <= xi <= L

見たことある人は見たことある問題ですね。

少し見ると難しそうな問題ですが解法自体は非常に簡単なものです。頭がよければノーヒントでも解けるかも。

ヒント: 蟻がぶつかるともと来た方向に戻るってことは...





ここからは正解になります。考えたい人はページを下げないように。






一見すると全探索したくもなりますが、計算量的に無理です。(計算量に関してはここでは割愛させてもらいます。このページがわかりやすいです。)

まずは、ヒントの意味ですがこれは蟻がぶつかった時にもと来た方向に戻るのではなく、そのまますれ違ったと捉えればいいということです。蟻に区別はありません。

つまり、解法としては蟻の場所から端までの距離だけを考えればいいことになります。


#include <iostream>
#include <algorithm>

#define MAX 1000000

int main(){
    int N, L, n, x[MAX];
    std::cin >> N;
    
    while(N--){
        std::cin >> L >> n;
        for(int i = 0; i < n; ++i){
            std::cin >> x[i];
        }
        
        int max = 0, min = 0;
        for(int i = 0; i < n; ++i){
            max = std::max(max, std::max(L - x[i], x[i]));
            min = std::max(min, std::min(L - x[i], x[i]));
        }
        std::cout << min << " " << max << std::endl;
    }
    
    return 0;
}

こんな感じです。POJ(北京大学オンラインジャッジ)に提出したコードなので、C++11が使えません。

POJへのリンクを貼っておきます。 Ants

どうやって強くなるか

オンラインジャッジについて

競プロはインターネット上のオンラインジャッジで練習をします。有名なサイトをいくつか参考までに載せておきます。

AOJ 会津大学オンラインジャッジ: 日本の会津大学が運営しているサイトです。言語もC++14やPythonHaskellまで対応しています。とても使いやすいサイトです。まずは、ここの初心者コースから始めるといいと思います。

POJ 北京大学オンランジャッジ: 少し、初心者向けではないかもしれませんが、問題の種類でいうならば非常に多いです。ただ、言語(話す言語)が中国語もしくは英語なのとプログラミング言語C++11に対応していません。

AtCoder: これも日本で運営されているサイトです。上の二つのサイトとは違いコンテスト形式で通常は土曜日の午後9:00から始まります。(ただ、残念ながら僕は毎週その時間帯には予定が入ってる...)ランキングやレーティングなどがあり、自分がどのくらいできるのかがよくわかります。

TopCoder: これは世界でも最大級のサイトだと思います。しかし、言語(話す言語)が英語なので少しわからないと辛いかもしれません。このサイトは問題と定期的にコンテストが開かれます。ただし、海外の時間帯で日本では参加できるわけがない時間帯に設定されることがあります。

書籍について

普通は解けない問題があればインターネットで調べて解決するので十分ですが、体系的にアルゴリズムを学ぶのにとても役立ちます。

プログラミング コンテスト チャレンジブック 第二版: 競プロのバイブル的な本です。通称、蟻本と呼ばれます。表紙に書かれている先ほどのAntsをイメージした図と名前をかけています。一冊は買っといたほうがいいと思います。ちなみに僕の学校のパソコン部では持ってない人が取り合いになったりもします。

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造: 簡単な本で初心者にはとてもお勧めできます。上の本はある程度難しいのでこちらの本から初めてみるのがいいかもしれません。ちなみに、著者の会津大学の渡部さんはわたのべさんと読みます。

少し書き方について

書き方に関しては色々あるのでここから話すのは個人的なものです。

実はさっきのコードには改善点があります。

defineとconstexpr

先ほどは #define MAX 1000000 と書きました。
これは競プロにおいてはよくやることで、あらかじめ制約を上に書くことで配列などの範囲をわかりやすくします。

しかし、数年前まではこう書いていましたが今はあまりよろしくありません。というのも#defineで書くとエラーメッセージが気持ちが読みづらいことになってしまいます。実際にコンパイルする前にソースコードの"MAX"という部分を全て"1000000"に書き換えてから処理を始めるので、エラーメッセージが"〜MAX is〜"のような形ではなく、"〜1000000 is〜"のようにわかりづらい表示になります。この問題では考えなくても良い気がしますが、書き方としてはあまり使われません。(この話はEffective C++という本に書いてあったはず)

そこで代わりにC++11から追加されたconstexprを使います。コンパイル時定数として扱われるので、defineよりも優れています。
上のコードは本来であれば(POJがC++11に対応していれば)
constexpr int MAX 1000000;
と書いた方が良いです。
2016/12/11 追記 タイプミスをコメントで教えてもらいました。 constexor → constexpr

constexprとdefineの違いについては割愛します。(正直なところ自分でもよくわかってない。)

では、defineは使い道がないのかというと、全くそういうことでもありません。次のようなことをしている人もいます。
#define REP(i, a) for(int i = 0; i < (a); ++i)
これはfor文を書く時間が勿体無いのでマクロで簡略化する方法です。僕は慣れられずに使わないのですが中には使う人もいます。僕はなんとなく使いたくないんですけど。

他にもincludeをとりあえず何が必要かわからないから全部書いてしまうこともあります。そのらへんの話はこのページあたりがとても参考になります。

入出力について

実は、競プロで判定をする時には、とても多い量の入力にかけられています。なので、普段はそこまで気にする必要のない入出力にも気をつけたほうがいいです。

stdioを使う場合

時代はC言語まで退化しますが速度はおそらく一番早いです。ただし、書式設定には気をつけたください。特に入力でスペースなどがある場合はそれを考慮する必要があります。ちなみに僕はいつもこれを使っています。

iostreamを使う場合

先ほどは書きませんでしたが、
std::ios::sync_with_stdio(false);
というおまじないをmainの一番上の場所に書くと処理が早くなります。ただし、これを使うとcin, coutとscanf, printfを混在させることはできません。 あとは改行についてですが、
std::cout << std::endl;
よりも
std::cout << '\n';
の方が早いです。(普段は前者の方が安定した動作をします。 参考: http://www.bohyoh.com/CandCPP/FAQ/FAQ00009.html))
2016/12/11 追記
コメントでご指摘をいただきましたが、そもそも、文字列などを出力する場合は'+'もしくは'+='の方が早いです。
Example:
	
		std::string S;
		std::cin >> S;
		std::cout << S + '\n';
	
	


その他

他にも入出力部分をmain、処理部分をsolveという関数で書いて分けたりもします。蟻本の書き方がこれなので他の人もこういう書き方をしていることはありますが、特に気にする必要はないです。

JOIについて

JOI、明後日です。
Antsの内容がわかれば、2問完全正解はいけると思います。
予選とのボーダーはDPができるかどうかだったのですが、去年からJOIの運営が4問目をDPでない問題にしたので予想はできないです。5問答えられれば予選は突破できそうです。

ただ、JOIの問題の提出がとても面倒くさくて、JOIやPOJのようにソースコードを提出するだけではなく、それらの入力データ(5個)が渡されて、それに対して出力データを用意して提出しなくてはいけません。(練習ページでやってみるといいかもしれません。)
そんな作業を手でやっていると間違いなく時間が足りなくなるので、普通はredirectというバッチファイルを作ってそれを使って自動化します。

参考までに(macOS向け)


#/bin/sh

clang++ $1 std=c++11 -o .execute.out

mkdir "out$2"

for var in {1..5}
	do
		input_file=`ls *in$2/*$var.txt`
		output_file="out$2/out$var.txt"
		./.execute.out < $input_file > $output_file
	done



使い方は
sh ./redirect.sh source_file problem_number
という風にして第一変数にコード、第二変数に何番目の問題かを指定します。入出力ファイルは同じ階層に1問目ならin1というフォルダを作ってその中に入力ファイルを入れます。

Windows向けは今、持っていないので知り合いにもらったら載せます。