本の虫

著者：江添亮
ブログ: http://cpplover.blogspot.jp/
メール: boostcpp@gmail.com
Twitter: https://twitter.com/EzoeRyou
GitHub: https://github.com/EzoeRyou

アマゾンの江添のほしい物リストを著者に送るとブログ記事のネタになる

筆者にブログのネタになる品物を直接送りたい場合、住所をメールで質問してください。

Dwangoプログラミングコンテストの感想

2016年2月14日、dwangoプログラミングコンテスト2016が行われた。「ドワンゴからの挑戦状」というタイトルもつけられている。

今回の競技プログラミングの参加者は、1月24日に行われた予選を勝ち残った、2016年度新卒予定者から上位20名、一般から上位10名の者である。予選では、以下のような問題が出された。

Welcome to dwangoプログラミングコンテスト - dwangoプログラミングコンテスト | AtCoder

この予選が終わった後で、筆者が予選問題を試みた結果が以下である。

本の虫: ドワンゴのプログラミングコンテストをクリアできなかったお話

筆者は、C問題のゲーマーじゃんけんの期待値計算が分からなかったので、バカにでも書けるモンテカルロ法を使い、力技で解こうと試みたが、少数点6桁という圧倒的に高い精度が要求されているため、必要な精度が出ずに敗北した。後に聞くところによると、問題で要求される精度をモンテカルロ法で出すには、1兆回ぐらいの試行回数が必要で、制限時間が2分であることを考えると、一回の試行辺り0.12ナノ秒しかかかってはならない計算になる。モンテカルロ法では不可能だ。とはいえ、入力がたったの98通りしかないので、答えを埋め込んむという手もあるのだが。

問題を解くだけでも難しいのに、予選はたったの2時間しか与えられていなかった。見事予選を突破した30人は、一体どのくらいの問題をクリアしたのであろうか。

まず、16新卒枠の20人は、C問題までは通過し、残りのDE問題で部分点まで取れたものが残ったようだ。一般人枠の10名は、D問題も完全に通過することが必要だったようだ。2時間で全問通過した参加者は、たったの一人だった。また、今回は、ドワンゴ社員の代表として、Kusanoが参戦することになった。予選の成績から評価すると、16新卒枠の20人には入れる実力がある。

さて、本線の問題は、以下から挑戦することが出来る。

Welcome to dwangoプログラミングコンテスト - dwangoプログラミングコンテスト | AtCoder

さて、当日の話をしよう。私は当日、非常に眠かった。というのも、プロコンの前日はちょうど金曜日である。花金である。ドワンゴでは、金曜日の夜は大抵ボードゲームが行われる。もちろん、金曜日以外にも突発的にボードゲームは行われるのだが、金曜日の夜は、ドワンゴでボードゲームのかからない日はないといってよい。金曜日も、会社の設備であるセミナールームを借りて、徹夜でボードゲームをしていた。カタン、カルカッソンヌ、キングオブトーキョー等など。そのため、プロコンが行われた会場であるセミナールームは、当日の朝まで大量のボードゲームが散らかっていたのであった。

さて、その徹夜ボードゲームの最中に、私がプロコンの懇親会のメンバーに入っていると、同僚から聞かされた。社内のスケジュール管理システムをみてみると、なるほど、確かに予定が追加されている。すでに午前0時を回っているので、私が知ったのは当日ということになる。タダ飯であり、しかも勤務扱いになるそうだ。

懇親会は夜なので、とりあえず午前中は歌舞伎を見て過ごし、午後になってから、会場となるセミナールームに顔を出してみると、すでに机が配置されていて、準備があらかた整っていた。机にはお菓子と飲み物が置いてあった。そして、前方に大量のきのこの山とたけのこの里・・・まさか、ここでおっ始めるつもりか。戦争を！

さて、その後は問題通過を示す風船を膨らますなどの作業をしていると、時間よりやや早く、人がやってきた。参加者であろうか。いや違う。これこそ世に隠れもなきAtCoderの高橋 直大(chokudai)御仁であった。この仁について、筆者がここで筆を弄して拙い紹介めいた文章を書く必要はないものと信ずる。

さて、御仁から、今回の問題を早々と見せてもらったが、白状すると、一番簡単であるべきA問題：ニコニコ文字列２ですら、筆者には解答方法が皆目見当がつかぬ。chokudai御仁によると、A問題は、今日来ている全員が正解するであろうとのことであった。全問正解はかなり難しいのではとも言っていた。

さて、そうこうしているうちに、参加者がぼつぼつ集まってきた。今回の予選を突破した参加者は、若い人は高校生。遠い人はなんと韓国からやってきている韓国人であった。そして、全員が男であった。一体、プログラマーにおけるいびつな男女比はなぜであろうか。やはり、まだ社会的な理由があるのであろうか。

筆者は、参加者の持ち込み物に注目してみた。本を持ち込んでいる者がいたが、なぜか皆、まったく同じ本を持ち込んでいる。一体あの本は何なのか。筆者は同じくドワンゴ社員であり、問題C: ゲーマーじゃんけんの問題作成をしたtayamaにたずねてみた。 その本はプログラミングコンテストチャレンジブック、通称をアリ本といい、競技プログラマーの間では知らぬ者のない名著であるという。また、chokudai御仁も、 最強最速アルゴリズマー養成講座 プログラミングコンテストTopCoder攻略ガイドという参考書を出しているそうだ。

6面ダイスを持ち込んでいる者もいた。tayamaによれば、もしダイスを使う問題が出てきた場合、問題の解法を考える際に、実際に回転させられる物理的なダイスがあると便利なのだという。あるプログラミングコンテストで、20面ダイスを使う問題が出てきたのだが、そんな珍しいダイスまで持ちあわせていない会場の参加者の中には、問題用紙に印刷された20面ダイスの展開図を切り取って組み立てはじめる者までいたそうだ。その中で、唯一20面ダイスを持ち込んだチームがいたのだが、そのチームは、せっかく持ち込んだダイスには目もくれず、さっさと頭の中だけで考えて問題を解いたそうだ。なかなか寓話めいた話である。

他には、物理的な紙とペンを用意している人も多かった。

肝心のコンピューターであるが、ラップトップ一台だけを持ち込んだ者がほとんどであった。マウスを持ち込んでいる者はそれなりにいたが、意外にもキーボードを持ち込んでいる者は少なかった。ディスプレイを持ち込んだ猛者はいなかった。

ちらっと眺めたところ、WindowsでもMacでもないOSとしては、UbuntuのUnityが目立った。それ以外のDEを使っている参加者もいたような気がする。

今回のドワンゴのプログラミングコンテストは、AtCoder社のシステムを使い、問題作成もAtCoder社に依頼したと聞いている。現在主流の競技プログラミングのシステムは、Webブラウザー上から、コードを提出し、サーバー側で実行される。競技プログラミングというのは、入力が与えられ、問題から期待される出力を返せば、テストに通過する。競技プログラミングには、正しい出力という条件以上に、最大の実行時間やメモリ使用量などがあらかじめ設定されている。

AtCoderのシステムでは、かなり多くの言語(なんとBashまである)を用いることができるが、今回の参加者は、一人を除いて皆、C++11を使った。一人はJavaを使った。

なぜC++を使うのか。競技プログラミングコンテストは様々あるが、大抵の競技プログラミング用のシステムは、C++はまずサポートしているというのがある。標準ライブラリで著名なデータ構造やアルゴリズムは網羅している。また、実行速度の問題もある。AtCoderのシステムと問題は、言語によって制限時間を変えることがないので、pythonやrubyやphpのようなネイティブコードにコンパイルしない言語は、その分不利となる。

ちなみに、chokudai御仁はC#を使うという。これは、彼の初めて参加した競技プログラミング大会が、Microsoftが主催したものであり、言語がC#限定であったからだという。また、御仁が始めた書いたプログラムは、競技プログラミングの問題に対する解答であり、hello,worldをすっ飛ばし、ifもforも知らない状態で千行ほどのCのコードを書いたという。

プログラミングの目的は様々ある。ソフトウェアを作ることが目的の者もいれば、プログラミング自体に楽しみを覚える人間もいる。しかし、今回のプログラミングコンテストの参加者は、競技プログラミングに回答するためにプログラミングをしているという者がいる。何と純粋な動機だろうか。

ちなみに、当日の参加者におけるきのこの山とたけのこの里であるが、どうやら勢力は拮抗していたように思われる。

さて、競技が始まった。我々は別室にて、AtCoderの管理用のアカウントを用いて様子を見ていた。最初の数分は、何の提出もない。当然だ。まず少なからぬ文章量の問題を読む必要があり、次に書く必要がある。

開始から6分6秒にして、A問題の通過者が現れた。驚くべき速さである。問題を理解するのにすら時間がかかり、解凍方法が思い浮かばない筆者としては、呆然とするしかないのだが、chokudai御仁からすれば、「まあ、解く人は解くでしょ。もちろん、すごい速いし難しいことに変わりはないけれど」と落ち着き払った様子。どうやら生きている世界が違うようだ。

やや時間が経過するが、A問題通過者はそれほど増えない。普段の実力を考えれば、そろそろ解いていてもおかしくない人たちが一度も提出に至らない。どうやら、たったの20点というA問題の配点を見て、後回しの判断をした可能性があるという。今回のプログラミングコンテンストは、たったの2時間である。ただ解けるだけではなく、このような戦略も必要になってくるのだという。

競技開始から一時間を経過したところで、ニコ生を行うことにした。ただ、後から考えると、競技開始と同時にニコ生を行ったほうが、「おお、6分6秒で最初の通過者！」などと実況ができて面白かったように思う。ドワンゴの@mesoとAtCoderの@chokudaiとドワンゴのtayamaと、ゲリラ的に筆者も出た。

dwangoプログラミングコンテスト「ドワンゴからの挑戦状」本選 - 2015/02/14 17:00開始 - ニコニコ生放送

色々と話はあったが、テキストエディターの宗派が全員違ったのは、なかなか興味深かった。chokudai御仁はVisual Studioを使っている。@mesoはSublime Textを、tayamaはEmacsを、筆者はVimを使っている。

さて、競技時間が残り少なくなってきた。

順位を見ると、A問題を通過して、BCを完全解答なりほぼ完全に近い部分点を取得をした人が上位に来ていた。D問題のコインの取り合いはなかなか通過する人がいない。ただし、部分点の10点を取得する人が出てきた。この10点は結構大きく、ABCを完全回答した上位者の中で、部分点10点によりさらに上位に位置する人が出てきた。ただし、部分点とはいえ、落書き回数0の場合も相当に難しいのだが。

順位表と各問題の配点を見ると、まだ、D問題を完全通過すれば、一発逆転のチャンスが残っているようだ。D問題さえできれば、いきなり上位に踊り出ることができる。できればの話であるが。

競技開始から一時間も立つと、手を動かしている人はまばらになった。何やら紙に書いたり、手で頭をおさえて顔をしかめながら虚空を見つめている人が多い。なんとか解法をひねり出そうをしているのだろうか。chokudai御仁によれば、どのような解法を適用すべきか見当がついていない人もいるので、例えばここで適切な解法の名称をぽろりと言ってしまうと、大いなるヒントとなり得るのだという。

さて、いよいよ残り時間が少ない。あと6分ぐらいだ。とそこへ、chokudai御仁がうなり声を上げた。一体何が起こったのか。提出された解答の一覧を見ると、なぜかある一人の参加者が、同じ問題に短時間で何十回も提出を繰り返しているではないか。コードを眺めたchokudai御仁が一言、

「rand使ってます」

その瞬間、全員の顔がニヤリとゆがんで爆笑が起こった。

要するに、入力に対して正解となる出力ができればいいのだ。その出力をどのようにして行ったかというのは、どうでもいいことなのだ。たとえそれが、たまたま正解に一致する乱数列であったとしても。

ただし、さらに詳しく調べたchokudai御仁によれば、これは全くの博打でもないようだ。というのも、この大量提出者の書いたコードは、一部のテストケースで制限時間に引っかかる十分に速度の出ない実装であるので、実行時間を計測して、あまりに時間がかかる場合だけ乱数を返すようにしてあった。chokudai御仁によれば、まっとうな方法の過去の提出で時間切れで失敗しているテストケースの数を考えると、乱数に頼る部分はそれほど多くなく、1/64ぐらいの確率で通ってしまうのではないかとのことであった。のこり5分ならばやる価値のある博打である。

そして、この博打はうまくいった。なんと、無事にテストに通過した提出があったのだ。実に熱い展開であった。

一言だけ付け加えておくと、Cの標準ライブラリのrand()は、C++では非推奨扱いになっている。C++11には新しい乱数ライブラリである<random>があり、C++17に向けてrand_intというrandのように使いやすくて安全なライブラリも提案されているので、そちらを使うべきである。もちろん、このときのAtCoderの環境はGCC 4.8なので、最新のC++14の機能をあますことなく使えるというわけではないのだが。どうやら、AtCoderは近々C++コンパイラーの更新を予定しているらしい。

さて、競技は終了した。ほぼ全員が解答にC++を使っていたので、懇親会で色々と気になることを聞いてみた。

まず、どのようなC++11の新機能を使っているのか。参加者全員が共通して答えた機能は、Range-based forであった。 

int main()
{
    std::vector<int> v{ 1, 2, 3, 5, 6, 7, 8, 9 } ;

    for ( auto && elem : v )
    {
        std::cout << elem << std::endl ;
    }
}

range-based forがもてはやされるのには理由がある。もちろん、コンテナーのすべての要素に対して何らかの処理をしたい場合はよくあるのだが、その最大の理由は、自分でイテレーターを使う必要がないという点である。range-based forを使わないと、以下のように書くのだが 

for ( auto iter = v.begin(), end = v.end() ; iter != end ; ++iter )
{
    std::cout << *iter << std::endl ;
}

これはバグの元である。人間が手でこのように書いて間違わないわけがない。競技プログラミングにおいて時間はとても貴重であり、くだらないtypoのために何分もデバッグに費やすようなことは大変に痛い時間の浪費である。

これにつけて言及すべき、競技プログラミング特有のC++のテクニックがある。競技プログラミングの解答であるソースコードは、大抵がまずよく使うヘッダーファイル群の#includeに始まり、数十行の、極めて特徴的なプリプロセッサーマクロの定義が続く。

たとえば、以下のようなマクロ 

#define ll long long
#define ull unsigned long long

long long a = 0 ; // だるい
ll b = 0 ; // 楽

あるいは以下のようなマクロ 

#define pb push_back

int main()
{
    std::vector<int> v ;

    v.push_back( 1 ) ; // だるい
    v.pb( 2 ) ; // 楽
}

長い識別子は打つのに時間がかかり、typoの元でもある。

このような単純な置き換えはまだいいものの、以下のようなマクロまである。 

#define rep(i,n) for (int i=0;i<(n);i++)

int main()
{
    int a[10] ;

    // だるい
    for ( int i = 0 ; i < 10 ; ++i )
        a[i] = i ;

    // 楽
    rep( i, 10 )
        a[i] = i ;
    
}

あるいは以下のようなマクロ 

#define all(a) (a).begin(),(a).end()

int main()
{
    std::vector<int> v = { 1, 2, 3, 4, 5, 6, 7, 8, 9 } ;

    {// だるい
        int sum = 0 ;
        std::for_each( v.begin(), v.end, [&](auto x){ sum += x ; } ) ;
    }

    {// 楽
        int sum = 0 ;
        std::for_each( all(v), [&](auto x){ sum += x ; } ) ;
    }
}

競技プログラマーとしては、できるだけこのような機械的な人間が間違える可能性のあるコードは書きたくないのだろう。

ただ、この中でrepがとても気になる。指定した回数ループするというのはよくある処理に思える。なぜC++はそのような文法を提供していないのか。ライブラリで十分に出来ることに。 

template < typename Integer, typename Func >
void rep( Integer count, Func func )
{
    for ( Integer i = 0 ; i != count ; ++i )
    {
        func(i) ;
    }
}
 
int main()
{
    int a[10] ;
    rep( 10, [&](auto i){ a[i] = i ; } ) ;
}

とはいえ、やはりラムダ式が冗長に見えるかもしれない。

C++に欲しい機能としては、全員が何はともかく無限精度整数を挙げた。たしかに、いい加減に標準ライブラリに存在すべきであると思う。

さて、16新卒枠の中で、ドワンゴの求人応募で、最終面接までのパススルー権を獲得した人が出たそうだ。その権利を実際に行使するのだろうか。

ドワンゴ広告

ドワンゴは本物のC++プログラマーを募集しています。

採用情報｜株式会社ドワンゴ

CC BY-ND 4.0: Creative Commons — Attribution-NoDerivatives 4.0 International — CC BY-ND 4.0