当時大学二回生であり、人並みに進振りの単位が足りなかった自分をB氏が誘ってきたのが始まりだった。B氏は、自分と同じく東京大学スポーツ愛好会卓球パートに所属する知人であった。相当の奇人であり、彼が卓球をしているところは見たことがなかった。実践的プログラミングという授業は端的に言えば競技プログラミングの問題を解く授業。学校に行く日を減らしたいという打算から受講することにした。これが自分と競技プログラミングとの初めての出会いである。B氏は受講しなかった。大学二回生春]当時の実践的プログラミングにはhos氏やrng氏を筆頭に日本のトッププレイヤー達が揃っていた。過去にKMCoderで腕を磨いたと言われる達人達も遊びに来ていたのかもしれない。当時の自分に誰かに話しかけようという気などはなく、その存在に気づきもせず講義は終わった。SRMの存在を知った自分はそれから毎回欠かさず出場するようになっていた。大学二回生ともなれば流石に飽きてくるというもの。SRMはほぼ出場していた。結果は芳しいものではなく、Div1とDiv2を彷徨うこととなった。大学二回生冬]『理学部』という響きのよさに惹かれ理学部情報科学科へと進学した自分にやる気などは一切なかった。C言語を学ぼうという簡単な講義ですら単位を落とす有様。怠惰な者にも勤勉な者と同じだけの時間が与えられるもの。この膨大な暇をSRMの過去問埋めと蟻本周回により潰した結果、三回生の春にはレッドコーダーになっていた。現在の競技プログラミングの基準で考えれば、この選択は勤勉に見えるかもしれない。当時競技プログラミングの大会と言えばまだそんなに数ない時代[要出典]。Codeforcesもできたばかりで、25割の確率で開始を延長し、英語の問題文は間違いだらけ[出典不要]。就活のために練習する人間などもいない[要出典]。要は数学やパズル大好き人間のためのマイナー競技だったのだ[要出典]。当時の自分は競技プログラミングを練習することは膨大な時間の浪費であると考えていた。情報科学科の生徒は地下に席与えられ、そこで多くの時間を過ごすこととなる。自分もそれからの一年半この部屋で延々競技プログラミングと向き合うこととなった。これまで独りで練習を重ねていたが、ここでy3eadgzae[要出典]などの新たな仲間達とも出会った。非常に優秀でありながらも謙虚に学びの姿勢を貫く、正にお手本とすべき学徒であった。今の自分があるのも彼らのおかげであると言って過言ではないだろう。彼らからは多くの煽り方を学んだ。競プロのことはtwitterから学んだ。当時twitter上でお世話になった人にhirose_golf氏やogiekako氏などがいる。彼らのような黙々と問題に取り組み難問を通すストイックなタイプの人々も今となっては懐かしさを覚える。自分の競技プログラミングの能力が一番高かったのもこの時期だ。当然と言えば当然であろう。500日もの間、蟻本周回やCFとSRMの練習、マラソンマッチに参加、もしくは秋葉原に散歩くらいしかしていなかったのだから。余談だが、牛ゲーという単語を誰が作ったのかというツイートなどをたまに見かけるが、あれは蟻本大好き人間の自分がこの頃に地下で呼び始めたものである。名前をつけるほどに重要視し練習を重ねておきながら本番で通せたことは過去に一度もない。現在]一年半に渡る地下生活を終え、自分を待っていたのは信じられないような幸運であった。外資系のソフトウェアエンジニアの給料が異常に高いという新事実。エンジニアの面接はホワイトボードコーディングをするだけという圧倒的競技プログラマ優位。企業も競技プログラマに目を付け始め、大会は増え、裾野は一般のプログラマーにまで広がり、レッドコーダーはモテはじめ、腹筋が綺麗に割れた知的な彼女ができました。運良く卒業後もそれなりにいい生活を送れているように思われる。競技プログラミングにおけるエッジケースの如く、サイコロを振ったら六が千回続けて出たかのように。あとがき結果として僕は大学の学部生活の大部分を競技プログラミングに捧げた。僕が大学二年生で丁度競技プログラミングを始めた時に、四畳半神話大系というアニメが放映されていた。ある僕達は大学入学時の行動で分岐する”もしも”の世界における数々の『私』を見ることとなる。大学入学時にテニスサークルに入った場合の『私』。映画サークルに入った場合の『私』。秘密組織に入った場合の『私』。そのどの平行世界においても『私』は満足をしない。僕はそのアニメを見てこう思った。calendarで自分語りポエムとか書いてる人がいて、実際問題ポエム読むの結構おもしろいなと思ったから自分で書いみた。最初は自分のことを極力省いて、自分の視点から見た他人のことや環境の変化だけを書こうかとも思ったけど、よく知らない人の名前出したら怒られそうだったからやめた。実際y3eadgbeaとか地下で煽りまくるハラスメンティスト筆頭みたいになっちゃったし。四畳半神話大系は言及したかったけど、アニメに影響されましたなんて書くのは凄く恥ずかしい。その部分を省いた結果として布教するだけになってしまった。真面目な話、最近感じてたことだけど最近のプロコンはポップな感じがするなぁと書いてて再確認した。自分の心境の変化かもしれないけど。最近のは皆で一緒に勉強して能力を上げて素晴らしい未来をみたいな感じ。topcoderの背景が黒くてatcoderの背景が白いのの関係とか、あとは薄暗い地下の陰気さとか色々な要因もありそうだけど。実際問題、ほぼ全ての面で今の方がいいのは確実なんだけど懐古厨なので昔を懐かしんでしまう。俺よりも昔からやってる人からは、蟻本ある時代の人間が何語ってるんだよって言われそうだけど。ちなみに、文中に出てきたKMCoderっていうのもそういった俺の始めるずっと前の時代のものらしい。wataさん(基本全部ABC順)などの真にヤバイ人々が練習に使ってた。あと今ググったらニコニコ大百科に記事があった。http://dic.nicovideo.jp/a/kmcoder全体の感想は、プロコンに出会えたのとか、自由に使える時間が膨大にあったのとか運良かったことかな。変人B氏のおかげで出会えたということには結構なひっかかりを感じてしまうが。20142日目の記事です。マラソンマッチの問題は機械学習系と最適化系の2種類からなります。本記事はTCOでも出題される最適化系について書かれています。みんなで最適化してTCOに行きましょう。"こまか~い"マラソンマッチにおける問題は多岐に渡るものの、使われるアルゴリズムは焼き鈍しかビームサーチであることが多いため、実際に過去問を解いたりコンテストに出たりして練習を積めば強くなれる競技だと僕は思っています。マラソンマッチは回答があるわけでもないので過去の問題を解いてみても新しい知識が入るわけではなく、ちゃんと練習になっているのかわからず少し辛いものがあります。本記事では1人では気づきにくいちょっとしたコツや僕なりのやり方等を軽く纏め、これから練習しようという人の手助けが出来ればと思います。巷には素晴らしい記事が溢れているので詳細な個々のトピックについては触れません。本記事は、以下の記事をきっちり読みんだうえで少しマラソンマッチに触った後に、軽く眺めておくくらいが有用だと思います。何を勉強すればいいのかわからない山登りと焼き鈍しとビームサーチが必須になります。高速化が重要になることが多いため累積和(いわゆるimos法)も時たま使います。ほとんどの場合これらしか使わないにも関わらず、強い人は概ねいつも強いのでこれらを練習を通して身につけることが大切そうです。言語はどれがいいのか高速に動作するという点ではC++が圧倒的に有利です。C++以外を使う強いコンテスタントもいますので何か利点があるのかもしれません。ちなみに、そういった人々も速度が重要な問題では途中からC++を使い始めることが多いです。Topcoderサーバー上では時間取得関数が非常に遅いTopcoderサーバー上では、時間を取得する関数(timeやgettimeofday)はローカルの数千倍、数万倍遅いため、これらの関数をあまり呼び出しすぎない工夫が必要となります。C++だとサーバー上でも高速に動作するrdtscを使用することにより、これを回避することができます。rdtscはクロック数を取得する命令なので、TCサーバー上で一秒間に何回クロックが振動するかを測定する必要があります。32);}Topcoderサーバー上でうまく動かないor劇的に得点が下がる九分九厘C++におけるメモリ外アクセスのせいです。配列のメモリ外アクセスを検知するコンパイルオプション-fsanitize=addressをつけると自動で検知してくれます。STLをデバッグモードにするコンパイルオプション-D_GLIBCXX_DEBUGもつけると安心です。以下のようなaliasを設定しておくと幸せかもしれません。-O2'これ以上改善できそうにない(貪欲や山登りを使ってる)貪欲や山登りを使っている場合は大抵焼き鈍しやビームサーチ等に変えることにより大幅に得点を伸ばすことができます。なくとも、同じアルゴリズムをパラメーターを変えて何度も実行して一番いい結果を出力することにより改善はできます。時間を使い切るタイプのアルゴリズムに変えるのがよさそうです。これ以上改善できそうにない(時間は使いきってる)ビジュアライザを眺めていると改善案が浮かびやすいです。プログラムの出力よりもよい解を人力で見つけることができたら、そこをカバーできるようにプログラムを変えれば大抵スコアは上がります。実際ビジュアライザを改造する人も多く、強い人ほどビジュアライザに力を入れる気がしてます。これ以上改善できそうにない(ビジュアライザを見てもどうしようもない)上位陣との開きが小さい場合は案外改善できるので諦めずに頑張りましょう。小さい改善をむりやり繰り返しながら何かに気づくのをぼちぼち待つのもありかもです。高速化、特定パターン用の実装(小さいケースのみ高速に動作するアルゴリズム等)、最終回答に対する最後の山登り等があります。上位陣との開きが大きい場合は自分なりの楽しみ方を見つけましょう。いいアイディアがあったので実装したがスコアが伸びなかったプログラムもしくは考えが間違ってることが多いです。プログラムが間違っていれば直して点数があがり、考えがおかしい時はちゃんと考え直す機会を得ることとなります。どちらにせよスコアをあげるチャンスなので原因はきちんと明らかにしておいた方がいいです。良さそうな状態にボーナスポイント」という形になります。「ランダムプレイアウト」などを使用します。評価関数が重いということはよくあります。評価関数の近似値を求めるだけであれば高速な実装も可能であることが多いです。「n個の物質の静電気力の総和」という評価関数の場合、正確に計算するとあまりにも重いです。そこで、ある程度遠い物質間の力は無視することにより高速な擬似評価関数が作れます。この擬似評価関数は高速ですが不正確です。実際には速さと精度のトレードオフを追求することになる。乱数を質のよいものに換える広く使われている乱数用の関数は線形合同法を使っていることが多いですがあまりよくないらしいです。マラソンでは一般にXorshiftが使われますが、メルセンヌツイスターなども有名です。僕は基本はXorshiftを使い、最終提出時に一応いくつか試してみて一番いいのを使ってます。0x7fffffff;}条件分岐がバグっていて一度も実行されていない行があることに気づいたコード網羅率という概念がテスト技法にあります。お手軽な方法として、gccを使っていれば以下のコマンドで簡単にどの行が何回呼び出されたか調べることもできます。140:}p[i]%の確率でfunc[i]を実行したい時とかコード1ようなものはよく見ますが、制御が難しくなって思い通り調整できなくなってくるのでコード2の方がいいように思ます。func_2();コメントを書く2013-12-26Komaki法23:35iwi先生がiwi法とか呼ばれ始めててずるい。calendarでブログ書くの旬なので作って書いた。しめじ:ぼくの師匠のkomakiが最後の問題で嘘解法を20回くらいサブミットし続けてジャッジを圧殺して最後は通してましたDを持つ者:時代はジャッジの圧殺。Komaki砲:WAを大量に送りつけた後、ACすること。解説:2~5時間ほどしかない競技中に、同じ問題に対して20(50を越すことも)ほどのWAを叩き出しつつも最終的にはACされるということがプログラミングコンテストにおいては稀に起こる。WA中は本人も辛いし、ジャッジキューが詰まり他人も辛い。非常に悲しい行為である。半面、その愚直さや真摯さは感じさせるところもあるので、それを成し遂げた人物はオンサイトイベントにおいて初対面の方々に賞賛されることが多々ある。本人はこの行為をあまり快く思ってないので実際反応に困る。難しい問題に挑戦する向上心、諦めない心、挫けない心。:結構どこでもやらかしているが、どこでやらかしたかあまり覚えていないので僕のcodeforcesのsubmissionsのリンクを貼っておきます。232Dを120WAの3日後にAC。164Eを30WA後にAC。flowすることに気づいたときに回避する、あの使用時の前提からして少し愚かな感じのするやつですか。}でメモを埋めといてから呼び出すんでしたよね。これ結構ダサいんで、もうちょっとカッコいいので僕を思い出してください。2012-10-19最小カット最小カット01:19この記事は壊れてます。18:48こんにちは。