プロコンを１年ぐらいやってみて思うところ

はじめに

私はちょうど１年前ぐらいにプロコンに興味が出てそれ以来ちょくちょく参加しています。プロコンといっても色々ありますが、ここではアルゴリズム系の数時間のコンテストに限った話になります(数日にかけておこなわれるコンテストもあり、それはマラソンとか言われたりします)。今までやったこととかをつらつらと書くので、興味がある人への導入になれば嬉しいです。

プロコン？

そもそもプログラミングコンテストとはどのようなものか
→(この記事では)問題に対してその解を与えるプログラムを作成するコンテスト

例題

例えば、実際にICPCという大学対抗のプログラミングコンテストで過去に出題された問題としてこういうものがあります↓
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1237
問題文が長ったらしいですが、まとめると

紙tに6桁以下の数字が1つ書かれている。これを数字の間で切って、いくつかの数字を作る(切らないのも可)。ここで生成されるいくつかの数字の和が、numよりも小さい中で最大のものとその時のそれぞれの数字を求める。
どのように切ってもnumより小さく出来ない場合はerror、そのような切り方が複数存在する場合にはrejectedと表示する。
(例)
123という紙は、{123},{1,23},{12,3},{1,2,3}という4通りの切り方がある。そしてそれぞれの和は123,24,15,6である。なので、t=123,num=18という入力が与えられると、「numよりも小さい中で最大のものとその時のそれぞれの数字」が答えになるので、答えは15 12 3といった具合になる。
(入出力例はリンク先にもっとたくさんあります)

このような問題をプログラムで解こう！という話です。
この問題の答えについてはのちほど。

使用する言語について

私はC++を使っています。Cを書いたことがある人ならコンテストに限って言えば書くコードはそCと大差はないと思います。Cと変わらないならCで良いじゃんって思うかもしれないですが、C++にはSTLという超便利なものがあります。特にこだわりがなければ、C++はおすすめです。
とはいえ、言語に関しては当たり前ですが自分の好みだと思います(そのコンテストがサポートする言語の範囲内で)。上位の人たちが皆C++なのかといえば、決してそんなことはないです。(ただ入出力が遅い言語とかはもしかしたら結構きついかも...)
しかし、どのコンテストを見てもC++を使用する人がかなり多いように感じます。だから、使う言語はたとえ自由だったとしても、他人のC++のコードを見て何をやっているか分かるぐらいの感じの方がいいかもしれません(他人のコードを見ることは大変勉強になります)。

これまでやったこと

基本的に

コンテストに参加すると、制限時間があるのでたいていはその時間で全問を解ききるのはなかなか出来ないです。コンテストが終わると大抵は解説の記事が出たりするので、解説を読みながら実際に書き直してみる、っていうのをよくやります。これをやるのは全部の問題ではなく、自分がn問できたときのn+1問目だけでも十分だと思います。また、過去問とかで、考えてもわからないやつとかは、ある程度の時間(自分だと2時間ぐらい)が経ったら解説を見てしまいます。それを見て実際に書いてみます。意外と解説を読みながら自分でコードを書くのはいい勉強になると思います。解説を見ておわりにしてた人がもしいれば、一度やってみるといいと思います。

また、問題数をある程度こなすのはとても大事なことの１つだと思います。経験は物を言います。まずは全探索系の問題を普通にできるようにするのが一番最初の段階だと思います。正直始めたばかりのときは、自分は学校でならったことはあったものの幅優先探索や深さ優先探索でさえ書くのに手間取りました...

1月~6月

日本語のコンテンツを利用していました。以下の２つです。
-AtCoder
↑解説とかもあってとっつきやすい。また、時間が合う時にはコンテストにも参加して、他には過去のABCの問題を主に見ていました。また、ここで問題がまとまっててよく使います→http://kenkoooo.com/atcoder/
-AizuOnlineJudge (AOJ)
↑たくさん日本語の過去問がある。とりあえず色々な問題に目を通してみて、できそうだったらやってみる、分からないやつはとりあえずメモ帳に問題番号をメモしとくみたいな感じで使ってます。その時はわからなかったやつでも、半年経つと解法を思いつけたりするのでここにある問題に関してはあんまり解法を調べたりはしてません。ICPCの過去問が難易度順に並んだサイトが便利でよくつかいます→http://ichyo.jp/aoj-icpc/

7月~

この頃から英語のコンテストにもちょこちょこ参加し始めました。
-Codeforces
-topcoder(←12/10に初参加)
topcoderはArenaの設定がめんどいです。プラグイン導入の記事とかはいっぱいあるんでそれを読んでみるといいと思います。自分はcodeprocessor,tztester,fileeditという３つのプラグインを入れてます。この辺に関しては自分もまだ良く分かってないので、どれがオススメかとかはわかりませんが、これは結構自分だと使いやすく感じてます。
(2016/1/21修正、今はGreedというプラグイン１つでこれらでやりたいことができるのでそっちがいい気がします。導入の参考程度に自分でまとめました。)

また、この2つはレート帯によってコンテストが分かれており、Division1と2に分かれます。1が強いです。また、この２つは海外で運営されているので、コンテスト時間がAM1:30~とかだったりして、もともとさほど良くない私の生活リズムがちょっっっとズレたりもしました。毎回開催時間はまちまちなので、気力と体力を見ながら参加してます。

CODE FESTIVAL 2015 (11/14,15)

これの本戦に参加できたのが自分の中でかなり大きいです。初めてのオンサイトでしたし、かなりテンションが上がりました。友人とかでも参加した人もいましたが、まずは予選を戦わなければならないのですが僕の知っている人は通過しませんでした...そのため、当日は１人で参加だったのですが、本当に様々なイベントが有り、そこで知り合いも多少出来ました。また、ICPCの世界大会に行ったような人が隣に座ってたり、他にも現在Codeforcesのレート日本人１位の人がいたり、すごい人達を間近で見れたのがとても素晴らしい体験でした。来年はぜひどなたかご一緒に参加しましょう...!

これから

※ここは個人的な目標とかどうしたいかを書いてるだけです

私はtopcoderとCodeforcesの両方でDivision1に定着が当分の目標です。そのために何をやらなければならないかというと、コンテストに参加していてひしひしと感じるのは「動的計画法(DP:Dynamic Programming)」が想定解となる問題を解けるようになることです。頑張って練習します...
これはなぜDPという結論に至ったかというと、自分がn問解けた時のn+1問目の想定解法がだいたいDPであるからです。要は、自然な考えとして今よりも1問多く解けるようになりたいと思う場合に、DPがネックになることが経験上多く、またDPの問題は非常に多種多様なので問題として出やすいのも事実です。避けては通れません。DPは考え方自体が非常に自然であり、理解も容易ですが、いざ自分で立式などして解こうとなると結構辛いです。

また、話はガラッと変わってC++だとlong long intの精度がだいたい10^18ぐらいで、どうしてもそれより大きい値を扱わないといけない場合に(値が大きくなる問題はだいたい剰余を取るのであんまりないですが)、いままでJavaを使ってましたが、書くのがめんどくさくてやってられないです。なので、どうしても大きい値を使いたいとき用に、Pythonも覚えたいと思ってます。Pythonは文字列の処理もつよいらしいので、そのへんでも活きればなお良いかなーと期待しながら勉強したいです(ただDPよりは優先度はとても低い→なかなか勉強しない...)。Pythonは最近になってプロコン界隈でも少しずつ市民権を得てきている感はあります。そういう意味も込めて。プロ研ではPython使おうかなと思ってますが、どうせなら3系で使えるようにしときたいという気持ちがあります...ちゃちゃっと基本的なことを覚えたいです。

実際に解いてみる

ここまでダラダラと書いてきましたが、冒頭の問題を私がどのようにして解いたか説明して少しでも面白さが伝わればと思います。

問題(再掲)

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1237
数字が書かれた紙を何枚かに切って、その数の和がnum以下で最大になる切り方を見つけよう。

考え方

いかにコードを素早く実装するかが最も重要なファクターであると思っている方もいるかもしれませんが、実はその前段階の考察が一番重要です。ここに一番多く時間をかけるべきです。(実装は、ある程度の方針が立ってから着手すべきで、なんとなくやっていても消したり書き足したりを繰り返すだけで多くの時間を消費します。)

さて、先程も書きましたが、なんといっても全ての基本は全探索になります。この問題は容易に全探索が可能です。

今回の問題において、最初に紙に書かれている数字は6桁以下です。ここでは、n桁とします。i桁目の数字を[i]と表すと紙は

[1] [2] [3] ... [n]

といった具合に数字が書かれています。すると、切り目は各桁の間になるので、n-1個あることになります。このn-1個のそれぞれの切り目に対して「切る・切らない」のどちらかを必ず選択することになります。よって、n桁の紙から作り出せる組合せは2^(n-1)ということになります。今回はn<=6ですから、余裕でこの全ての状態を列挙することが可能です。後は列挙してその１つ１つに対して調べていこうと、方針が立ちました。

ここまでとは言いませんが、ある程度方針を立ててから実装にとりかかります。例えば、今回はn<=6ですが、もしn<=100の場合には、とてもじゃないですが時間内に答えを出力することはこの方針では不可能です。部分点などが設定されていない限り、この方針での実装は全く意味を持たないことになります。計算時間についてのだいたいの考察も役に立ちます。

実装

それでは、これをどのようにして実装するかとなった場合、たとえば再帰による深さ優先探索などが挙げられます。(結構引数が多くなりそう)
ここでは、それを使わず、このように状態を全列挙したい場合によく使えるbitloopというのを使います。正式な名前ではないかもしれませんが、説明すると2進数の各ビットを0:切らない,1:切ると見立ててn-1ビットの2進数を考えると、00...0から、11...1までの数が全ての状態を表しているというように考えることが出来る、というようなものです。
例えば、数123に対して、切り口は2つあります。「1と2の間だけを切る」という状態と、01は対応し、「2つとも切る：という状態は11に対応していることになります。
これを使うことによって、全ての状態を単純なforループ１つで表現することが可能になります。見通しが最高で、私は他の問題でこの解法を知り感動しました。この方針で書いていきました。

また、C++のSTLとして、vectorやstringを使用しています。
vectorは可変長配列として利用できます。v.push_back(a)はvector型のvに対して末尾にaという値を挿入していることを表します。挿入すると、自動的に配列のサイズは1大きくなります。切断された文字をint型に変換して保存する場所として使っています。
また、C++では文字列をstring型として扱うことが出来ます。s.substr(a,b)という関数は文字列sのインデックスのa番目を始点とするb文字の長さの部分文字列を返してくれます。文字列を切断する動作として利用しています。
この２つぐらいが分かってれば、なんとなくやってることはわかると思います。

冒頭にも書いたとおり、それぞれの場合を考慮して答えを出力する必要があるので、そのあたりの処理を追加して以下のようになりました：

#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main(){
  while(1){
    int t;
    string num;
    cin >> t >> num;
    if(t==0 && num=="0") break;

    int now=0; //最大値は十分小さな値で初期化
    int same_ct=0; //和がnowとなる切り出し方をカウント
    int small=1000000; //最小値は十分大きな値で初期化
    vector<int> ans;

    //カットするべき数の桁数
    int len = num.size();
    //各桁の間を切るか切らないかでbitloop
    for(int i=0; i<(1<<(len-1)); ++i){
      vector<int> s;

      int st=0; //部分文字列の先頭となるindex
      for(int j=0; j<len-1; ++j){
        if(i>>j & 1){ //j桁目とj+1桁目の間が切り目になる
          s.push_back(atoi(num.substr(st,j+1-st).c_str()));
          st=j+1;
        }
      }
      s.push_back(atoi(num.substr(st,len+1-st).c_str()));

      int tmp=0; //切り出した数の和を求める
      for(int j=0; j<s.size(); ++j) tmp+=s[j];

      //最小値の更新
      small = min(small, tmp);

      if(t<tmp) continue; //targetより大きかったら論外
      if(now<tmp){ //答え更新
        ans.resize(s.size());
        for(int j=0; j<s.size(); ++j) ans[j]=s[j];
        now=tmp;
        same_ct=1;
      }
      else if(now==tmp) same_ct++; //違う切り出し方発見
    }

    //output
    if(small>t) printf("error\n"); //最小値よりtargetが小さい
    else if(same_ct>1) printf("rejected\n");
    else{
      printf("%d", now);
      for(int i=0; i<ans.size(); ++i) printf(" %d", ans[i]);
      printf("\n");
    }
  }
}

例外処理について：
変数smallには状態を全列挙した時の和の最小値が保存されていて、smallよりも目標の数が小さかったらそれはムリです。→error
変数same_ctは探索途中で、同じ和の値を出す方法が見つかるごとに増え、最大値が更新されると1に戻ります。終了時に1より大きければ、最適解を出す切り方は複数有るということなる。→rejected

bitloopかなり綺麗に状態を全列挙することが出来ます。結構私は好きです。

おわりに

長々と書いてきましたが、ちょっとはプロコンに興味が出たでしょうか。始めるに遅すぎることはないです(社会人から始めたなんて人もちらほら見ます)。ぜひ私と一緒にプロコンしましょう！