Hatena::Grouptopcoder

CKomakiの日記

2016-12-10競技プログラマーのサイコロは千回続けて六が出る

あるレッドコーダーの歩んだ道のり

競技プログラミングadvent calendar 2016




B氏の誘惑 [2010年: 大学二回生春]


『一緒に実践的プログラミングっていう授業とろうよ』

当時大学二回生であり、人並みに進振りの単位が足りなかった自分をB氏が誘ってきたのが始まりだった。

B氏は、自分と同じく東京大学スポーツ愛好会卓球パートに所属する知人であった。

相当の奇人であり、彼が卓球をしているところは見たことがなかった。


実践的プログラミングという授業は端的に言えば競技プログラミングの問題を解く授業。

当時の自分はアルゴリズムが何かすらよくわかっていなかったのだが、

月曜6限という夜に開講される希少授業であったことと、

少しでも学校に行く日を減らしたいという打算から受講することにした。

これが自分と競技プログラミングとの初めての出会いである。


B氏は受講しなかった。




練習をしない [2010年: 大学二回生春]


当時の実践的プログラミングにはhos氏やrng氏を筆頭に日本のトッププレイヤー達が揃っていた。

過去にKMCoderで腕を磨いたと言われる達人達も遊びに来ていたのかもしれない。

しかし、当時の自分に誰かに話しかけようという気などはなく、その存在に気づきもせず講義は終わった。


SRMの存在を知った自分はそれから毎回欠かさず出場するようになっていた。暇だったのである。

バイトもせず授業も出ない一人暮らしの大学生が家ですることといえばタワーディフェンスしかないのだが、

大学二回生ともなれば流石に飽きてくるというもの。なのでSRMはほぼ出場していた。

しかし、プログラミングの能力を向上させようなどという気は一切なく練習もしていなかったため、

結果は芳しいものではなく、Div1とDiv2を彷徨うこととなった。




練習をする [2010年: 大学二回生冬]


『理学部』という響きのよさに惹かれ理学部情報科学科へと進学した自分にやる気などは一切なかった。

C言語を学ぼうという簡単な講義ですら単位を落とす有様。

しかし、怠惰な者にも勤勉な者と同じだけの時間が与えられるもの。

この膨大な暇をSRMの過去問埋めと蟻本周回により潰した結果、三回生の春にはレッドコーダーになっていた。


現在の競技プログラミングの基準で考えれば、この選択は勤勉に見えるかもしれない。

しかし、当時競技プログラミングの大会と言えばまだそんなに数ない時代[要出典]。

Codeforcesもできたばかりで、25割の確率で開始を延長し、英語の問題文は間違いだらけ[出典不要]。

就活のために練習する人間などもいない[要出典]。

要は数学やパズル大好き人間のためのマイナー競技だったのだ[要出典]。


ともあれ、当時の自分は競技プログラミングを練習することは膨大な時間の浪費であると考えていた。




地下 [2011年: 大学三回生春 ~ 大学四回生春]


東京大学理学部七号館の地下一階に学生端末室という単純に超汚い部屋、通称『地下』がある。

情報科学科の生徒は地下に席与えられ、そこで多くの時間を過ごすこととなる。

そして自分もそれからの一年半この部屋で延々競技プログラミングと向き合うこととなった。


これまで独りで練習を重ねていたが、ここでy3eadgzae[要出典]などの新たな仲間達とも出会った。

後にその多くがレッドコーダーとなる彼らは、

非常に優秀でありながらも謙虚に学びの姿勢を貫く、正にお手本とすべき学徒であった。

今の自分があるのも彼らのおかげであると言って過言ではないだろう。

彼らからは多くの煽り方を学んだ。


競プロのことはtwitterから学んだ。

当時twitter上でお世話になった人にhirose_golf氏やogiekako氏などがいる。

彼らのような黙々と問題に取り組み難問を通すストイックなタイプの人々も今となっては懐かしさを覚える。


自分の競技プログラミングの能力が一番高かったのもこの時期だ。

当然と言えば当然であろう。

500日もの間、蟻本周回やCFSRMの練習、マラソンマッチに参加、もしくは秋葉原に散歩くらいしかしていなかったのだから。

余談だが、牛ゲーという単語を誰が作ったのかというツイートなどをたまに見かけるが、

あれは蟻本大好き人間の自分がこの頃に地下で呼び始めたものである。

しかし、名前をつけるほどに重要視し練習を重ねておきながら本番で通せたことは過去に一度もない。




地上 [2012~16年: 大学四回生冬 ~ 現在]


一年半に渡る地下生活を終え、自分を待っていたのは信じられないような幸運であった。

外資系のソフトウェアエンジニアの給料が異常に高いという新事実。

更にエンジニアの面接はホワイトボードコーディングをするだけという圧倒的競技プログラマ優位。

企業も競技プログラマに目を付け始め、大会は増え、裾野は一般のプログラマーにまで広がり、

レッドコーダーはモテはじめ、腹筋が綺麗に割れた知的な彼女ができました。(ふくらはぎの筋肉も良い)


妄想はさておき、何も考えず競技プログラミングをしていただけなのに、

運良く卒業後もそれなりにいい生活を送れているように思われる。

まるで競技プログラミングにおけるエッジケースの如く、

サイコロを振ったら六が千回続けて出たかのように。




あとがき


結果として僕は大学の学部生活の大部分を競技プログラミングに捧げた。

僕が大学二年生で丁度競技プログラミングを始めた時に、四畳半神話大系というアニメが放映されていた。


主人公である『私』は大学三年生。

視聴者である僕達は大学入学時の行動で分岐する”もしも”の世界における数々の『私』を見ることとなる。

大学入学時にテニスサークルに入った場合の『私』。

映画サークルに入った場合の『私』。

秘密組織に入った場合の『私』。

そのどの平行世界においても『私』は満足をしない。

思い描いていた薔薇色のキャンパスライフとは程遠い大学生活に『私』は絶望する、という物語




僕はそのアニメを見てこう思った。




おもしろいから布教すべきだと。




ーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーー


くぅ疲


競プロのadvent calendarで自分語りポエムとか書いてる人がいて、実際問題ポエム読むの結構おもしろいなと思ったから自分で書いみた。

最初は自分のことを極力省いて、自分の視点から見た他人のことや環境の変化だけを書こうかとも思ったけど、

よく知らない人の名前出したら怒られそうだったからやめた。

実際y3eadgbeaとか地下で煽りまくるハラスメンティスト筆頭みたいになっちゃったし。


四畳半神話大系は言及したかったけど、アニメに影響されましたなんて書くのは凄く恥ずかしい。

なのでその部分を省いた結果として布教するだけになってしまった。


真面目な話、最近感じてたことだけど最近のプロコンはポップな感じがするなぁと書いてて再確認した。

自分の心境の変化かもしれないけど。

昔の競プロは自分の知能やプライドをかけて戦う場という感じだったけど、

最近のは皆で一緒に勉強して能力を上げて素晴らしい未来をみたいな感じ。

topcoderの背景が黒くてatcoderの背景が白いのの関係とか、

あとは薄暗い地下の陰気さとか色々な要因もありそうだけど。

実際問題、ほぼ全ての面で今の方がいいのは確実なんだけど懐古厨なので昔を懐かしんでしまう。

俺よりも昔からやってる人からは、蟻本ある時代の人間が何語ってるんだよって言われそうだけど。


ちなみに、文中に出てきたKMCoderっていうのもそういった俺の始めるずっと前の時代のものらしい。

iwiさん, kita_masaさん, omeometoさん, wataさん(基本全部ABC順)などの真にヤバイ人々が練習に使ってた。

あと今ググったらニコニコ大百科に記事があった。http://dic.nicovideo.jp/a/kmcoder


全体の感想は、プロコンに出会えたのとか、自由に使える時間が膨大にあったのとか運良かったことかな。

ただ、変人B氏のおかげで出会えたということには結構なひっかかりを感じてしまうが。



2014-12-02

マラソンマッチにおける頻出Q&Aと小技

05:54

これはCompetitive Programming Advent Calendar 20142日目の記事です。

マラソンマッチの問題は機械学習系と最適化系の2種類からなります。本記事はTCOでも出題される最適化系について書かれています。みんなで最適化してTCOに行きましょう。


"こまか~い"



マラソンマッチにおける問題は多岐に渡るものの、使われるアルゴリズムは焼き鈍しかビームサーチであることが多いため、実際に過去問を解いたりコンテストに出たりして練習を積めば強くなれる競技だと僕は思っています。

しかし、マラソンマッチは回答があるわけでもないので過去の問題を解いてみても新しい知識が入るわけではなく、ちゃんと練習になっているのかわからず少し辛いものがあります。なので、本記事では1人では気づきにくいちょっとしたコツや僕なりのやり方等を軽く纏め、これから練習しようという人の手助けが出来ればと思います。巷には素晴らしい記事が溢れているので詳細な個々のトピックについては触れません。あくまで道中の看板程度です。



本記事は、以下の記事をきっちり読みんだうえで少しマラソンマッチに触った後に、軽く眺めておくくらいが有用だと思います。

マラソンマッチの始め方

マラソンマッチの取り組み方

MarathonMatchトレーニングのための過去問レビュー









何を勉強すればいいのかわからない

山登りと焼き鈍しとビームサーチが必須になります。

高速化が重要になることが多いため累積和(いわゆるimos法)も時たま使います。

ほとんどの場合これらしか使わないにも関わらず、強い人は概ねいつも強いのでこれらを練習を通して身につけることが大切そうです。



言語はどれがいいのか

高速に動作するという点ではC++が圧倒的に有利です。

ただ、C++以外を使う強いコンテスタントもいますので何か利点があるのかもしれません。

ちなみに、そういった人々も速度が重要な問題では途中からC++を使い始めることが多いです。



Topcoderサーバー上では時間取得関数が非常に遅い

Topcoderサーバー上では、時間を取得する関数(timeやgettimeofday)はローカルの数千倍、数万倍遅いため、

これらの関数をあまり呼び出しすぎない工夫が必要となります。

ただしC++だとサーバー上でも高速に動作するrdtscを使用することにより、これを回避することができます。

rdtscはクロック数を取得する命令なので、TCサーバー上で一秒間に何回クロックが振動するかを測定する必要があります。

double getTime(unsigned long long int begin_cycle)
{
  return (double)(getCycle() - begin_cycle) / cycle_per_sec;
}

unsigned long long int getCycle()
{
  unsigned int low, high;
  __asm__ volatile ("rdtsc" : "=a" (low), "=d" (high));
  return ((unsigned long long int)low) | ((unsigned long long int)high << 32);
}


Topcoderサーバー上でうまく動かないor劇的に得点が下がる

九分九厘C++におけるメモリ外アクセスのせいです。

配列のメモリ外アクセスを検知するコンパイルオプション-fsanitize=addressをつけると自動で検知してくれます。

また、STLをデバッグモードにするコンパイルオプション-D_GLIBCXX_DEBUGもつけると安心です。

以下のようなaliasを設定しておくと幸せかもしれません。

alias g++0x='g++ -std=c++0x -D_GLIBCXX_DEBUG -fsanitize=address -D "KOMAKI_LOCAL" -O2'


これ以上改善できそうにない(貪欲や山登りを使ってる)

貪欲や山登りを使っている場合は大抵焼き鈍しやビームサーチ等に変えることにより大幅に得点を伸ばすことができます。

そうでなくとも、同じアルゴリズムをパラメーターを変えて何度も実行して一番いい結果を出力することにより改善はできます。

なので、とりあえず時間を使い切るタイプのアルゴリズムに変えるのがよさそうです。



これ以上改善できそうにない(時間は使いきってる)

ビジュアライザを眺めていると改善案が浮かびやすいです。

プログラムの出力よりもよい解を人力で見つけることができたら、そこをカバーできるようにプログラムを変えれば大抵スコアは上がります。

実際ビジュアライザを改造する人も多く、強い人ほどビジュアライザに力を入れる気がしてます。



これ以上改善できそうにない(ビジュアライザを見てもどうしようもない)

上位陣との開きが小さい場合は案外改善できるので諦めずに頑張りましょう。

小さい改善をむりやり繰り返しながら何かに気づくのをぼちぼち待つのもありかもです。

高速化、特定パターン用の実装(小さいケースのみ高速に動作するアルゴリズム等)、最終回答に対する最後の山登り等があります。

上位陣との開きが大きい場合は自分なりの楽しみ方を見つけましょう。



いいアイディアがあったので実装したがスコアが伸びなかった

プログラムもしくは考えが間違ってることが多いです。

プログラムが間違っていれば直して点数があがり、考えがおかしい時はちゃんと考え直す機会を得ることとなります。

どちらにせよスコアをあげるチャンスなので原因はきちんと明らかにしておいた方がいいです。





評価関数はどんなものがあるか

大抵「問題のスコアリング + 良さそうな状態にボーナスポイント」という形になります。

また、極偶に「ランダムプレイアウト」などを使用します。



評価関数がボトルネックになっている時

評価関数が重いということはよくあります。

しかし、評価関数の近似値を求めるだけであれば高速な実装も可能であることが多いです。

例えば「n個の物質の静電気力の総和」という評価関数の場合、正確に計算するとあまりにも重いです。

そこで、ある程度遠い物質間の力は無視することにより高速な擬似評価関数が作れます。

しかし、この擬似評価関数は高速ですが不正確です。

なので実際には速さと精度のトレードオフを追求することになる。



乱数を質のよいものに換える

広く使われている乱数用の関数は線形合同法を使っていることが多いですがあまりよくないらしいです。

マラソンでは一般にXorshiftが使われますが、メルセンヌツイスターなども有名です。

僕は基本はXorshiftを使い、最終提出時に一応いくつか試してみて一番いいのを使ってます。

class XorShift{
public:
  static int rand();
private:
  static unsigned int x;
  static unsigned int y;
  static unsigned int z;
  static unsigned int w;
  static unsigned int t;
};
unsigned int XorShift::x = 123456789;
unsigned int XorShift::y = 362436069;
unsigned int XorShift::z = 521288629;
unsigned int XorShift::w = 88675123;
unsigned int XorShift::t = 1;

int XorShift::rand()
{
  t = x ^ (x << 11);
  x = y;
  y = z;
  z = w;
  w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
  return w & 0x7fffffff;
}


条件分岐がバグっていて一度も実行されていない行があることに気づいた

コード網羅率という概念がテスト技法にあります。

お手軽な方法として、gccを使っていれば以下のコマンドで簡単にどの行が何回呼び出されたか調べることもできます。

> g++ --coverage tmp.cpp -o tmp
> ./tmp
> gcov tmp.gcda
> gedit tmp.cpp.gcov

tmp.cpp.gcovはこんな感じになります

        -:  130:
        1:  131:int main()
        -:  132:{
        1:  133:  int total = 0;
       11:  134:  for(int i = 0; i < 10; ++i){
       30:  135:    for(int j = 0; j < 2; ++j){
       20:  136:      ++total;
        -:  137:    }
        -:  138:  }
        1:  139:  cout << total << endl;
        4:  140:}


p[i]%の確率でfunc[i]を実行したい時とか

コード1ようなものはよく見ますが、制御が難しくなって思い通り調整できなくなってくるのでコード2の方がいいように思ます。

コード1

if(rand() % 5 <= 1){ 
  func_0(); 
}else if(rand() % 2 == 0){ 
  func_1(); 
}else{
  func_2();
}

コード2

static vector<int> bag;
for(int i = 0; i < 40; ++i) bag.push_back(0);
for(int i = 0; i <  6; ++i) bag.push_back(1);
for(int i = 0; i < 54; ++i) bag.push_back(2);
int func_id = bag[rand() % sz(bag)];
if(func_id == 0) func_0();
if(func_id == 1) func_1();
if(func_id == 2) func_2();

2013-12-26

Komaki法

23:35

iwi先生がiwi法とか呼ばれ始めててずるい。

http://topcoder.g.hatena.ne.jp/iwiwi/20131226/1388062106

俺も何か欲しいし、advent calendarでブログ書くの旬なので作って書いた。





しめじ:

  ぼくの師匠のkomakiが最後の問題で嘘解法を20回くらいサブミットし続けてジャッジを圧殺して最後は通してました

Dを持つ者:

  時代はジャッジの圧殺。覚えましたし。




Komaki砲:WAを大量に送りつけた後、ACすること。

解説:

2~5時間ほどしかない競技中に、同じ問題に対して20(50を越すことも)ほどのWAを叩き出しつつも最終的にはACされるということがプログラミングコンテストにおいては稀に起こる。

WA中は本人も辛いし、ジャッジキューが詰まり他人も辛い。非常に悲しい行為である。

半面、その愚直さや真摯さは感じさせるところもあるので、それを成し遂げた人物はオンサイトイベントにおいて初対面の方々に賞賛されることが多々ある。しかし、本人はこの行為をあまり快く思ってないので実際反応に困る。

 

 

難しい問題に挑戦する向上心、諦めない心、挫けない心。自分を信じる心。

一見すると自己啓発本に出てきそうなこれらの要素がKomaki砲の主な原因である。諸行無情。

 

  

参考文献:

結構どこでもやらかしているが、どこでやらかしたかあまり覚えていないので僕のcodeforcesのsubmissionsのリンクを貼っておきます。

232Dを120WAの3日後にAC

164Eを30WA後にAC

http://codeforces.com/submissions/Komaki/page/10

iwiwiiwiwi2013/12/26 23:41僕はロシアで教えてもらったあのメモ再帰からメモリ節約 DP にするテクを使う時 Komaki くんを思い浮かべるよ

CKomakiCKomaki2013/12/27 00:09再帰関数でrecur(pos)というのを書いちゃった後に、再起しすぎでstack over flowすることに気づいたときに回避する、あの使用時の前提からして少し愚かな感じのするやつですか。
{ return recur(n); } で呼び出さずに{ rep(pos, n) recur(pos); return recur(n); }でメモを埋めといてから呼び出すんでしたよね。

これ結構ダサいんで、もうちょっとカッコいいので僕を思い出してください。

2012-10-19最小カット

最小カット

01:19

この記事は壊れてます。












TagussanTagussan2012/10/25 18:48こんにちは。例題0の燃やすと埋めるの関係がおかしい気がしますが気のせいでしょうか?

CKomakiCKomaki2012/10/29 23:02直しました

RandiRandi2016/05/03 06:23Didn't know the forum rules allowed such brnlilait posts.

CarolineCaroline2016/05/04 01:57I loved as much as you will receive carried out right here. The sketch is tasteful, your authored subject matter stylish. nonetheless, you command get bought an shakiness over that you wish be delivering the following. unwell <a href="http://wuqeoecalsa.com">untqseuionably</a> come further formerly again since exactly the same nearly very often inside case you shield this increase.

JustisJustis2016/05/06 22:32I have to voice my affection for your <a href="http://cgeuxjii.com">kidsnhearted-ens</a> supporting those who absolutely need help on in this idea. Your personal commitment to getting the solution all through had become remarkably important and has encouraged professionals like me to achieve their ambitions. Your entire invaluable instruction signifies this much to me and further more to my colleagues. Thanks a lot; from each one of us.

RileighRileigh2016/05/08 12:23Cmq saltare la katana (o più probabilmente i80;sim2l-katanaࢴ in termini di lama) fa un grande effetto scenografico … come faceva notare Pino, le ragazze iraniane sono molto belle. http://xvqtubudjrq.com [url=http://xlmrikdir.com]xlmrikdir[/url] [link=http://tmjefzvel.com]tmjefzvel[/link]

eweyuzufoiafoeweyuzufoiafo2017/06/16 00:47http://100mg-viagracanada.com/ - 100mg-viagracanada.com.ankor <a href="http://sertralinezoloftonline.com/">sertralinezoloftonline.com.ankor</a> http://20mg-tadalafil-lowest-price.com/

odiomiuhodiomiuh2017/06/16 00:59http://100mg-viagracanada.com/ - 100mg-viagracanada.com.ankor <a href="http://sertralinezoloftonline.com/">sertralinezoloftonline.com.ankor</a> http://20mg-tadalafil-lowest-price.com/

axahdegginiraxahdegginir2017/06/16 01:02http://100mg-viagracanada.com/ - 100mg-viagracanada.com.ankor <a href="http://sertralinezoloftonline.com/">sertralinezoloftonline.com.ankor</a> http://20mg-tadalafil-lowest-price.com/

eboqifieboqifi2017/06/16 01:15http://100mg-viagracanada.com/ - 100mg-viagracanada.com.ankor <a href="http://sertralinezoloftonline.com/">sertralinezoloftonline.com.ankor</a> http://20mg-tadalafil-lowest-price.com/

eydafaxoeydafaxo2017/06/16 04:45http://100mg-viagracanada.com/ - 100mg-viagracanada.com.ankor <a href="http://sertralinezoloftonline.com/">sertralinezoloftonline.com.ankor</a> http://20mg-tadalafil-lowest-price.com/

ofukonurofukonur2017/06/16 04:46http://100mg-viagracanada.com/ - 100mg-viagracanada.com.ankor <a href="http://sertralinezoloftonline.com/">sertralinezoloftonline.com.ankor</a> http://20mg-tadalafil-lowest-price.com/

uredahuwiuredahuwi2017/06/16 05:01http://100mg-viagracanada.com/ - 100mg-viagracanada.com.ankor <a href="http://sertralinezoloftonline.com/">sertralinezoloftonline.com.ankor</a> http://20mg-tadalafil-lowest-price.com/

eicutgemameicutgemam2017/06/16 05:02http://100mg-viagracanada.com/ - 100mg-viagracanada.com.ankor <a href="http://sertralinezoloftonline.com/">sertralinezoloftonline.com.ankor</a> http://20mg-tadalafil-lowest-price.com/

avvurijolusavvurijolus2017/06/16 05:25http://100mg-viagracanada.com/ - 100mg-viagracanada.com.ankor <a href="http://sertralinezoloftonline.com/">sertralinezoloftonline.com.ankor</a> http://20mg-tadalafil-lowest-price.com/

inixomoihuwinixomoihuw2017/06/16 05:27http://100mg-viagracanada.com/ - 100mg-viagracanada.com.ankor <a href="http://sertralinezoloftonline.com/">sertralinezoloftonline.com.ankor</a> http://20mg-tadalafil-lowest-price.com/

urcyuxaziurcyuxazi2017/06/16 06:10http://100mg-viagracanada.com/ - 100mg-viagracanada.com.ankor <a href="http://sertralinezoloftonline.com/">sertralinezoloftonline.com.ankor</a> http://20mg-tadalafil-lowest-price.com/

ujcihikedokujcihikedok2017/06/16 06:27http://100mg-viagracanada.com/ - 100mg-viagracanada.com.ankor <a href="http://sertralinezoloftonline.com/">sertralinezoloftonline.com.ankor</a> http://20mg-tadalafil-lowest-price.com/