https://icfpcontest2019.github.io/
https://github.com/tomerun/icfpc2019
一人で参加した。一人でフル参加したのは何気に初めて。
会社で問題を読んで、帰宅して環境整備から取りかかった。
最低限の目標として、コンテストの順位は二の次で、快適に解答を実行できる環境を整備することに置いていたので、ライトニングは無視です。
AWS Batchで並列実行できるようにすることをもくろむ。そのためにDockerイメージを作る。
Crystalで書くつもりだったのでCrystal公式イメージをベースに作った。
実際の動作はソースコードに同梱したシェルスクリプトを実行して行わせるので、Dockerでやることはs3からソースコードとテストデータを落としてきて、ソースコードを解凍して中にあるスクリプトをたたくだけ。パラメタ的なのは環境変数で渡す。
なのでイメージに必要なのはawscli（とそのためのPython）くらい。
けど入れてみたらイメージサイズが700MBくらいになってECRへのアップロードがメッチャ時間掛かっていたので一旦停止して、Alpine Linuxのイメージから自分で作ることにした。
だがCrystalがすんなり動かず、依存パッケージを自分で色々入れないといけないらしい。
https://github.com/sam0x17/crystal-alpine/blob/master/Dockerfile
これを参考にしたけど、最新より一つ古いバージョンの0.28.0で試したものっぽいし、結局これらインストールしてたらイメージサイズも別に小さくなってないしで、結局最初の方針通りcrystal公式イメージから作った。だいぶ時間ロス…
あと結果を入れるためのRDSも立ち上げて、テーブル定義しておく。
ややこしいエンティティ間の関連があるわけじゃないし保守性の制約も緩いから、RDSじゃなくてDynamoDBのほうが適切そうな気もするけど、NoSQL本格的に使ったことないのでとりあえずRDBで。
イメージの準備ができたのでAWS Batchでジョブを定義していく。
初見では概念が色々ややこしいけど、クラスメソッドさんのブログを熟読してとりあえず動くレベルで設定をした。
昼過ぎぐらいにはジョブを投げて並列で実行されることを確認できた。初回はEC2インスタンス立ち上げからなのでジョブの実行が始まるまで数分かかることを知った。
入力パーサを書き始める。ソルバで使うことを考えて情報を色々リッチに持たせていたらだいぶ時間かかってしまった。
各テストケースを画像化しようかと思ったけど、Crystalに良い感じの画像ライブラリがなさそうだったのであきらめた。
このあたりで開始から24時間が経過して、仕様が出そろった。けど最後に出てきた追加仕様は弱小一人チームでは手が足りなすぎて無視するしかないやつで、はい…という気持ちになった。
ライトニングの順位表凍結が解除されたので、とりあえず順位表情報を10分おきに取得しておく。これはLambdaを使って定期実行した。コンテスト中には何も使わなかったけど、グラフ化でもしてみるつもり。
ひとまず正の得点を出すべく、単純に直近のまだ塗っていないところを塗りに行くグリーディーソルバを書いていく。
最初は単純なソルバからと思っていたのと相反して、Extension of the Manipulator使ったり、直近3歩だけは全探索して一番塗れるパターンを探したり、などいろいろやり始めてしまい、動かせるものになったのはこの日の21時くらいだった。
これで実行環境に投げて実行されている間に、DBからベストな結果を取ってきて提出用のzipにするスクリプトを書き、出てきた結果を提出してみた。
するとちゃんと点数が出て、しかも想像していたよりだいぶスコアが高く、一人で盛り上がった。
テンション上がってきて、Fast Wheels使うのとか、ブースターが近くにあったら優先的に取りに行くのとか、小さな非連結成分を塗り残していたら優先的に塗りに行くのとか、5時近くまで実装やってしまった。
Extension of the ManipulatorやFast Wheelsは取ったら即使うように決め打ち。
Manipulatorの追加位置は、本体から遠い箇所が選ばれやすいようなランダムで。
引き続きテンション上がっているので9時過ぎぐらいから活動開始。
ビジュアライザで見ると明らかに塗り残しがあるまま先に進んじゃっているのが見られるので、これをなんとかしたいと思う。
直近のまだ塗っていない所を探すときに、現在位置からの距離が直近な場所ではなく、ボットに「ベース位置」みたいなものを決めて、そこからの距離が近い場所を塗りに行くようにした。
あまりにも遠いところになってしまう場合は、現在位置をベース位置としておき直す。
本当はもっと大局的に、盤面をざっくりとグラフ構造としてみてTSPで経路最適化、とかをやりたかったが、シンプルに実装する道筋が見えず、アドホックな改善を積み重ねる形になってしまった（初日の環境整備に使った時間がなければ…）。
Fast Wheelを使ったときの探索がバグりまくって苦しかった。スピードアップしてると細い道から脱出できずに行動できないことがあるとか、最初想像できていなかった…。
自前チェッカのようなものは準備していないので、公式のビジュアライザでちまちま動かすのつらい。
残り5時間くらいで、まだDrill,Teleport,Cloneを使えていない状況で、それらを実装するか、ブースターは捨てて探索を賢くするのを頑張るか迫られた。
が、せっかくある仕様はできるだけ実装しておきたく、ブースターを実装するほうを選択した。
まずDrill。これは取ったらすぐ使うわけではなく、近い位置に塗り残しがなくて次にどこを塗るかBFSするタイミングで、Drillを使ったとした場合の探索も行い、時間が短くなるようなら使う、とした。
Drillを使うことにどれくらい効果があったかはよくわからないが、プラスの意味はあったと思う。
そしてClone。これはLambda Coinガン無視チームにとっては80ケースしか影響しないのであまり気は進まなかったが、やらないとその80ケースが壊滅的になるのは明らかなので、仕方なく実装した。
本当は分裂したBotたちを上手く協調させることをやらないといけないんだろうけど、各Bot独立にこれまでのアルゴリズムで動かしただけ。
それでも目に見えて結果は良くなったので、さすがにやって良かったという気になった。まあトップのスコアから見たら、ひどいゴミが多少マシなゴミになったくらいの変化ですが…。
Teleportは上手く使えそうに思えなく、時間もなかったので無視することになった。
終了1時間前に、最後の実行としてジョブを投げまくっていたら、インスタンスがkillされることがちょこちょこあってちょっと焦った。スポットインスタンスでやっていたので、リザーブドインスタンスの環境も急遽立ち上げ。
それでも一部ジョブの実行がなかなか始まらなくてやきもきさせられた。
これ、実行開始のレイテンシが気になるときは、Minimum vCPUを大きめの値にして常時インスタンス立ち上がっている状態にしておくものですね…（学び）。
手元で十分なバリデーションができてなくて、提出したらFailedになるのが怖いので、実行途中で何度か提出して様子を見る。無事最後まで全部validな解になっていて良かった。
ちゃんと環境作れたのは大変良かった。手元でスクリプト一つ流したら勝手に実行して結果を保存してくれるのは最高だ。
これ、マラソンマッチとか他のコンテストでも役立ちそうなので使えるように整備しておこう。
今回は画面は何も作らなかったので、次回はダッシュボード画面を頑張りたい。まあ一人チームでは自己満足にしかならなそうだけど、楽しいのが重要。
ソルバーのほうは、仕様を実装するので精一杯という感じで、全く詰められた感じはしないなあ。
探索ロジックはだいぶアドホックになりすぎたきらいはあって、最初からもっと大局的に考えられれば良かったのかなあという感じ。未実装仕様が残っていることによる実装プレッシャーがあると、じっくり考えるの難しいが…。
クラウド費用は1800円くらい。ソルバ実行をガンガン動かしたのは最後だけだから、こんなもんか。
全部東京リージョンでやってたけど、計算サーバーは別に東京である必要なかった。リージョン変えたら多少節約はできる。
これは Competitive Programming (1) Advent Calendar 2018 10日目の記事です。
僕が初めて参加したプログラミングコンテストは Google Code Jam 2008 なので、今年でプロコンに参加し始めて10年です。
これまでにあったことを振り返ってみます。
小学校にパソコンが導入されて、初めてコンピュータを触った。といっても置いてあるだけで何ができるものなのかさっぱり不明で、昼休みのゲーム機としてしか使われてなかった。
誰が買ってきたのか忘れたけど家にパズラー（昔とても人気があったパズル雑誌）が1冊あって、ハマっていた。一度解いた問題を消しゴムで消してもう一回解いたりしてた。
中学校か市かの図書館で、数学オリンピックの本を見かけて興味を持つ。内容は全然わからない。
大学受験にむけてだいぶ数学を勉強したので、ようやく数学オリンピックに出てもよさそうな気がして参加した。
センター試験そっちのけで過去問10年分くらいやったおかげで、予選はボーダーちょうどで通過できた。けど本戦はさっぱり。「こういうの、完全にそれ用の訓練をしとかないと無理でしょ」と感じた。
関連して、灘や筑駒の数オリ金天才中高生！！！ みたいな記事を見て、ほへーそういう世界もあるんだなあ、と思うなど。
大学のオープンキャンパスでスタッフしてたとき、資料として置いてあった情報学科の後期入試問題が目にとまった。こんなの。パズル/競プロっぽさありますよね。
高校生の時にこれを知ってたら情報学科に興味を持っていたかもなぁ、と思った。
バイト先にExcelで組まれたシステム（マクロも使っていないのでシステムというほどのものでもないが）があって、触れる人があんまりいなかったのでExcelを覚えてちょこちょこ改造したりしてた。
大学では化学専攻だったものの、この先それを続ける気もあんまりなく、だったら経済的に余裕もないし大学院行かずにさっさと就職してしまおう、と考える。
プログラミングとかほとんどやってないけど論理パズルみたいなの好きだし、まあこれから勉強すれば普通の人よりはうまくやれるんではないか、ということでソフトウェアエンジニアを目指す。
一応、情報処理演習の授業で、Fortranを使って簡単な物理シミュレーションを書くというのはやったくらい。
運良く、未経験歓迎地頭学歴採用みたいな感じ（？ 実際のところは知らない）のところに引っかかって就職できた。
就職に備えての準備として、学生のうちに基本情報技術者を取るくらいはしておいた。
就職。
自然言語処理系の部署を希望してたけど何も経験・業績ない人がそんな仕事できるわけもなく、アプリケーションエンジニアをやる。
とにかく一々わからないことだらけで基本情報技術者取ったくらいじゃあ全然足しにはなりませんなあ、という気持ちになった。
コンピュータ扱う人たちの職場なので行動様式もいろいろ厳密だったりするんだろうか、と思っていたけど、そんなことはなくて、ちゃんと定義されていない言葉が使われたり（例：「ビルド」というのはコンパイルするだけのことですか、jarにまとめるまでのことですか、デプロイするところまでですか）でそんなに特別なことはないんだ、という感想だった。
あと、コンピューターサイエンスっぽい数式を触って…みたいなのはほとんどなく、複数人開発だから結局ボトルネックは人間系、みたいな感じで少々イメージとのギャップはあった。
まあ、地道に黙々実装するのはそれはそれで楽しいのですが。
Project Eulerを発見して、埋めていってた。憧れていたけど実現できなかった、コンピュータと数式を使って問題を解く（人工的な問題ではあるけれども）、という営みが楽しくてハマる。
My Job Went To India を読んで、TopCoderのことが触れられていた。この名前を見たのはこのときが最初だと思う。
あと 日本語による最初のTopCoderの紹介として有名なITMediaの例の記事 もたぶん見てたんじゃないかな。
Google Code Jamの紹介記事 を見て、何これ面白そう！と思って参加した。
結果は、Round1は通過できたけどRound2でまったくわからなくてTシャツ取れず。
このときは「予選で 500 位以内の方は、最寄りの Google オフィスで行われる準決勝にご招待します」だったんですよね…。超大盤振る舞いだ。
数学パズル的なプログラミングは割と自信があったものの、全然太刀打ちできなかったので、これはもうTopCoderで鍛えるしかない！ となって、SRMに参加し始めた。
そしたら、世界中の数学・パズル・プログラミング好きな人たちとネトゲっぽく競えるのが楽しくて完全に沼に落ちてしまった。
ちょうどはてな界隈で ハチロク世代 が盛り上がっていたので、（1986年生まれからはちょっと外れるけど）参加して、そこのメンバーでSRMのたびにskypeチャットでワイワイやってた。
Imagin Cupで3位になって話題になっていた chokudaiさんが参加してきたりして、うわぁ有名人が来たーとか思っていた。
2008年の終わりくらいには黄色に定着した感じ（Easyしか解けてないけど）。
ちなみに、このとき自分が書ける言語がJavaだけだったのでJavaで参加してた。それを今までずっと引きずっている
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上の記事で見るだけだった人からフォローバックをもらって嬉しくなるなど。
SRMで赤くなった。TopCoderのコンテストは59回目だった。TCO予選でぐぐっとレーティングを上げられたのが効いた感じ。
診断人さんがニコ生でTCO会場から中継をしていて、激アツ展開に見入った。
この年のICFPCはめっちゃ面白かった（車のやつ）
それと、技術力の幅を広げたくてCTFに初めて参加。これも面白い。 http://d.hatena.ne.jp/tomerun/20101129/1291048564
これ以来、CTFにも年1,2回ほど参加するようになった。
せっかくプログラミングコンテストでアルゴリズム勉強しているので実用に使えるようなこともやれないかと思い、機械学習をちょっと触り始めた。PRML読書会に参加しに東京へ行ったり。
それに合わせてUTPCの懇親会にも参加した（確かオンサイト会場もあったけど参加は東大関係者限定だった）。プロコン界の多くの有名人の方々と初対面。
マラソンマッチで本格的にスポンサーコンテストが始まり、機械学習を勉強し始めたこともあって参加してみた。結果は惨敗で、これはこれで別のノウハウがいるね、となった。
スポンサーコンテストが入るようになったせいか、だいぶ通常マラソンの回数が減ってしまって悲しみ。それでもこの年のうちにマラソンも赤到達。20回目のコンテストだった。
短時間コンテストの情熱はだいぶ落ちてきて、過去問を解いたりといったコンテスト向けの練習に時間を使うのはやめることにした。
codeforcesがこの頃から盛り上がってきていたと思うけど、そんなわけで、参加はたまに時間が合えば、という程度で。
KUPCオンサイトに参加しに京都へ行った。ここでもプロコン界の多くの有名人の方々と初対面できて、数年ぶりの京都ということもあり、大変楽しかった。
Google Developer Day の DevQuiz（イベントに参加するための予選）の最終問題がマラソン問題だったので、時間をかけて取り組んで満点を取った。
満点を取った人だけが参加できるハッカソンにも参加したけど、Web周りの技術のことがまったく分からなくて丸一日座るだけをした。
色々あって転職した。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
やっぱりアルゴリズムっぽい仕事がしたい！ となって転職した。
ローレイヤー高速化の仕事を希望してたけど何も経験・業績ない人が（略）、組み込みエンジニアをやる。
この頃から数年間、JAGに細々と問題を提供していた（ICPC参加経験なくてもJAG入会できるんですよ）。関連して、AOJでICPC過去問をぼちぼち埋めたり。
CodeIQでマラソン問題を出題した。 https://togetter.com/li/559726
1位になったmachyさんがかなり工夫したアルゴリズムで解いていて感激した。
ICFPCに初めて合宿形式で参加し、なにやらうまくいって2位！
この年はコンテスト期間中めちゃくちゃ暑くて、そればかりが印象に残っている。
前の年の年末からKaggle Santa問題に真剣に取り組んで、5位に入った。正直サンタコンペはマラソンマッチとしては問題が微妙なことが多いんだけど、この回はかなり良かった。
機械学習マラソンにもう一度参加してみたらやっぱり惨敗した。難しい…。
代休が大量に溜まってたので、TCO Marathon予選に全投入して14日間ひきこもりマラソン生活を送ってみた。が通過できず、時間を費やせば良いというものでもないんだなあという学びを得た。
と同時に、全然人と喋らなくてもちょっとTwitterやっておくくらいで（少なくとも主観的には）社会性を維持するのには大丈夫であることがわかった。
CodeChefのlong contestがマッタリやるのにちょうど良いということを発見して、ときどき参加するようになる。
この年の後半くらいから身の回りが大変になって、コンテストはとんとご無沙汰になる。
AtCoderが国際化・レーティングシステムを開始して、自分の状況的にも変わってきたのでコンテスト参加復帰。
AtCoderの問題は知識不要なことが多くて、訓練をサボっている自分のような人にとっては取り組みやすくて助かる。
色々あって転職した。仕事でアルゴリズムっぽいことはやらなくても良いので、普通にアプリケーションが作れるようになることを目指していこう、プロコンは趣味で参加を続けられる環境を得られればいいや、と方向転換。
DNA解析のマラソンマッチが面白かった。結果はダメだったけど… https://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=16683&pm=14187
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を埋めたりする。
またTCO MarathonでFinal進出できた。今年はだいぶ運によるものだった感じはあるけど…。
さすがに海外旅行3回目ともなると慣れて余裕が出てきた。これからもまだまだ参加したい。
社会人枠が広いオンサイトコンテストが増えてきて、BitFlyer、SoundHound、HTTFの本戦に参加。ありがたいことです。
会社でのコンテストも引き続き開催。問題の質を保つの大変だぁ。
プログラミングコンテストに参加してなかったらどういう暮らしを送っていたのか、想像できないですね。
次の10年も楽しんでやっていきましょう。
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して使うのも可。
除算・剰余算は遅いのでできる限り取り除きます。
その１：焼きなましの受理判定のときに発生する温度での除算は逆数の乗算にする
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); }
その２：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で詰め込もうとしたら、今度は大幅に遅くなりました。さすがに自前でマスクしてシフトして、という処理があちこちに入るとそのオーバーヘッドの方が重かったようです。
状況によっては、頑張って詰めた方が良い場合もあるとは思います。
普通はフィールドのデータは 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にする、とかもこれに含めて良いかと。
やり過ぎると命令メモリが増えることによりアクセス局所性が悪くなって遅くなっちゃいますが。
上でも書きましたが、第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をクリア } }
ナイーブにやると次のようになります。
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++;
Competitive Programming Advent Calendar 2017 2日目の記事です。
近年のAdvent Calendar執筆ハードル上昇に対抗するため簡単な記事にします。
皆さんご存じのように競技プログラミングは役に立ちませんが、マラソンマッチやってるとたまに役に立つので役に立ったことを書きます。
短時間コンテストでは自分でクラス作ったりすることはそんなに無いかもしれません。一方、マラソン系コンテストで実装が重めのやつは1000行超える規模になって、ある程度は関心事の分離ができた構造になっていないと扱いづらく、なかなか死ねます。
また、整理されたコードを見るのは気分的にも良い。何度も同じコードを見ることになるのでこれは重要です。
短時間コンテストだと最悪計算量しか気にしませんが、実データで最悪ケースが来ることはそうそう無く「実際はどんなデータなのか？」を計測・分析して、実用上速いデータ構造・アルゴリズムを使うことになります。
プロコン以外のプログラミングでもこういうのが大事なところは多いかと。
解答やテストデータの様子を確認するためにHTML+JavaScriptでツールを作ることはよくやります。場合によってはちょっとしたwebアプリ立てることも。
高速化やったところで最終的なスコアにほとんど意味ない場合も多いですが、わかっていてもついやりたくなっちゃうんだよね〜、ということを身をもって実感できます。
また、いざ高速化やるぞと取り組むときにはプロファイラ使ったりアセンブラ眺めたりして、これはこれで相当実用的な経験になります。
マラソンマッチの終盤には、最適な答えを出すパラメタの探索をやります。これは機械学習のモデル作成でも課題となってくるところであり、ノウハウ知っておくのは良さそうです。
（僕はグリッドサーチしかやったことないですが…）
また、計算の実行にクラウド使うことも多いので「クラウド環境の活用経験あります！」と言えるようにもなりますね。
英語に慣れなければという気持ちはあるものの、でも慣れていないので英語を実用で使う機会が得づらい、というスタートアップ問題がありますが、forumに書き込むのは自由なので貴重な機会になります。
他の書き込みを見ていると「文法無茶苦茶じゃねえか！」みたいな投稿がわりとあって勇気づけられることも。
マラソンマッチをやろう！
16時の飛行機で成田から出発。空港に着いたのは2時間弱前で、サンドイッチ食べるくらいの余裕はあった
こういう話があるので今後はもっと早く行った方が良さそう http://www.afpbb.com/articles/-/3148112?cx_position=34
12時間かけてワシントンまで行き、そこから乗り継いでバッファローまで。
乗り継ぎの間は1時間40分で、入国審査のカウンターが一つしか開いていなくて、列がなかなか進まず出発時間ぎりぎりだった。空港内をリアルマラソンしてなんとか（5年前と同じ…）
飛行機内では、機内誌を読んだりiPadで本を読んだり。仕事しようかとも思ってたけど、照明落とされるのでPCを開く気になれなかった。
機内誌にスタンディングデスクの広告が2つ載っていた。流行りか…。
現地時間の17時頃にバッファロー到着。Topcoderの手配でホテルまで送ってもらう。mugurelionutさんと一緒だった。
やっぱりホテルの部屋が一人には広すぎで落ち着かない。
ホテル近くのスポーツバーで夕食。サンドイッチやハンバーガーを頼んだところ、やっぱりアメリカンサイズのが出てきてワイルドだった。
朝食はホテルのバイキング。食べ物の種類は少ない。飲み物の種類が多く、持ち帰り用のカップがあるのは良い。
この日は夜にWelcome Receptionがあるだけなので1日オフ。chokudaiさんとりんごさんはナイアガラの滝に行っていたが、僕は体を休ませたいのと英語キーボードの練習をしたいのとでホテルに残る。
持参したキーボードでAOJの軽い問題を解いたりしてた。
昼食はホテル近くのdomino's pizzaで。焼きたてのピザおいしすぎる…。
19時からWelcome Reception。会場はホテルとは別で、大学？研究所？のキャンパス。そこが今年のTCOのメインスポンサーでもある。ホテルから徒歩15分くらいで、シャトルバスも出ている。
バスがいつ来るかよくわからず、歩いて向かっているグループについて行った。
会場について参加賞をもらう。なんかノベルティ少なめだ。5年前に会った他のコンテスタントの人たちに挨拶する。
Marathon参加者の人たち、すでにデスクで各自準備を進めている。本来はコンテスト開始30分前からなんだけど、やっちゃっていいのかなあ…と思いつつ自分もやる。まあ、やることはそんなに無いのだけど。JDKが入ってなかったのでインストールしたくらい。英語版Windowsは普段使わないのでPATH通すのに手間取ったりしてた。
デスクの環境はこんな感じ。
MilaninさんがMM95の画像を表示していた。
朝は会場まで徒歩で行った。空気が気持ちいい（気温は東京と同じくらい）。
9時-19時でコンテスト。昼食として自席で食べられるサンドイッチを用意してもらえるのは大変ありがたい。
最初数分問題が開けなかったりしたけど、まあこういうのはよくあることなので慌てず待つ。
だいぶオーソドックスな問題だった。とりあえず問題を読んで、テスターのコードを読んでカスタマイズ（別プロセスではなく直接自分の解答を呼び出す・マルチスレッド化・出力に情報を追加）して、空解答を作って動かすまでが40分と、なかなか順調にいった。
10時間ではあまり難しいことできないので、基本的には近い所を取りに行くgreedy。それに評価関数の要素をいろいろ加えていく感じだった。ただ最後2時間くらいは、1位とはかなり差があったのに細かいパラメタ調整に終始することしかできず不毛だった。もうちょっと攻めるべきだった。
インタラクティブ形式でありつつ隠しパラメータがほとんど推測可能なので自分でシミュレーション可能という重要な特徴があるのだけど、それに最初気づいていなくてこの特徴を解答に取り入れることができず、残念。
やっぱり慣れないキーボードだとかなりタイピング速度が損なわれるので、次回は自分用のキーボードを持ち込もうと思った。
終了後は会場で夕食を取りつつAlgo Semifinal1を見る。
ホテルに戻ってからはTopcoderスタッフの方に連れられて2日前に行ったのと同じバーで軽く飲み。
さすがに前日は疲れたのでゆっくり目（8時半くらい）の起床。
一人で座って朝食を取っていたら、mugurelionutさんとmarek.cyganさんがやってきて、それからPaulJefferysさんも来て会話していた。途中からヨーロッパにおける政治事情の話になってまったくついていけず置物と化していた。
コンテストの問題についてとか、トピックが限定されていてなじみのあるものならまだなんとかコミュニケーション取れるのだけど…。
昼からナイアガラの滝を観に行った。会場からシャトルバスが出ており、25分ほど。
時間そんなにない＆お金それなりにかかるということもあって、滝の下までは降りずに上を歩いて回っただけだけど、カナダ側は一帯が水しぶきで覆われていて、雨が降ってないのにずぶ濡れになる感じで満喫した。
帰りのバスの時間がわからず2時間待つ羽目になり、AlgoとMarathonの人は参加してね！と言われていたData Science Workshopには参加できなかった。
会場に戻り、UI PrototypeとDevelopmentのコンテスト風景を眺めた。みんなハッカソンガチ勢っぽい。使われているエディタが、Atom,VSCode,Sublimeなど様々に分かれていて、Developmentでは使われている言語も様々で面白かった。
翌日の飛行機が早いので、この日は早め（6時）に起床。
朝食後に会場へ。UI Design部門のコンテスト風景を眺めた。
このへんのコンテストの種類について書いておくと、こんな感じ。
あと、TCOブロガーであるgorbunovさんがたたずんでいたのでいろいろ話した。
午後からAlgo Final。りんごさんの応援をしつつ観戦する。
その後閉会式・結果発表。ニューヨーク州の副知事が来ており、挨拶がいかにも政治家という話しぶりだった（ちなみに開会式にはバッファロー市長が来ていた）。
移動してバー的な店でclosing reception。
Nickolasさんにマラソン問題を作るときに考えていることについて聞いたり。
タコス食べたら相当おなかいっぱいになった。
飛行機が朝7時発なのでホテル出発が5時。眠い…
空港で軽い朝食を取って、まずはシカゴまで。
シカゴで4時間待ち。空港をうろついたりサンドイッチ食べたりだらだらしたりしていた。
その後成田まで13時間。本読もうとしたがなんかもう目が乾いてダメだった。半分寝ていた。
16時頃に到着。いったん会社に立ち寄って雑務やってから帰宅。
この日はまだ興奮してたのか6時間弱しか寝れなかったけど、次の日に13時間寝てしまってだいぶ疲れてたのだなあと。
また来年参加できるようがんばろう。もっとコミュニケーション取れるように英語も（生きていて英語使う機会がTCOしかないので、これを逃すと一生習得できない）。