Hatena::Grouptopcoder

TopCoderの学習のお時間 RSSフィード

戦績(topcoder.com) / 戦績(competitiveprogramming.info) / 過去記事 / 日記

2018-12-11

[]プログラミングコンテストに参加し始めて10年が経ちました 03:02 はてなブックマーク - プログラミングコンテストに参加し始めて10年が経ちました - TopCoderの学習のお時間


これは Competitive Programming (1) Advent Calendar 2018 10日目の記事です。


僕が初めて参加したプログラミングコンテストは Google Code Jam 2008 なので、今年でプロコンに参加し始めて10年です。

これまでにあったことを振り返ってみます。


-13年目


小学校にパソコンが導入されて、初めてコンピュータを触った。といっても置いてあるだけで何ができるものなのかさっぱり不明で、昼休みのゲーム機としてしか使われてなかった。


-10年目


誰が買ってきたのか忘れたけど家にパズラー(昔とても人気があったパズル雑誌)が1冊あって、ハマっていた。一度解いた問題を消しゴムで消してもう一回解いたりしてた。

中学校か市かの図書館で、数学オリンピックの本を見かけて興味を持つ。内容は全然わからない。


-7年目


大学受験にむけてだいぶ数学を勉強したので、ようやく数学オリンピックに出てもよさそうな気がして参加した。

センター試験そっちのけで過去問10年分くらいやったおかげで、予選はボーダーちょうどで通過できた。けど本戦はさっぱり。「こういうの、完全にそれ用の訓練をしとかないと無理でしょ」と感じた。

関連して、灘や筑駒の数オリ金天才中高生!!! みたいな記事を見て、ほへーそういう世界もあるんだなあ、と思うなど。


-4年目


大学のオープンキャンパスでスタッフしてたとき、資料として置いてあった情報学科の後期入試問題が目にとまった。こんなの。パズル/競プロっぽさありますよね。

高校生の時にこれを知ってたら情報学科に興味を持っていたかもなぁ、と思った。


バイト先にExcelで組まれたシステム(マクロも使っていないのでシステムというほどのものでもないが)があって、触れる人があんまりいなかったのでExcelを覚えてちょこちょこ改造したりしてた。


大学では化学専攻だったものの、この先それを続ける気もあんまりなく、だったら経済的に余裕もないし大学院行かずにさっさと就職してしまおう、と考える。

プログラミングとかほとんどやってないけど論理パズルみたいなの好きだし、まあこれから勉強すれば普通の人よりはうまくやれるんではないか、ということでソフトウェアエンジニアを目指す。

一応、情報処理演習の授業で、Fortranを使って簡単な物理シミュレーションを書くというのはやったくらい。


運良く、未経験歓迎地頭学歴採用みたいな感じ(? 実際のところは知らない)のところに引っかかって就職できた。


-3年目


就職に備えての準備として、学生のうちに基本情報技術者を取るくらいはしておいた。


-2年目


就職。

自然言語処理系の部署を希望してたけど何も経験・業績ない人がそんな仕事できるわけもなく、アプリケーションエンジニアをやる。


とにかく一々わからないことだらけで基本情報技術者取ったくらいじゃあ全然足しにはなりませんなあ、という気持ちになった。

コンピュータ扱う人たちの職場なので行動様式もいろいろ厳密だったりするんだろうか、と思っていたけど、そんなことはなくて、ちゃんと定義されていない言葉が使われたり(例:「ビルド」というのはコンパイルするだけのことですか、jarにまとめるまでのことですか、デプロイするところまでですか)でそんなに特別なことはないんだ、という感想だった。


あと、コンピューターサイエンスっぽい数式を触って…みたいなのはほとんどなく、複数人開発だから結局ボトルネックは人間系、みたいな感じで少々イメージとのギャップはあった。

まあ、地道に黙々実装するのはそれはそれで楽しいのですが。


-1年目


Project Eulerを発見して、埋めていってた。憧れていたけど実現できなかった、コンピュータと数式を使って問題を解く(人工的な問題ではあるけれども)、という営みが楽しくてハマる。

My Job Went To India を読んで、TopCoderのことが触れられていた。この名前を見たのはこのときが最初だと思う。

あと 日本語による最初のTopCoderの紹介として有名なITMediaの例の記事 もたぶん見てたんじゃないかな。


1年目 (0年目は存在しない数え方) : 2008年


Google Code Jamの紹介記事 を見て、何これ面白そう!と思って参加した。

結果は、Round1は通過できたけどRound2でまったくわからなくてTシャツ取れず。

このときは「予選で 500 位以内の方は、最寄りの Google オフィスで行われる準決勝にご招待します」だったんですよね…。超大盤振る舞いだ。

数学パズル的なプログラミングは割と自信があったものの、全然太刀打ちできなかったので、これはもうTopCoderで鍛えるしかない! となって、SRMに参加し始めた。

そしたら、世界中の数学・パズル・プログラミング好きな人たちとネトゲっぽく競えるのが楽しくて完全に沼に落ちてしまった。


ちょうどはてな界隈で ハチロク世代 が盛り上がっていたので、(1986年生まれからはちょっと外れるけど)参加して、そこのメンバーでSRMのたびにskypeチャットでワイワイやってた。

Imagin Cupで3位になって話題になっていた chokudaiさんが参加してきたりして、うわぁ有名人が来たーとか思っていた。

2008年の終わりくらいには黄色に定着した感じ(Easyしか解けてないけど)。


ちなみに、このとき自分が書ける言語がJavaだけだったのでJavaで参加してた。それを今までずっと引きずっている


2年目 : 2009年


SRMの過去問で練習するだけでは飽き足りなくなってPOJを始める(C++の練習も兼ねていた)。

たぶんこの頃が一番コンテストにハマっていて、SRMが平日午前中にあるときはそれに合わせて有給休暇を取ったり、コンテスト終了後はotinn.com(competitiveprogramming.info みたいなやつ)にF5連打したりしてた。


リーマンショックの余波?でSRMの回数が減ってしまって悲しかったので、マラソンマッチに初参加した。 http://topcoder.g.hatena.ne.jp/tomerun/20090129/1233244793

2週間あるうちの1回目の週末が問題読むだけで終わってるあたり、まだそんなにハマってなくてとりあえず覗いてみた、感がありますね。


TCO09 Marathonの予選にも参加して、Round1、Round2はまあ上位は無理ゲーだねーという感じだったけど、Round3で何かハマって20位を取れた。 https://topcoder.g.hatena.ne.jp/tomerun/20090408/1239210636

この年は予選が勝ち抜き制でRound3の10位までがFinal進出だったので、自分にもチャンスがあるかも!? という気になった。

ここでもまだ1回目の木曜-日曜までで計7時間しか使っておらず、まだこの時点ではライト層だった…。

TCO予選で覚醒したか、このあと何度か通常のマラソンに参加して1桁順位を連発し、レーティングは2000超へ。SRMは2000手前くらい。


この年が2回目の開催だったUTPCに参加して番狂わせで優勝した。どうも強い人がことごとく調子が悪かったっぽい。 http://topcoder.g.hatena.ne.jp/tomerun/20090608


ICFP Programming Contestにも初参加した。このときは問題があんまり好きじゃなくて同時にマラソンマッチも行われていたので、ちょっとしか触らなかったけど。


この頃からTwitterをよく使うようになり、競プロ勢っぽい人を多数フォローする。それまでWeb上の記事で見るだけだった人からフォローバックをもらって嬉しくなるなど。


3年目 : 2010年


SRMで赤くなった。TopCoderのコンテストは59回目だった。TCO予選でぐぐっとレーティングを上げられたのが効いた感じ。


診断人さんがニコ生でTCO会場から中継をしていて、激アツ展開に見入った。


この年のICFPCはめっちゃ面白かった(車のやつ)

それと、技術力の幅を広げたくてCTFに初めて参加。これも面白い。 http://d.hatena.ne.jp/tomerun/20101129/1291048564

これ以来、CTFにも年1,2回ほど参加するようになった。


せっかくプログラミングコンテストでアルゴリズム勉強しているので実用に使えるようなこともやれないかと思い、機械学習をちょっと触り始めた。PRML読書会に参加しに東京へ行ったり。

それに合わせてUTPCの懇親会にも参加した(確かオンサイト会場もあったけど参加は東大関係者限定だった)。プロコン界の多くの有名人の方々と初対面。


4年目 : 2011年


マラソンマッチで本格的にスポンサーコンテストが始まり、機械学習を勉強し始めたこともあって参加してみた。結果は惨敗で、これはこれで別のノウハウがいるね、となった。

スポンサーコンテストが入るようになったせいか、だいぶ通常マラソンの回数が減ってしまって悲しみ。それでもこの年のうちにマラソンも赤到達。20回目のコンテストだった。


短時間コンテストの情熱はだいぶ落ちてきて、過去問を解いたりといったコンテスト向けの練習に時間を使うのはやめることにした。

codeforcesがこの頃から盛り上がってきていたと思うけど、そんなわけで、参加はたまに時間が合えば、という程度で。


KUPCオンサイトに参加しに京都へ行った。ここでもプロコン界の多くの有名人の方々と初対面できて、数年ぶりの京都ということもあり、大変楽しかった。


Google Developer Day の DevQuiz(イベントに参加するための予選)の最終問題がマラソン問題だったので、時間をかけて取り組んで満点を取った。

満点を取った人だけが参加できるハッカソンにも参加したけど、Web周りの技術のことがまったく分からなくて丸一日座るだけをした。


5年目 : 2012年


色々あって転職した。DevQuizの解法を書いたブログを見て声を掛けてきたらしく、実質プロコン転職だ。

東京に引っ越してきたので色々イベントに参加するようになる。SRM勝手オンサイトとかやってた。


TCO Marathonで予選通過してFinalに参加した。 http://topcoder.g.hatena.ne.jp/tomerun/20121231/1356967269

この年は予選が3回あってそれぞれ上位4人がFinal進出、というルールだったけど、なぜかRound1で赤上位の人が3人しか参加してなくて、ギリ赤くらいだった自分が4位にすべり込めた。

Finalは日本からの参加者が多数だったこともあってめっちゃ楽しかった。


komiyaさんから誘われてプロコンを開いた。 https://autumn_fest.contest.atcoder.jp/

問題を作って出題するのは初めてで、コンテスト準備の大変さを実感した。

このコンテスト主催メンバーでIPSCにも初参加。変な問題が多くて、マラソン系を除くと一年で一番楽しみなコンテストだ。


この年はマラソンマッチで高速化コンテストがあってなかなか楽しかったのだけど、またやってくれないかな… https://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=15038&pm=11776


6年目 : 2013年


やっぱりアルゴリズムっぽい仕事がしたい! となって転職した。

ローレイヤー高速化の仕事を希望してたけど何も経験・業績ない人が(略)、組み込みエンジニアをやる。


この頃から数年間、JAGに細々と問題を提供していた(ICPC参加経験なくてもJAG入会できるんですよ)。関連して、AOJでICPC過去問をぼちぼち埋めたり。


CodeIQでマラソン問題を出題した。 https://togetter.com/li/559726

1位になったmachyさんがかなり工夫したアルゴリズムで解いていて感激した。


ICFPCに初めて合宿形式で参加し、なにやらうまくいって2位!

この年はコンテスト期間中めちゃくちゃ暑くて、そればかりが印象に残っている。


7年目 : 2014年


前の年の年末からKaggle Santa問題に真剣に取り組んで、5位に入った。正直サンタコンペはマラソンマッチとしては問題が微妙なことが多いんだけど、この回はかなり良かった。


機械学習マラソンにもう一度参加してみたらやっぱり惨敗した。難しい…。


8年目 : 2015年


代休が大量に溜まってたので、TCO Marathon予選に全投入して14日間ひきこもりマラソン生活を送ってみた。が通過できず、時間を費やせば良いというものでもないんだなあという学びを得た。

と同時に、全然人と喋らなくてもちょっとTwitterやっておくくらいで(少なくとも主観的には)社会性を維持するのには大丈夫であることがわかった。


CodeChefのlong contestがマッタリやるのにちょうど良いということを発見して、ときどき参加するようになる。


この年の後半くらいから身の回りが大変になって、コンテストはとんとご無沙汰になる。


9年目 : 2016年


AtCoderが国際化・レーティングシステムを開始して、自分の状況的にも変わってきたのでコンテスト参加復帰。

AtCoderの問題は知識不要なことが多くて、訓練をサボっている自分のような人にとっては取り組みやすくて助かる。


色々あって転職した。仕事でアルゴリズムっぽいことはやらなくても良いので、普通にアプリケーションが作れるようになることを目指していこう、プロコンは趣味で参加を続けられる環境を得られればいいや、と方向転換。


DNA解析のマラソンマッチが面白かった。結果はダメだったけど… https://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=16683&pm=14187


10年目 : 2017年


kenkooooさんが会社でコンテスト開きたい!! と言っていたので問題を作った。

アルゴリズムコンテストにしちゃうと既存の企業コンテストと差別化が難しいので、ショートマラソンを。 https://beta.atcoder.jp/contests/rco-contest-2017-final

マラソン問題って狙って良い問題作るのはかなり難しくて、案をたくさん出してその中から良さそうなのを選ぶ感じで。コンテストで使ったのは4問だけど、案は20個くらい出した。


5年ぶりにTCO Marathonで予選通過してFinalに参加した。 http://topcoder.g.hatena.ne.jp/tomerun/20171029/1509277486

この年から予選がGP30スコアの合計になったことがかなり有利だった。環境が変わって予選にフル参加できたことも大きい。


DDCC2017で初めて企業コン本戦に参加。


AtCoderでスポンサーマラソンコンテストが開催されたので参加。結果は微妙ではあったものの、参加者も多く、アツかった。


企業合同コンテストで初めてオンサイトチーム戦をやった。自分の気質的なところもあるが、他の人がいると集中が大幅に削がれて、これで効率上げるの相当難しいのでは…となった。ICPCに出てる人たちはどう対策してるんだろう。


Crystal言語が自分の中で盛り上がってきてたので、ABCを埋めたりする。


11年目 : 2018年


またTCO MarathonでFinal進出できた。今年はだいぶ運によるものだった感じはあるけど…。

さすがに海外旅行3回目ともなると慣れて余裕が出てきた。これからもまだまだ参加したい。


社会人枠が広いオンサイトコンテストが増えてきて、BitFlyer、SoundHound、HTTFの本戦に参加。ありがたいことです。


会社でのコンテストも引き続き開催。問題の質を保つの大変だぁ。


おわりに


プログラミングコンテストに参加してなかったらどういう暮らしを送っていたのか、想像できないですね。

次の10年も楽しんでやっていきましょう。

2017-12-16

[] 北大日立新概念マラソンでやった高速化色々 23:59 はてなブックマーク -  北大日立新概念マラソンでやった高速化色々 - TopCoderの学習のお時間


Competitive Programming Advent Calendar 2017 16日目の記事です。


北大日立新概念マラソン、1回目も2回目も、Simulated Annealingの良い近傍を適用できた人が上位になったという結果でした。

僕はこの手の良い近傍を見つけるという問題があまり得意でなく、かわりにナイーブな方法を頑張って高速化して対抗しようとしてしまう悪い癖があり、いろいろな高速化をやりました。その内容について、多少一般化した形にしながら書いていきます。

なお別に高速化のプロではないので、CPUのパイプラインを埋める…とか先のキャッシュラインをプリフェッチ…とかの話はしません(できません)。アルゴリズムのレイヤ中心です。


動的メモリ確保しない(影響度:☆☆☆☆☆)

とにかく動的なメモリ確保は取り除きます。

たとえば、小さな規模のBFSを何回もやるというシチュエーションはよく現れます(今回では、第2回で1ノードを取り除いたとき残った同じ番号のノードが連結かどうかを判定するのに使いました)。

void bfs(int pos) {
    vector<int> que = {pos}
    for (int i = 0; i < que.size(); i++) {
        // queにpush_backしたり
    }
}

毎回vectorを作るのが遅いので、十分なサイズのバッファをはじめに確保しておき、そこを使い回します。

int bfs_buf[2048];
void bfs(int pos) {
    int que_size = 1;
    bfs_buf[0] = pos;
    for (int i = 0; i < que_size; i++) {
        // bfs_buf[que_size++] = next_pos; とかでキューに追加
    }
}

「十分なサイズ」がとても大きくて全テストケースでその量のメモリを確保するのが嫌な場合は、グローバル(または関数スコープのstatic)なvectorにしておいて、毎回clearして使うのも可。


除算・剰余算を取り除く(影響度:☆☆☆☆☆)

除算・剰余算は遅いのでできる限り取り除きます。


その1:焼きなましの受理判定のときに発生する温度での除算は逆数の乗算にする

bool accept(int score_diff) {
    if (score_diff >= 0) return true;
    return rnd.next_double() <= exp(score_diff / temperature);
}

bool accept(int score_diff) {
    if (score_diff >= 0) return true;
    return rnd.next_double() <= exp(score_diff * temperature_inv);
}

その2:N点の中から動かす位置を決めるときは、乱数に対してNでmod取るののかわりに、順番に選んでいくようにする

void simulated_annealing() {
    for (int turn = 0; ;turn++) {
        int selected_pos = rnd.next_int() % N;
        // selected_pos を動かしたりする
    }
}

void simulated_annealing() {
    int selected_pos = 0;
    for (int turn = 0; ;turn++) {
        selected_pos++;
        if (selected_pos == N) selected_pos = 0;
        // selected_pos を動かしたりする
    }
}

または、候補になる位置をvectorに入れておき、要素を重複して入れることでそのvectorのサイズを2のべき乗にする。

選択される位置に偏りはできてしまうし、メモリアクセスの局所性は悪くなるものの、これで速くなって結果が良くなることもある

void simulated_annealing() {
    for (int turn = 0; ;turn++) {
        int selected_pos = cand_pos_list[rnd.next_int() & (cand_pos_list.size() - 1)];
        // selected_pos を動かしたりする
    }
}

スコア差分計算のために現在の値を保持(影響度:☆☆☆☆)

第1回では、ランダムな2点を交換するという近傍を採用しました。

このとき、スコア変化を調べるため「交換後に得られるスコア - 交換前のスコア」を計算する必要があります。

交換前のスコアは何度も同じ値にアクセスするため、事前に計算して保持しておいた方がよいです。

int calc_score_diff(int pos1, int new_val) {
    int ret = 0;
    for (int i = 0; i < 8; ++i) {
        ret -= graph[node[pos1]][node[pos1 + DIFF_POS[i]]];
        ret += graph[new_val][node[pos1 + DIFF_POS[i]]];
    }
    return ret;
}

int calc_score_diff(int pos1, int new_val) {
    int ret = -pos_score[pos1];
    for (int i = 0; i < 8; ++i) {
        ret += graph[new_val][node[pos1 + DIFF_POS[i]]];
    }
    return ret;
}

ビット並列化(影響度:☆☆☆☆)

1bitの情報はできるだけbitset的データ構造で持って、64bit分(またはSIMD使って128bit, 256bit分)まとめて処理できるようにします。

たとえば第2回では、元のグラフGでノード間にエッジがあるかどうかと、現在のキンググラフに埋め込んだ盤面上でノード間にエッジがあるかどうかをどちらも(オレオレ)bitsetで保持して、スコア変化を V/64 回のループで計算できるようにしました。

https://beta.atcoder.jp/contests/hokudai-hitachi2017-2/submissions/1867989 の823行目あたり


メモリサイズを減らす(影響度:☆☆☆)

メモリアクセスは遅いです。

プログラミングにあまり慣れていなかった頃、「exp関数遅いし、細かく離散化してテーブルに入れておけばアクセス1回で値を引けて速くなるんじゃないの」と思ってやってみて、逆に遅くなったという経験をしたことがある人はそこそこいるんじゃないでしょうか(僕はあります)。

できるだけ使っているメモリがキャッシュに乗るよう、でかい配列はデータ型をコンパクトにします。

第1回では、元グラフでの辺の重みを保持する500*500の配列が大きかったので、はじめint32_tで持っていたのをuint8_tにしました。これだけで1割くらい速くなった記憶があります。

ただし何でも詰め込めば良いというわけでもなく、値が最大で15なのをいいことに1要素4bitで詰め込もうとしたら、今度は大幅に遅くなりました。さすがに自前でマスクしてシフトして、という処理があちこちに入るとそのオーバーヘッドの方が重かったようです。

状況によっては、頑張って詰めた方が良い場合もあるとは思います。



座標を1次元に潰す(影響度:☆☆☆)

普通はフィールドのデータは field[x][y] で持つと思いますが、座標を1次元に潰して field[(x << 6) | y] で扱うと速くなりました。

座標をxy別々に扱わずに済んで、いろいろ簡略化されるからだと思います。

おなじみの

int DX[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
int DY[8] = {-1, 0, 1, -1, 1, -1, 0, 1};

int DN[8] = {-65, -64, -63, -1, 1, 63, 64, 65};

になります。


番兵で条件判定を取り除く(影響度:☆☆)

盤面の端をはみ出たかの条件をif文で書く回数を減らせるよう、盤面を64*64分確保して、実際のデータはxyそれぞれ1ずらした位置に置き、外周1周分を番兵として使えるようにしました。


焼きなまし受理判定の枝刈り(影響度:☆☆)

exp関数は遅いので、スコア差分が圧倒的に悪くてほぼ受理されなそうなら、exp関数を呼ばずに棄却します。

bool accept(int score_diff) {
    if (score_diff >= 0) return true;
    double v = score_diff * temperature_inv;
    if (v < -6) return false; // 枝刈り
    return rnd.next_double() <= exp(v);
}

ループアンローリング(影響度:☆☆)

回数が固定されているループで、呼ばれる回数が多い箇所はループ展開します。

for (int i = 0; i < 8; i++) {
    int next_pos = pos + DN[i];
    // next_pos を使って何か
}

int next_pos = pos + DN[0];
// next_pos を使って何か
next_pos = pos + DN[1];
// next_pos を使って何か
(中略)
next_pos = pos + DN[7];
// next_pos を使って何か
}

また、必ず1回以上実行されることがわかっているループはwhileではなくdo-whileにする、とかもこれに含めて良いかと。

やり過ぎると命令メモリが増えることによりアクセス局所性が悪くなって遅くなっちゃいますが。


BFSで来た方向に戻る移動をしない(影響度:☆)

上でも書きましたが、第2回で同じ番号のノードの連結性の確認のためにBFSを使いました。

シンプルに書くと、次のようになります。

for (int i = 0; i < que.size(); i++) {
    int pos = que[i];
    for (int j = 0; j < 8; j++) {
        int next_pos = pos + DN[j];
        if (node[next_pos] == n && !visited[next_pos]) {
            que.push_back(next_pos);
            visited[next_pos] = true;
        }
    }
}

まず、各点で隣接するそれぞれのノードが自分と同じ番号かどうかを、1bitずつ計8bitの値で持っておきます。

すると、BFS内での同じ番号のノードかどうかのチェックが削除できて、隣接位置すべてを見るループも削減されて、次のようになります。

for (int i = 0; i < que.size(); i++) {
    int pos = que[i];
    int bits = surround[pos];
    while (bits) {
        int dir = __builtin_ctz(bits);
        int next_pos = pos + DN[dir];
        if (!visited[next_pos]) {
            que.push_back(next_pos);
            visited[next_pos] = true;
        }
        bits &= bits - 1; // 最下位bitをクリア	
    }
}

さらに、BFSでキューにpushしたときに、自分に戻ってくる側の移動は見なくて良いはずなので、それを教えてあげると、さらに少し速くなります。

for (int i = 0; i < que.size(); i++) {
    int pos = que[i]; // queに入っている値は、上位16bitが探索する方向の候補、下位16bitが位置を表す
    int bits = pos >> 16;
    pos &= 0xFF;
    while (bits) {
        int dir = __builtin_ctz(bits);
        int next_pos = pos + DN[dir];
        if (!visited[next_pos]) {
            int next_bits = surround[next_pos] - (1 << (7 - dir)); // 自分にすぐ戻る移動を抑制
            que.push_back((next_bits << 16) | next_pos);
            visited[next_pos] = true;
        }
        bits &= bits - 1; // 最下位bitをクリア	
    }
}

0〜N-1 の中から異なる2つをランダムに選ぶときのテク(影響度:☆)

ナイーブにやると次のようになります。

int v1 = rnd.next_int() % N;
int v2 = rnd.next_int() % N;
while (v2 == v1) {
    v2 = rnd.next_int() % N;
}

よく知られているテクとして、次のようにすれば乱数呼び出しが確実に2回で済みます。

(ただし分岐予測は効きにくくなるので速くなるかどうかは場合によるかも…)

int v1 = rnd.next_int() % N;
int v2 = rnd.next_int() % (N - 1);
if (v2 >= v1) v2++;

2017-12-02

[] マラソンマッチは役に立つ 18:29 はてなブックマーク -  マラソンマッチは役に立つ - TopCoderの学習のお時間


Competitive Programming Advent Calendar 2017 2日目の記事です。

近年のAdvent Calendar執筆ハードル上昇に対抗するため簡単な記事にします。

皆さんご存じのように競技プログラミングは役に立ちませんが、マラソンマッチやってるとたまに役に立つので役に立ったことを書きます。


人間を意識したコーディング

短時間コンテストでは自分でクラス作ったりすることはそんなに無いかもしれません。一方、マラソン系コンテストで実装が重めのやつは1000行超える規模になって、ある程度は関心事の分離ができた構造になっていないと扱いづらく、なかなか死ねます。

また、整理されたコードを見るのは気分的にも良い。何度も同じコードを見ることになるのでこれは重要です。


計算量の感覚

短時間コンテストだと最悪計算量しか気にしませんが、実データで最悪ケースが来ることはそうそう無く「実際はどんなデータなのか?」を計測・分析して、実用上速いデータ構造・アルゴリズムを使うことになります。

プロコン以外のプログラミングでもこういうのが大事なところは多いかと。


ビジュアライザ

解答やテストデータの様子を確認するためにHTML+JavaScriptでツールを作ることはよくやります。場合によってはちょっとしたwebアプリ立てることも。


高速化

高速化やったところで最終的なスコアにほとんど意味ない場合も多いですが、わかっていてもついやりたくなっちゃうんだよね〜、ということを身をもって実感できます。

また、いざ高速化やるぞと取り組むときにはプロファイラ使ったりアセンブラ眺めたりして、これはこれで相当実用的な経験になります。


パラメタ最適化

マラソンマッチの終盤には、最適な答えを出すパラメタの探索をやります。これは機械学習のモデル作成でも課題となってくるところであり、ノウハウ知っておくのは良さそうです。

(僕はグリッドサーチしかやったことないですが…)

また、計算の実行にクラウド使うことも多いので「クラウド環境の活用経験あります!」と言えるようにもなりますね。


英語を利用する機会

英語に慣れなければという気持ちはあるものの、でも慣れていないので英語を実用で使う機会が得づらい、というスタートアップ問題がありますが、forumに書き込むのは自由なので貴重な機会になります。

他の書き込みを見ていると「文法無茶苦茶じゃねえか!」みたいな投稿がわりとあって勇気づけられることも。


まとめ

マラソンマッチをやろう!

2016-12-01

[] AtCoderの昔の問題を難易度推定する 00:09 はてなブックマーク -  AtCoderの昔の問題を難易度推定する - TopCoderの学習のお時間


これは Competitive Programming (その2) Advent Calender 2016 1日目の記事です。


先日、Twitterでこのような発言を見かけました。

AtCoderの過去問が今の基準だと何点になるのか知りたい

https://twitter.com/hogeover30/status/785894012716654593

やってみました。


一応、背景を書いておきます。

以前のAtCoder Regular Contest(以下ARC)・AtCoder Beginner Contest(以下ABC)では、基本的にそれぞれの問題は100点満点でした。

2016年7月にAtCoderがリニューアルされた際、難しい問題は高い点数となるよう、難易度に応じた配点がされるように変わりました。

そこで、以前の問題が最近の基準では何点くらいになるのかを、ユーザーの回答状況を元に推定しました。


AtCoderリニューアル後のコンテストの問題に対する、各ユーザーの正解/不正解の結果と配点を教師データとして機械学習し、過去の問題に対する正解/不正解の結果をテストデータとしています。


結果はこちらにあります。

https://tomerun.github.io/atcoder_statistics/estimated_scores.html


  • どうしても古いコンテストほどデータが少なくて推定しづらい様子。ABCのA問題が250点くらいといった高すぎる数値が出ている
    • 逆に、新しめのものはそこそこよさげに見える
    • こういった状況は他の機械学習案件でもありそうなんだけれど、うまく扱う方法あるんだろうか
  • ABCのD問題にもけっこう難しいのが紛れている
    • あまり出てないので知らなかった
  • 難易度順が逆転してしまっているところはあんまりない
  • これくらいの推定なら正解者数や正解率だけの分析でも出せるんではないかという気もしますが…
  • 解ける人が数人しかいない最高難易度帯の問題は、そのコンテストに誰が参加していたかによって結果がかなり影響されてしまうので、信頼性低そう
    • おおまかには、強い人がコンテストに出ていて解けなかった場合に推定スコアが高くなるという仕組みなので、あまり強い人が出ていなかった場合、推定スコアが高くなりようがない


実装に関しては、だいたいはscikit-learnのSVMに放り込んだだけですが、細々とした話としては次のようなことがあります。

  • 全ユーザー使ってしまうとデータがすごくスパースになって精度下がってしまうので、過去のコンテストに100問以上参加しているユーザーのみを計算に使いました
    • 対象ユーザーは236人でした
  • 過去に一部、満点が101点という問題がありましたが、100点以上を正解として扱っています
  • 「後ろのほうの問題だけ解いて他は無視」という参加をする人もいるので、コンテストの後半の問題は提出しているのに前半の問題は未提出の場合、前半の問題は不正解ではなく不参加という扱いにしています
    • 逆に前半だけ提出していて後半は未提出の場合、後半の問題は手が出なかったとみなして不正解扱い


せっかく今回いろいろデータを集めてきたので、他にもなにか面白い分析をやりたいですね。アイディアがある人はぜひ教えてください。


Advent Calendar2日目は、tubo28さんの「未定」と、snuke_さんの「IOIへの出題について」です。お楽しみに!

2015-12-01

[]すごいサブミット 00:42 はてなブックマーク - すごいサブミット - TopCoderの学習のお時間


これは Competitive Programming (その2) Advent Calendar 2015の1日目の記事です。


Advent Calendarの基本に返って、すぐ書ける記事にします。

これまでにコンテストで見た、印象に残ったサブミットを列挙します。

他人のコードを勝手に紹介することをお許しください。


SRM436

https://community.topcoder.com/stat?c=problem_solution&rm=300564&rd=13698&pm=10336&cr=10597114


想定解がFFTの問題だったのですが、インラインアセンブラで気合いで通しています。

1発ACを要求されるSRMで、36分でこのコードを書いて通すのは、当時の界隈にかなりの衝撃をもたらしました。


2010 TCO Marathon Round 2

https://community.topcoder.com/longcontest/?module=ViewProblemSolution&pm=10989&rd=14273&cr=22696357&subnum=8


このマラソンマッチは完全なる高速化ゲーでした。

というわけでJITです。


Marathon Match 78

https://community.topcoder.com/longcontest/?module=ViewProblemSolution&pm=12444&rd=15570&cr=21688563&subnum=13 (重いので注意)


圧勝した人のコードです。

皆が焼きなます中、Pythonで遷移パターンを列挙して埋め込んでDPしたみたいです。


NSA Marathon Match Event 1

https://community.topcoder.com/longcontest/?module=ViewProblemSolution&pm=10676&rd=14176&cr=7462740&subnum=3


これはコードよりも 順位表 を見てもらった方が良くて、訳が分からない点差が付いています。

これは暗号解読の問題だったのですが、どうも一人だけまともに解読できたらしいです。

コードで何をやっているか読めた方は来年のAdvent Calendarのネタにでもすると良いのではないでしょうか。ぜひしてください。


AtCoder Regular Contest #030

http://arc030.contest.atcoder.jp/submissions/286413


コードを見ても何をやっているのか分からないと思いますが、見るべきは提出時間で、コンテスト開始3秒後にサブミットされてACを取っています。

サンプルから解答を推測するプログラム、なのでしょうか??


お誕生日コンテスト

http://birthday0410.contest.atcoder.jp/submissions/128080

http://birthday0410.contest.atcoder.jp/submissions/127943


これも順位表を見てもらった方が良くて、WA回数が大変なことになっています。

問題の性質的に、インプット解析でがんばれてしまったのですね…。


なおこのようなひどい(褒め言葉)問題であるにもかかわらず、まともな方法で満点を得ているサブミットもあってこちらもすごい

http://birthday0410.contest.atcoder.jp/submissions/127561


おわりに

ほかにも興味深いコードがあったら教えてください!!