Hokkaido Univ.& Hitachi 1st New-concept Computing Contest 2017の反省
AtCoderで初の本格マラソンマッチ。楽しかったです。13位/302。最近のマラソンマッチ不振を考えれば良い結果だったけど、反省点も多かったです…。
（方針の公開がOKになったので、公開します。2ndがあるので、ちょっと迷いましたが、北大日立さんにとって良い結果が出たほうが、今後さらなるマラソン開催にもつながるので、公開します。）
ファーストインプレッション(2017/11/16)
- どういうデータなのか？
- 辺の数とか、平均でいくらぐらいなんでしょう？ →辺は思ってたより多い。100本以上辺があるのは普通。
- 最適解がわかるケースを逆につくれば便利。最適解を知っていれば、焼きなましをやってみたときに、うまくいってるかわかる。
- King's graphから作る
- 一定条件を満たせば、そこから辺を足しても最適解をキープすることは可能？より一般的＆難しい問題が作れる
- 三角不等式を満たすものは除去してもいい？
- このときに意図的に最適解をつくる操作が、逆の操作が近傍として有力な可能性はある。
- より簡単なケースで考えてみる。
- King's Graphではなくグリッドグラフにマッピングする場合は？二部グラフに持ち込める？
- 最大流かカット系で楽にできないか？
- 使えなくても、初期解として有効な可能性があるので、無駄にはならないと思う。
- King's Graphではなくグリッドグラフにマッピングする場合は？二部グラフに持ち込める？
- 過去の反省
- 類問の解法に固執しすぎ。
- 今回のは、TCO17 MM Round 1 TCO17 Marathon Round 1 (GraphDrawing) の反省 - じじいのプログラミングに似てる気もする。そうすると優勝したchokudaiさん解の重力モデルか焼きなましの中間っぽいのが有効なのか？
- ただ、ちょっと条件がちがっただけで、解法が全然違うことがある。まっさらでスタートしたほうがいいのでは。
- 類問の解法に固執しすぎ。
- 方針
- ベタに行けばこの問題は、ただの焼きなまし。そして、最後に焼きなましの解をダメ押しでGreedyするの忘れずに。
- 粗いグリッドで焼きなましから、徐々に細かいグリッドにして焼きなまし。
- ただし、先日tomerunさんと似た解法だったのにもかかわらず、自分だけ大敗したので、ちゃんと敗因を確認すること。特に、細かいグリッドになったときに調整できるかどうかもポイント。
- ランダムグラフの頂点間距離は使える？
- 高得点辺だけを使ったのGreedy・焼きなまし
- 1点や0点の辺は無視してもいいくらい。というか0点は最初から削っていいのでは。
- 何を焼きなまし？（「近傍の種類の多さが重要」と昔Komakiさんが言ってた）
- 頂点ベース
- 頂点ベース（位置を気にする。近傍は近くの点）
- 辺ベース
- 15点→0点で、辺をじょじょに開放
- 場所を後から、配置する解法はないか？よく、「置く場所を決める焼きなまし」→「何を置くか決める焼きなまし」のように、２段階に分けると良いこともある。
Submission 1 (2017/11/18) 52935点
同じ番号の頂点をマッピング。同点のみなさん多数。
その後、多忙で無事乗り越えたものの、休日に冷房病になってしまい、計１週間休み。すごく警戒してたのに…。
Submission 2 (2017/11/25) 129838点
場所2箇所の交換（頂点あるなしは気にしない）を100万回する山登り法。
Submission 3 (2017/11/25) 148673点
場所2箇所の交換（頂点あるなしは気にしない）を、9秒間する焼きなまし法。
Submission 4 (2017/11/26) 152871点
焼きなまし法の、温度を5度→1度にする。わりと効果があった。
ビジュアライザ
このタイミングでビジュアライザも追加する。 Siv3Dを今回も使いました。感謝→ Siv3D · GitHub）ビジュアライザは、
- 押すボタンごとに、いろんな近傍への遷移をリアルタイムで試せる。
- 頂点ごとに最高点と現在の得点を追加。ちなみに、最高点はベスト8の総和。
ただ、ビジュアライザをつくっても、なぜ問題が起きてるのかにちゃんと着目した情報を表示して、本質を見抜けないと意味がないので、気を付ける。
このchokudaiさんの記事はおすすめ（というか、悪い例にでてくるモデルは、たぶんわしじゃ…。）
chokudai.hatenablog.com
焼きなまし法の温度と得点、統計情報（どの近傍で、どれだけ上がったか）等も、グラフプロットに追加すればよかった。
Submission 5 (2017/11/26) 159335点
動かす頂点Aと、元グラフでつながっている頂点Bの隣に移動。上位の人が多く使っていた有効な近傍。
セカンドインプレッション(2017/12/26)
- 焼きなまし温度調整必須
- 15点の辺だけ使って、辺を少なくして、橋・関節点で分けて、
- 浮いている点の15とかは重要？
- 15,15,15,15,15,15,15,15,15,15,15,15,15,15,5,5,5 みたいなときは代替があるので、あとで決めていい
- 塊ごと移動できない？
- 番兵で、範囲チェックのifを減らせ
- 範囲広すぎだと、ダメかもしれない。60x60ではなく、範囲を狭くしたら。
- 範囲なしにして、あとからくっつけたほうがいいかも。
Submission 6 (2017/11/27) 159913点
- 元グラフでつながっている頂点Bは、高得点ベスト８の隣接頂点から選ぶ。かつ、焼きなまし法を2倍高速化
- この時点で、焼きなまし法のコツ Ver. 1.2 - じじいのプログラミングに載っている、
★★★★ 高速化がどれだけ効果的か検討する。
のも重要です。ためしに10秒だけやってる計算を、あえて100秒とかに伸ばしてみて、結果がどうなるか見てみましょう。
- 時間をかければかけるほどスコアが伸びる
- 高速化しよう＆スコアが素早く伸びるように次の状態を決めよう。山登り法に変えるのも良い。
- 時間をかけてもスコアが伸びない & スコアが高い
- 最適解がでてる可能性が高い。計算を打ち切って、余った時間を他に使う
- 時間をかけてもスコアが伸びない & スコアが低い
- 次の状態の決め方、スコア関数の見直しを再検討する。焼きなまし法を使わない法がよいときもあるのも忘れずに。
を試した。なんと計算時間を10倍にすると、30ケースあたり平均+5000増える！！（実際には30ケース*10セット）1位が狙える位置に行くことがわかる。
でも、10倍高速化するのは無理だろうなという考えと、まだ試してないアイディアがいっぱいあるので、まずそちらからやることにした。これが敗因の１つ…。
10倍で効果があるのだから、せめて、計算時間を5倍にしたら、計算時間を2倍にしたら、どれだけ増えるのか試して、それをみて高速化にどれだけ作業するか考えるか判断すれば良かった。
失敗したアイディア集
ここから点数がさっぱり増えなかった、ボツアイディア集。反省点の１つとして、結果の確認とまとめを、もうちょっとちゃんとしてれば良かった。失敗したアイディアの中では、点がほとんど変わらなかったものもあるけど、これは下手すると最終盤でちょっと点数を上げたいときに有効な場合もあるので。
初期値
初期値がわるいとダメなケースもある。特に、今回のは、わりとバラバラに頂点が飛んで非効率に見えたので、初期位置を中央に固めた。でも、すぐに結局バラバラに飛んで行って、スコアが上がらなかった。
バラバラにならないようにする。
中央に行くほどボーナス点をつけたり、KingGraphの隣に頂点があるときにボーナス点をつけた。バラバラになりにくくなったけど、スコアはだいぶ下がった。バラバラシャッフルっぽい動きは有効だったっぽい。
頂点Aを意図的に選ぶ。
頂点得点の最大値（頂点の辺ベスト8の合計）をあらかじめ計算しておき、交換する頂点を、以下のような基準で選ぶけど、これもだいぶ点が下がった。
- 低得点率（現在の得点 / 最大値）
- 得点差（最大値 - 現在の得点 ）
yowaさんのなんか他の人の解法をみるに、全てを均等回数を選んだほうがいいという議論もあるらしい。
同じく最初にシャッフルしたあと順番に舐めてた。たしかTopCoderマラソンの↓この回(KnightsAttacks)の感想戦で「焼きなましで変更加える箇所、ランダムじゃなくて順番でいいんじゃね？」みたいな話が出てたのを思い出した
— yowa (@yowa) 2017年11月30日
| TCO17 Lighting MM - Togetter - https://t.co/jAG3dXsMvd
次回は要検討。
隣接頂点Bの選び方
Submission 6「元グラフでつながっている頂点Bは、高得点ベスト８の隣接頂点から選ぶ」の部分が、あまりに雑だったので、ここはスコアは伸びるかなと思ったけど、伸びなかった。辺得点x,y,zだったら、選択確率は、pow(x,t)/(pow(x,t)+pow(y,t)+pow(z,t))のようにして、tを調整した。tが0なら全部等確率1/3, tが∞なら最高辺得点のだけが確率1になる。でも、スコアは伸びなかった。
さまざまな近傍
「近傍をたくさん作ったほうが勝つ」と、Komakiさんが昔言ってたので、いろいろ足した。
- 2-Swap
- 隣り合う2点を交換。A→B, B→A
- 3-Rotate
- 三角の形で隣接する3点を、A→B, B→C, C→Aのように移動。ある頂点Aを固定すると、三角形の選び方は12パターンある。
- 4-Rotate
- 四角の形で隣接する4点を、A→B, B→C, C→D, D→Aのように移動。
- スライド
- 縦 or 横 or 斜めに一列にならんだx点（2点～4点）を一方向に押してスライドさせる。A,B,C,Dと並んだ場所で、A,B,Cが頂点があって、Dが空きのとき、C→D, B→C, A→Bと移動させる。
それぞれに対して、全てのマスが頂点埋まっているバージョンと、そうでないバージョンを試した。また、近傍については確率で選んで調整する（辺隣接ワープ 95%, 2-swap 4%, 3-Rotate 1%とか、そんなかんじ）
- 空きマスが一部ある場合の結果は、概してよくなかった。
- 2swapについては、低得点の際には効果があるように見えたが、マッチの終盤にはほぼ意味がなくなったので、最終的には、これらの近傍は全てボツとなった。
また、本当なら、別な動きをする近傍をいろいろ作ったほうがいい。今回の3-Rotate, 4-Rotateは、2-swapで2回,3回で代用可能かつそれなりの確率で起こりうるので、あまりよくない近傍（ただ、それでも1回は試すべき。）
レプリカ交換法
ほぼやけくそ。N個の焼きなまし法を同時に走らせる方法。それぞれ別な温度を固定でもつ。一度やってみたかったので、やった。
レプリカ交換法 - Wikipedia
得点差に応じて、温度を入れ替える（状態を入れ替えるより簡単。）
これは、あまり有効でない。中途半端な得点の解がたくさんできるだけだった。特に、今回のように時間をかければスコアが伸びるケースでは、時間が1/Nになるのはもったいない。１つに集中して時間をかけたほうがいい。ただ、並列計算とかできる環境であれば、有効なケースもあるのかも。
プロファイラで高速化。
この時点で、最終日で、残り4時間ぐらいになってしまった…。Visual Studioの標準機能のプロファイラを使って、高速化する。しかし、時間が足りず、結局、以下の２つは高速化せずに終わってしまった。
- 番兵で範囲チェックをなくす
- ファーストインプレッションにも書いたのに。時間がなくなってしまった。番兵など、最終盤で、高速化するにはバグを埋め込むリスクが高いところは、もっと早めに高速化やったほうがいい。
- 焼きなましのexpの式
- あわててテーラー展開したやつを書いたけど、点が下がったので、怖くなったので、やめた
- 焼きなましのexpの式なんて毎回使うのに、高速化を最終盤にしようとして、おざなりになるのを繰り返してるのは、本当にダメである…。効果が少なくても、1度作れば一生使えるのは、暇なときにしっかり作りましょう。
自分のは、7000万回程度しか回らなじゃった。他の人は2億～4億ぐらい回っている。その中でもっとも怪しいのが、ケチらずintとかdoubleとか大きい方を使っていたこと。一般に、プロファイラはボトルネックにはすぐにきづくが、全体的に遅くなってる要素には気づきにくいので、要注意。ただ小さい型を使うのが、これだけ早くなるのは意外。キャッシュミスあたりが予想されるけど、今回のフィールドは小さいので、過小評価してた。自分がなんか誤解している可能性も高い。要調査。
その他
- お尻に火がついたのが、いつもより少し早かった。
- 若くないので、体調管理は大事。冷房病は徹底した温度管理で避けよう。
- 昔は、夜遅くなっても次の日なんともなかったけど、今はリバウンドがくるので、ちゃんと早めに寝たほうがいい。
- AtCoderさん、ありがとう！マラソンマッチでこんな問題を受注できるとは、本当にすばらしい。
Topcoder Arenaを起動する方法とJavaブロックの回避
はじめに
Topcoderで競技プログラミングをする場合、以下の２つの方法があります。
- ウェブ版（ベータ）TopCoder Arena
- アプリ版 Competition Arena
ウェブ版はずっとベータ版で開発終了停止している模様なので、懐かしのアプリ版を立ち上げたいところ（パスワード平文疑惑がありますが…）。でも、昔参加していた人が戻ってきても、ホームページが大改造されていて、はまりやすいのでメモ。Topcoderの登録は無事できているものとします。
アプレットArenaをダウンロードする
直接リンク Competition Arena
ちなみに、本家ページは以下の場所から行けます。一番目につくCOMPETE→COMPETITIVE PROGRAMMINGと行ってしまうと、ウェブ版（ベータ）が立ち上がるので注意
アプレットArenaをダウンロードする
そのままですと、「セキュリティ設定によってブロックされたアプリケーション」というエラーで、Javaにブロックされて起動できません。以下のように、例外サイトにhttp://www.topcoder.comを追加しましょう。
最小カットを使って「燃やす埋める」問題を解くスライドのフォロー
この記事は競技プログラマー向けです。
はじめに
以前、最小カットを使って「燃やす埋める」問題を解くというスライドを書きました。
これに対して、tokoharuさんから、『燃やす埋める』よりも『Project Selection Problem』を使うべきという、提言がありました。
『燃やす埋める』と『ProjectSelectionProblem』 - とこはるのまとめ
続：『燃やす埋める』と『ProjectSelectionProblem』 - とこはるのまとめ
この記事は、それに対するフォローの記事です。
- tokoharuさんの記事では、解法と問題名の双方について指摘されてると思いますが、この記事ではスライドの解法についての意見だけ書きます。（問題名については、twitterで別に考えを書きます。）
- スライドに載っているのは、私の解法や解釈で、元の『燃やす埋める』の記事に載っていた解法とは違うので、ご注意ください。そちらに押しかけないように。
- 「全部一緒でしょ」と思う人は、おそらく理解している人だと思うので、この記事を読む必要はないと思います。
解法について
解法の種類
主に以下の[A][B][C]のような解法があります。
[A] スライドの解法
- カットする辺が選択に対応します。小問題を並列に、選択肢を直列に並べます。
- 最小カットになる辺の容量の合計が総コストになります。
スライドP14
[B] プログラミングコンテストチャレンジブックの解法
- カット後の頂点が、s側に属するか、t側に属するかで、選択を決めるという考え方です。
- 最小カットになる辺の容量の合計が総コストになるのは[A]と同じです。
[C] Project Selection Problemのよく知られた解法
- tokoharuさんの記事の説明通りです。
- 講義スライド http://www.cs.princeton.edu/~wayne/kleinberg-tardos/pdf/07NetworkFlowII.pdf のProject Selectionの引用です。
- 基本は、2N+2個の頂点を持ち、中央の部分で、必要条件の依存関係のグラフ（prerequisite graph）をつくるかんじです。
- 本：https://books.google.com.sg/books/about/Algorithm_Design.html?id=GORecgAACAAJ&redir_esc=y
- 元の論文：Jean-Claude Picard (1976) MAXIMAL CLOSURE OF A GRAPH AND APPLICATIONS TO COMBINATORIAL PROBLEMS
[A][B]の本質はほぼ一緒ですが、分かりやすさについては、若干[A]が上回ると判断し、また[A]で対象の問題が全て解けたので、スライドでは[A]で統一しました。（当時、[C]は名前は知っていたのですが、誤解してました…。）
解法[A]のメリットとデメリット
[A]には以下のようなメリット・デメリットがあると思います。
【メリット1】定式化された最小カット問題と、直接結びつく。
最小カット問題を定式化すると以下のようになります。（Max-flow min-cut theorem - Wikipedia から引用です）
辺をカットする・しないを選択肢に対応させると、
のカットする辺が、「選択する」
のカットしない辺が、「選択しない」
- 辺容量
は、選択した場合にかかるコスト
- 目的関数は
、かかるコストの総和、これを最小化する選択肢の組み合わせを探すということです。
- 制約条件は、カットの条件で、小問題ごとに選択肢を１つ選ばなければならないのに対応しています。
最小カット問題とグラフが、特に変形などもせず、直接結びついています。これは以下のメリットにも、つながります。
【メリット2】選択肢の入れ替えをして良いというのが、分かりやすい。
選択肢の入れ替えは、制約条件が追加するにあたって、重要テクニックになってきます。スライドのP34～の内容です。その際、[B]のような解釈をすると、そもそも小問題ごとに選択肢を自由に入れ替えていいのか？という点で、少し迷うと思います（実際は可能です）。
[A]の解釈であれば、（制約条件の辺を追加する前であれば）選択肢の順番が、最小カットに影響を与えないのは明らかです（どちらのケースでも、コストの最小値は20+30=50です）。
【メリット3】3択以上でも適応可能というのが、分かりやすい。
[B][C]の解釈ですと、s側とt側の2つなので、3択には適応できないのでは？と、少し迷うと思います（実際は可能です）。
[A]の解釈であれば、3択以上に拡張しても問題ないというは、明らかです。（実際には、3択の場合、制約条件の追加が限定されて難しいのですが、それは、おそらく[A][B][C]どれも一緒だと思われます。）
【デメリット】負辺の処理で間違える可能性が残る
tokoharuさんの指摘にあった、解法[A][B]のデメリット、負辺で間違う可能性がある（解法[C]では負辺がでてこない）ので間違えないということでした。それは正しいのですが、ただ、このスライドを読んだ人で、このP21が理解できず引っかかる人はあまりいないような気がします、自分はデメリットは些細だと思っています。
また、[C]でも制約条件で負辺にあたるものが出てきた場合、どちらにしてもこの部分は理解してないといけない気がします。
評価
自分の考えでは、
- 慣れた人にとっては、これらのメリットもデメリットも些細。
- 慣れてない人にとっては、[A]がわかりやすい。
という印象です。
また、[A]と[C]は、「メモ化再帰」と「動的計画法」の関係みたいに、問題により若干有利不利はでてきますが、だいたいどちらでも解けるというかんじだと思います。複数の解釈を知っていたほうが、理解が深まることがあります。
さらに、[A]は、最小カットの式に素直に対応していて、一部にしか適応できない変なテクニックというかんじでもありません。
もちろん、[C]の解法は、もっと広まっていいと思うので、自分のスライドで出てきた問題をすべて[C]で解いてみる記事や、[A]と[C]で同じ問題を解いて比較する記事があればいいなぁと思っています。
おわりに
・念のためですが、この解法で解けるのは、最小カットの一部の問題のみです。一般性がすごくある解法と誤解せぬように。他の最小カットの問題も分類した記事があるとうれしいです。
・スライドは、自分の実力よりもだいぶ背伸びした内容になってます（この問題より、ずっと簡単な問題でも、解けてません…）。でも、気にせず記事を書きましょう。
→ぜひ、アドベントカレンダーへ（2枠目が過疎…）
adventar.org
2017/11/26 追記（特にためになったご意見です）
解法[B]のメリット（解法[A]のデメリット）
yosupotさん
ARCに最小カットを出したら最小カットが結構話題になったっぽいんですが、最小カット問題を「辺を選ぶ」問題、つまり辺をいくつか選んでS, T間のパスを消す問題、と認識してしまうと、かなり(プロコンにおいては)損だと思います
— W521 (@yosupot) 2017年11月14日
基本的に「グラフを非連結にするように選ぶ」っていうのはかなり難しい条件だと思っていて，燃やす埋めるのように条件が複雑に絡み合っていくと，「頂点に値を割り振り+罰金」形式の方が考えやすいと思うんです(もちろん燃やす埋める，Project selectionのようにフレームワークを
— W521 (@yosupot) 2017年11月15日
tmaeharaさん
具体的な問題に対してどちらが考えやすいか、という話なら問題依存（∴両方できるべし）になりそうです。理論屋は (1) 頂点変数に取ると任意の部分集合が実行可能になる、(2) 頂点変数のほうが関数の性質が良い（枝から頂点を定められる条件が複雑）、という理由で頂点変数にとることが多いです。
— Takanori MAEHARA (@tmaehara) 2017年11月15日
これらの問題では差がない。
southerwolfieさん
A or Bでなんかコストがついている最小カットは全部同じものと認識していて、そうでない最小カットの問題は時々面白い問題がある
— AGCは天才以外お断りパズルコンテスト (@southerwolfie) 2017年11月14日
最小カットはDiv1Hardを漁っていると時々妙なグラフを作る問題があるのが面白いです。s-[N頂点]-tとかs-[N頂点]-[N頂点]-tみたいなのしか作れないと後々苦労するので変なのに出会うといいと思います
— AGCは天才以外お断りパズルコンテスト (@southerwolfie) 2017年11月14日
TCO17 Marathon Round 1 (GraphDrawing) の反省
問題と1位の方（chokudaiさん）の解法
結果
- 力学モデル（バネ）で、長さ比に応じて力を加える。その後、貪欲法（一番悪い辺の点を、最も高得点になる場所へ移動）で解を改善。
- 45位/146位 652,515.28点。30位ぐらいの人ともかなりの点差が開いていて、敗北感ある…。
敗北までの流れ
ファーストインプレッション
- 方針
- 力学モデル
- 焼きなまし
- よさげな頂点同士をマージしながら構築
- 問題の穴
- 木の足の部分はどうでもよい。
- 距離が近くになる点どうしは、まとめて動かしてもいいかも。
- 三角形などサイクルの形で、辺が絶対につながらず満点が取れないケースもあるので、こういうケースでは理論上最高得点を求めて、最高得点にあわせて、目標長さの条件も緩めたほうがいいのでは。
- MAX_RATIO / MIN_RATIOなのに注意。全部言われた長さにせよとは言ってない。全部スケールしても得点は変わらない？
- 三角形って何個あるんでしょう。位置関係が確定する気がする。
- 長さが整数値になることを使ったHackはなさそう。
ざっくり焼きなまし
- 近傍
- ランダム移動、だんだん移動量を少なく
- 評価値
- 最小値だと、差分を使いづらく、雑に書くとO(E)、良くてO(logE)ぐらいな気がしたので、とりあえず重み付きの和で対応
Submission 2 得点 248563.14
上位の得点が、70万点近くなので、恐らくハズレ方針だと思い、あきらめる。
力学モデル（バネ）
メモ
- 微分せよ。
- ズレ0のやつで、位置があうか比較する。
- インラインアセンブラがききやすい
- 論文（良い初期位置とか）
- Logをつけてみては？
- 引っ張る力を比ベース
- たぶんランダムな力とかは筋がわるそう。
試したこと
- 普通のバネで引っ張る
- バネモデル、意外とバネ定数により、発散しやすい。
- 枠外でも力を加えて、枠に入れたほうが高得点になる。
- 今回は目標の長さとの比が得点にかかわるので、長さ比に比例した力を加える（普通のバネは差に比例した力を加えるので、）
- バネの力により簡単に発散するので、バネ定数の調整と、pow()をつけた調整を試す。
- powやlogを付けた調整は発散しやすかった。
- 距離の短い辺が、強い力でずっと動き続けて足をひっぱる。
- 序盤は遊びを入れて、自由に動けるようにする。目標得点を0からスタートし、目標票得点内に収まるのであれば力は加えない。そして徐々に目標得点を増やしていく（拘束も強まる）
- →これは極値にハマる可能性を大幅に減らせる有力な方針だと思ったけど、そうでもなかった。結局同じような場所でハマる。
- エネルギー最小化
- https://cs.brown.edu/~rt/gdhandbook/chapters/force-directed.pdf のKamada and Kawaiのアルゴリズム。
- バネエネルギーは積分すればいいので、
差ベース
// energy = integrate k*(x-a) dx from x=a to b ====> k * (a-b)^2 / 2比ベース
// energy = integrate k*(x/a-1) dx from x=a to b ====> k * (a-b)^2 / (2*a)
// energy = integrate k*(a/x-1) dx from x=b to a ====> k * (a * log(a/b) + (b-a) )
-
- 本当だったら、高速化のためKamada and Kawai多変数のニュートン法で = 0系の連立方程式を解くのだけど、まずは遅くてもいいので、エネルギー最小になる点を全探索で試すことにした。バネより結果が悪いのであきらめる。
- このタイミングでビジュアライザも作成。正しくは動いているっぽい。
- ズレなしで満点を取れるテストケースを試す
- それでも満点がとれない。
- どうやら初期位置が悪いと簡単なケースでは、ダメなことが分かる。
- 逆にチートして、初期位置を知っているものとしてやると、バネでも高得点が取れる。
- 簡単なわりには低得点になるケースを探す
- 変な三角形とか、田んぼの田とか、いろいろと手作業でいろいろと作るも見つからず。
Submission 3 得点 475556.16
恐らくバネ方針も良くないのだと思い、あきらめる。
強引な貪欲法
もう一番得点が低い辺の頂点の片方を、700*700の移動先を全部試して一番良いところに移動させる。というか、なぜこれを最初に試さない。
- 高速化する。得点ハイトマップを作成して、関数形を見る限り、そんなに山の数が多いかんじではないので、焼きなましで探していいのでは？（ドーナツを重ねてくり）
-
- 250回ぐらいの焼きなましループで、最適解（=700*700）を90%ぐらいの正解率
- 得点は伸びたが、上位の70万点には程遠い。
- 貪欲→バネ→貪欲→バネを繰り返せば、極大値にハマらないのではないか？
- ハマる
Submission 4 得点 606403.67
焼きなまし
貪欲でいいのなら、焼きなましもやっぱり行けるでしょうと思い、焼きなましの戻る
メモ
評価値
- 最小値（問題のスコアと一緒）
- 足し算
- 重み付き足し算（ペナルティはV倍とかにしないとダメ）
- 分散
近傍
- 頂点どうしの位置交換
- 悪い頂点のとなり
- 辺対称
- 大ランダム移動（たぶん大きい移動が入った時点で負け）・小近傍移動
- 速度つき近傍（慣性）
- 粗いグリッド⇒細かいグリッド
実際にやったこと
評価値
- 最小値
- 足し算
- 重み付き足し算（に比が1から離れていれば離れるほど、さらに悪くなる）
- 分散
- O(1)で計算できるし、２番目に悪い点、３番目に悪い点も実質考慮できるので、よいかなと思ったけど、だめだった。
近傍
- 粗いグリッドに分けて、ざっくりした位置を決めたのち、徐々に細かいグリッドにしていく。2*2→4*4→8*8→…
- 32*32を最高にスコアが落ち始めるので、あきらめる。←これはもったいなかった。32以降は別方針にするとか、2段階の解法で高得点いけた
Submission 2と同レベルの得点しかとれないので、やめる。
Beam search系
迷走する。書くほどでもないか…
反省点
部分最適（極値にハマる）理由を考察するのを第一に考える。
シンプルで統一的な解法にこだわりがち。
- シンプルで統一的な解法でないと高得点が取れないと、その後複雑な解法にした際も、最終的には点が伸ばせないと考える癖がある気がする。
- それ自体はいいのだけど、どうもシンプルな解法をいろいろ試すものの、それぞれの解法への考察が雑になり、点が伸ばせる解法を、謝って枝刈りしてしまっている気がする。
- 悪いところを考察したうえであれば、例外的な対処も入れて良い。部分的対応をどんどん入れていってよい。
- 力学解法でも、焼きなましでも、高得点は取れてたっぽい。
- 悪そうな解法でも、部分的にでも良いところを探すようにする。
- ちゃんとした物理に従う必要はないですよ。
- バネモデルで、たまにワープさせたって構わない
- バネモデルで、全部のやつに同時に力を加えなくたって構わない。（一番悪いやつだけとか）
評価関数を状況に応じて変える
（分かってるつもりなのですが…）
- 例えば、焼きなましのグリッド解法は、高得点を取ってる人はいるので、良い方針だったはずなのだけど、2*2のときも、700*700のときも、似たような評価関数を使っているのは、大変良くない。
- そもそも、段階ごとの目的に意識がいってない気がする。粗いグリッドのときは、「正しいセルに振り分ける」のが目的、細かいグリッドのときは「高得点取れるようにする」なのに、評価関数が1つというのは良くない。それぞれの段階での目的をはっきりさせて、評価関数をつくろう。
- これは焼きなましに限らない。Beam Searchの前半と後半で評価値を変えたりもするし、目的ベースで、柔軟にかえる
頭の悪さは、ビジュアライザとランダムテストで補おう
- 極値にハマる、単純なケースを、自分でテストケースを作るものの、見つけられなかった。
- ランダムで単純なテストケースを大量に作って、試せばいいだけ
- せっかくビジュアライザもあるんだから、考察も簡単にできるのだし
スコアに大きな影響を与えるものを、必ずしもアルゴリズムの最初に確定する必要はない。
- 今回は短い辺が、低得点の原因になるけど、その場所を先に確定させると高得点にはならない。
- 短い辺は確かにボトルネックになるけど、アルゴリズムの後半でGreedyとかやれば必ず治せる。
- 似たようなテクニックとして、「後で決めても辻褄が合っていればよい。(Peg Jumpingとか)」というのもある。
このブログは、マラソン開催中に非公開で書くべし
- 絶対にマラソン中に書いたほうが効率がよい。
- 他の人の解答をまだあまり検討していない⇒復習としては最悪！
ビームスタックサーチについての勉強メモ
マラソンマッチ界隈でよく知られている通称chokudaiサーチ、それと似ていると言われてるビームスタックサーチ(beam-stack search)について、ちょっと調べてみました。論文はこちらです。
R Zhou, EA Hansen (2005) Beam-Stack Search: Integrating Backtracking with Beam Search, 15th International Conference on Automated Planning and Scheduling
でも、いまだ分からないところも多いので、まとめました。誤解してそうなので、間違いを指摘してもらえると助かります！論文と照らし合わせながら読んでもらえると良いと思います。
この記事を読むのには以下の知識が必要です。
- ビームサーチ
- 全探索（深さ優先探索など）
- A*アルゴリズム等で出てくる、ヒューリスティック関数の意味
ビームスタックサーチの概要
前提
- 許容的なヒューリスティック関数、つまり、最小値を求めるときは、現在の状態～未来で取りうるコストの下限が必要。最大値を求めるときは上限。（Admissible heuristics)
- 最適解を求めるのが目的。枝刈りは行われるが、基本は全部のパスを通ろうとするので、最適解があれば、必ず見つけられる。(Completeness)
特殊なケース
- ビーム幅が十分に大きいときは、分枝限定法-幅優先探索と同じ。バックトラッキングは行われない。
- ビーム幅が1のときは、分枝限定法-深さ優先探索と同じ。（ちなみに、ビームサーチだと、ビーム幅1は貪欲法と同じ。）
疑似コード
上記の論文に載っているビームスタックサーチの疑似コードの引用である。24～28行目の変数relayの部分は、拡張バージョンdivide and conquer beam-stack searchの部分なので、今回は無視する。
ビームスタックサーチの流れ
ビーム幅2で、ビームスタックサーチを使って、最小値を求める場合を考える。（注意：まだ不明な点があるので、グラフをわざと簡単な木にしてます）
各ノードnを状態とし、それぞれのノード内の数字は評価値を表す（f-costと呼ぶ。ノード番号では無い！）。評価関数f(n) は
f(n) = g(n) + h(n)
- g(n)は、スタートノードからノードnまでのコスト
- h(n)は、許容的なヒューリスティック関数、ノードnからゴールノードまでのコストの下限（絶対に過大評価しない値）
スタートノード（f-costが0）から、最小値を求めていく。
Layerごとに、
- f-costでソートする。
- fmin・fmaxという範囲を示すペアの値を持つ。初期値は fmin=0, fmax=U。(Uは現在までの最適解。Uの初期値は+∞で良い)。
fmin・fmaxのペアをレイヤーの小さい順からスタックにpushしていったものを、ビームスタック(beam stack)と呼ぶ。
スタートノードから、ビームサーチをしていく（8行目）。注意点は、f-costが[fmin,fmax)に入るノードだけを探索するところ21行目?。ビーム幅が2なので、上位2つ（低いコスト）しか入れない。ビーム幅から漏れたノードの評価値が新たにfmaxとなる（3行目）。つまり範囲が狭まる。
ゴールノードにたどりついたので、最小値を更新し、U=6となる。もし、fmax>Uとなった場合は、そのLayerはEmpty Layerとなる。Empty Layerが、ビームスタックのtopに来たら除去される。つまり深いLayerから探索から外れていく（46～48行目）。
（ここが全く分かってない可能性あり！）最深層までたどり着いたら、最深層のfminとfmaxが更新される。fminが今までのfmax、fmaxがUになる（50～51行目）。
ここはfmaxはそのまま。評価値5のノードは辿っておらず、ビーム幅2からあぶれたわけではない。
深さ優先探索順に新しい訪問先を辿っていく
別のゴールノードにたどり着いたので、最小値を更新し、U=5となる。常に後で見つかった解のほうが、良い最適解になるのに注意する(44～45行目)。これでビームスタックが空になったので、終了（49行目）。
私見と疑問点
アルゴリズムの観点から
- 疑似コードで、どうやってバックトラッキング（深さ優先探索）を実行しているのか？
- 普通は深さ優先探索をするには、再帰にするか、stackにpush・popをするか、どちらかだけど、8～37行目を見る限り、popはしていないし、再帰呼び出しもない。
- 関数searchは毎回スタートから行われているので、新たに訪問するノードの順が、深さ優先探索順になるだけかもしれない。
- ただ、そうだとすると、毎回スタートから同じノードを何度もたどり、計算量がひどいことになりそうな…。
- 以下の例は大丈夫なのか？f-cost3のノードを訪問する前に、f-cost4と5のノードを訪問するので、fmaxが6になり(3行目)、その後すぐfminが6になるので、f-cost3のノードを訪れずに終わってしまいそう。
- wikipediaでビームサーチを見たら、そこでもヒューリスティック関数の例がでていたし、先行する論文のいくつかもそうだった。もしかして、それが普通？
- ビームスタックサーチを分枝限定法（branch and bound）と呼ぶのは大げさな感じが…。ただの枝刈りでは…。でも、英語版wikipedia見ると、ヒューリスティック関数で枝刈りするだけでも、そう呼べるみたい。
マラソンマッチの観点から
- 許容的なヒューリスティック関数が必要だとすると、使用箇所は限定されそう。
- 最短距離のようにコストが増えていくだけなら、許容的なヒューリスティック関数を常に0とみなしても、よさげですが。自由に値をとりうる評価関数だと、枝刈りが行われず、ビームスタックサーチは、ただの探索になってしまいます。
- マラソンマッチの探索上手な人だと、そもそも、幅優先だか深さ優先だか最良優先だかあまり区別のつかないような、自由な探索を書く人も多く、まさにビームスタックサーチは、その中に含まれそう。
- ビームスタックサーチとほぼ同じと言われてたchokudaiサーチとは、アルゴリズムも目的も全然違うっぽい。
Kaggle体験記（TopCoder機械学習マラソンとの違いなど）
tanzakuさん、今年もありがとうございます！ Competitive Programming （その2） Advent Calendar 2016 - Adventarの25日目！
はじめに
Kaggle（https://www.kaggle.com/）も、TopCoder機械学習マラソン（TopCoder）も、広義の競技プログラミング！ ということで、今回Kaggleに軽めに参加してみました。これらの違いについて取りあげようと思います。機械学習そのものについては取り上げてません。あしからず。
Kaggleの特徴（TopCoderと異なる点）
予測データのみを提出すれば良い。
- TopCoderは、マッチにより、予測する実行コードを提出する形式か、予測したデータを提出する形式か違ってきますが、Kaggleは、ほぼ予測データのみ提出です（例外はある）。そういうわけで、ライブラリや計算資源を好きなだけ使えます。
参加しやすい
- ページのレイアウトが分かりやすく、いたれりつくせりで、TopCoderのように管理がされなくなったりということもなさげで（過去問が動かないとか）、全体的に、ちゃんとしてます。
- とりあえず提出できるサンプルデータも用意されてるので、最初の１歩は踏み出しやすいです。
- 運営の方から、「新たな検索機能を追加したので、感想をきかせてね」といった連絡がリアルタイムで送られてきて、驚きました。積極的に改善しようという姿勢がうかがえます。
マッチの開催中でも、フォーラム内でなら、解法を議論してよい。
- 解法そのものについて直接言及しているのもあります（こうすると、何点までは行けるとか）
- データのビジュアライズなど、面倒そうなことをやってくれてる親切な人もいます。
- ただ、上位の人は、下位の人向けへのヒントをとどめて、本当に上位にいけそうなアイディアを公開するのは控えているようです。
マッチの開催中でも、コードを公開することができる。
- 後から始めたほうが情報が入る分有利で、公平でないとか、そういう議論もあるようです。
- そんな人はTopCoder。TopCoderは議論禁止・コード公開禁止、また、コード提出の場合は計算資源も全員いっしょなので、そういう意味で公平な競争がしたい人にはおすすめ。
- ただ、TopCoderのようにコード提出形式のもはじまったようです。
- 上位の情報は書いてないので、上位の人たちは、別にこのままのルールでも、公平な競争ができてると感じているかも。でも、中位以下の人のモチベーションがどうなるか気になります。
- そんな人はTopCoder。TopCoderは議論禁止・コード公開禁止、また、コード提出の場合は計算資源も全員いっしょなので、そういう意味で公平な競争がしたい人にはおすすめ。
書いたコードを、Kaggleのブラウザ上で実行できる。
- TopCoderでもできなくはないけど、ファイルも取り扱えたり。folkもできたり、高機能。多くのライブラリも使えます。Dockerのおかげ？
- 計算資源がしょぼいのを除けば、ブラウザ上だけでなんでもできそう。すごい。
最終提出データを2種類選択できる。
- TopCoderだと1番最後に提出した1つになるので、万が一間違ったものを提出したことを考えると、時間ギリギリで提出するのは無謀。
- 1つは過学習したやつ、1つはクロスバリデーションしっかりやった無難なやつといった、作戦もありそうです。
参加者のレベル
- 語れる立場にありません（泣）。マシな結果を出してからにします。ただ、最近はTopCoder→Kaggleへ参戦して結果を出しているトップクラスの方や（colunさん・Komakiさん・marek.cyganさん・iwiさんなど）、またKaggleからTopCoderへ参戦してる方もいます（fugusukiさんなど）ので、強い人はどこでも強いということだけは言えるでしょう。
Kaggle体験記じゃ
今回、参加したのはこれ。
www.kaggle.com
作業過程20時間をすべて録画していたので、時刻つきで、見直してみました。流れは分かるかと。
- (00:00:00) なんでもいいので、最低限の解答を提出しよう。自分は大風呂敷を広げて暴走する悪癖があるので、まず簡単な解をめざす！
- (00:31:54) Kernelsってところで、他の人のコードが見れて、ショック！folkって書いてあるってことは、これを使っていいのか？同じぐらいの得点の人もたくさんいるし、ぱくってそう…。
- (00:43:49) そのまま実行できるの？どれぐらい時間かかるんだろう…。
- (00:52:37) 提出できるし、Dockerすごい。まぁ、パクってるけど、最低限の解答ということにする。
- (02:36:56) 罪悪感をかんじてきたので、せめて自分で実行する。Linuxのほうがインストールが簡単そうだけど、家にLinuxがないので、Amazon Web Service(AWS) EC2で、無料のUbuntuインスタンスを借りてみる。
- スクリプトで使われてるパッケージ（NumPy, scipy, pandas, scikit-learn）を、全部インストールしたつもりなのに、動かず、ハマる。python 2で動くのか疑心暗鬼に。原因は、間違ってpython等を古いバージョンに戻したため、バージョンの整合性のせいで動かず、一からインストールしなおしたら、治った。 python 2で普通に全部動く。（2016年12月時点の話ですが、xgboostのインストールで、赤字の部分は古い情報も見かけるので注意。）
#xgboost
git clone --recursive https://github.com/dmlc/xgboost.git
cd xgboost; make; cd python-package; sudo python setup.py install; cd ~
- でも、やっぱり別のエラーがでる…。スクリプトの文字コードにスペイン語が入ってるのにも関わらず、秀丸はSHIFT-JISと誤認識して、文字化けしてた。おーい…。絶対UTFで。
- (08:30:59) 今度はMemoryエラー。単に無料インスタンスではメモリ不足のよう。有料で1番安いインスタンスを借りなおし、インストール用のbashスクリプトをちゃんと整備。
- (10:37:38) 動くようになる。ただし、単に自分でスクリプトを実行しただけでなので、スコアは同じ。この時点で、527位/1700ぐらい。
- (11:30:22) スクリプトの中身とxgboostのパラメータなどを理解しようとする。
- (12:30:57) データセット・スコアの理解につとめる
- (13:27:10) フォーラムをみる。 Lagと呼ばれる特徴量を追加すると0.03点いけるらしいのでやってみる。*1
- (16:04:55) 簡易版のLagを入れてみると、実際0.03にかなり近い得点にいけた！てきと～なことこの上ないけど、上位10%まであと少し。ただ、終了まで3時間しかない…。
- ちゃんとLagを入れてみるが、点が下がる。実装ミスかもしれないけど、AWS上だとIDEはさすがに使えないので、デバッグしづらい…
- 5分程度しか計算してないので、短すぎかも？
- (18:09:16)もう高いEC2インスタンスC4.8XLarge借りちゃえ。1時間$3ぐらいだし、もう1時間30分しかないので、問題ないでしょう。
- うわー、それでも結果伸びない。他人のを借りてきただけど、いろいろちゃんとセットアップしないので、結局損。xgboostしか使ってないのは、そこまで大問題ではないと思うけど、特徴量選択の自動化・ハイパーパラメータ調整・クロスバリデーションも何もやってない。眠い。天啓による調整に頼る（ダメ）。
- 最後、結構時間ギリギリ（打ち切れるように改良してないのもだめだし、そもそもギリギリまでやってるのがダメ）
- なんとか間に合って
- (19:38:59) あぁぁぁぁ、あせって間違ってデータではなく、pythonスクリプトを提出してることに気づく。つい、TopCoderの癖が…。バカすぎる…。
- マッチ終了
- (19:42:19) Post Deadlineと表示される。提出遅れには厳粛に対応、しかし、遅れた結果はしっかり見せる、優しいのか鬼なのか分からないけど、ちゃんとしてる仕様。
- 最終結果は、215位/1784(上位13%)でした。TopCoderのように、レート下がるってことはなさげなので、下位に沈んだら放棄する人も多いのかも。
- 徹夜したので、次の日は即寝落ち。
- 2日後、高額なインスタンスにつなげっぱなしだったのに気づく！
- 結果
- …わしはバカすぎじゃ。
Kaggle体験記まとめ
- 普段からLinuxを使っている人や、AWS EC2やS3を使っている人であれば、もっとすんなり行くと思います。
- 今回は全部AWS EC2上のUbuntu上で行いましたが、自分のPCにも開発環境を用意したほうがいいと思います。IDEが使えないのが痛い…。
- Kaggleの流れを知りたいのであれば、最初の1回は今回のように他の人のスクリプトを足がかりにスタートするのは悪くないと思います。
- ただ、成功例をたどるだけでは、勉強にはならなそう（短時間のわりに良いスコアは得られるかもしれませんが）。試行錯誤したり、アルゴリズムを導入・改良したり、自動化など環境をより便利にしたりってところは、自分でやったほうが、長期的にみると、スコア的にも勉強の観点からも得だと思います。
- Forumでの解法の事後公開やディスカッションもとても盛んなので、読みましょう。そのあとの復習が大事。
- 日本人のKaggle参加者の参戦記もたくさん落ちているので、ぜひ読みましょう。
おわりに
来年こそはKaggleもがんばりたい…といいたいところですが、本職が大変になりそうなので、ぜひ、これをみた皆さんは、わしの分まで、Kaggleをやるのじゃぞ！
*1:（同じお客様IDの過去5年間のデータを探し、それも特徴量に加えるという方法です。過去の記事 ランダムフォレストのつかいかた - じじいのプログラミング -> 同種の説明変数を追加する。 -> （1）同種のデータとのかかわりを表す変数を追加する ぽいやつ）
競技プログラミングの2015年の結果、2016年の目標
2015年の結果
| SRMに56.6%以上参加 | 20点 | 達成 |
| SRMに56.6%以上参加したうえでRating1800以上 | 20点 | 失敗 |
| TCO15 SRM Round 3 | 20点 | 失敗 |
| マラソンマッチ レッドコーダー | 80点 | 失敗 |
| TCO15 マラソン予選10位以内 1回ごとに | 20点 | 失敗 |
| TCO15 マラソンワールドファイナル出場 | 300点 | 失敗 |
| Google Code Jam Round 3 | 10点 | 失敗 |
| プロコンTシャツゲット1枚ごとに | 5点 | 2枚 |
| プロコン賞金10万円ごとに | 10点 | 失敗 |
| プロコンでオンサイト決勝出場 | 50点 | 失敗 |
| ニコ生放送200枠分（=100時間） | 10点 | 失敗 |
| 海外でプロコンオフ会をやる | 10点 | 達成 |
| Codeforcesで栗原市ランキングいり | 10点 | 失敗 |
2015年の結果 40点でした…。(なお、2014年は60点でした)
2015年の反省
| マラソンマッチ レッドコーダー | 80点 | 失敗 |
| TCO15 マラソン予選10位以内 1回ごとに | 20点 | 失敗 |
| TCO15 マラソンワールドファイナル出場 | 300点 | 失敗 |
まずは、ここらへん。TCO15 Marathon Match Round 1の最終提出が間に合わず（もちろん自分が悪い）、レーティング激減して、気持ちが切れてしまった感じがあります…。あと、そもそも時間が作れなかったというのもありました（特に2015年上半期）。
また、自分の場合は、安定した結果を出すために、マッチに参加するよりも、突っ込んだ復習が大事な気がしているのですが、復習のモチベ維持もできていなかった気がします。
2016年はもっと時間がなさそうで、未来は暗い気がしますが、参加するマラソンマッチを絞って、出たやつについては丁寧にやっていこうと思います。
| プロコン賞金10万円ごとに | 10点 | 失敗 |
主に機械学習マッチでチャンスがあると思っていたのですが、そもそもあまり参加ができませんでした。少なくとも解答がでた場合は、結果が悪くても提出するようにはしているのですが、解答まで至らなかったマッチが２つありました…（地震と前立腺がん）。こっちは短時間で準備するノウハウはつかんできた気がするので、今後、通常マラソンよりは結果が出せそうな気はします。
| SRMに56.6%以上参加したうえでRating1800以上 | 20点 | 失敗 |
2015年は初めて一時的にRating 1800を越え、最終戦まで1800を越えるチャンスはあったのですが、逃してしまいました。Mediumが解けないのはしょうがないにしても、Easyで落とすケースが目立ちました。というか、Easyが昔ほど簡単ではありません。
まずEasyの出てない回の問題もたまってきたので、Easy問題を練習で解いてEasy安定に努めたいと思います。これなら、時間はそんなにかからないはず。
| Google Code Jam Round 3 | 10点 | 失敗 |
大会では、もうちょっとうまくやれた気がします。Code Jam Round 3は決して不可能ではない目標なのですが、ピンチになって難しい問題を解かないとダメな状況になるとほぼ失敗するので、ピンチになってもあせらずに簡単な問題を確実に解いていくようにしたいです。
| ニコ生放送200枠分（=100時間） | 10点 | 失敗 |
結果、放送したのは120枠分（＝60時間）程度でした。現状だと100時間はかなり難しいですが、できる範囲で継続してやっていきます。
| 海外でプロコンオフ会をやる | 10点 | 達成 |
シンガポールでオフ会をするのは予想以上に大変でした…。「人を集める方法」「人に連絡する方法」「場所探し」「参加費」「何をすればいいのか」、すべてが難しかったです。かなりの時間を使った気がしますが、達成できてよかったです。ただ、これをやらなければ、他に時間をつかえた気もします。
あと、数少ない良かった点としては、「目標を常に覚えていた」ことでしょう。目標がなければ、もっと無為に過ごしていたと思われるので、それよりはマシ。2016年も目標を忘れない！
2016年の得点表と目標
正直なところ、2016年は2015年より忙しくなる要素しかないので、目標は2014年の水準、60点以上にします。あと、Codeforces, Facebook Hacker Cup, Kaggleとバリエーションを増やしました。（これらを増やしても2015年は40点です。）
| SRMに50%以上参加 | 20点 |
| SRMに50%以上参加したうえでRating1800以上 | 20点 |
| TCO16 SRM Round 3 | 20点 |
| マラソンマッチ レッドコーダー | 80点 |
| マラソンマッチ Rating 2000以上 | 40点 |
| マラソンマッチ Rating 1800以上 | 20点 |
| TCO16 マラソン予選10位以内 1回ごとに | 30点 |
| TCO16 マラソンワールドファイナル出場 | 300点 |
| Codeforces Highest Rating 2200以上（薄い橙） | 50点 |
| Codeforces Highest Rating 1900以上（紫） | 10点 |
| Google Code Jam Round 3 | 10点 |
| Facebook Hacker Cup Round 2 | 5点 |
| Facebook Hacker Cup Round 3 | 20点 |
| プロコンTシャツゲット1枚ごとに | 5点 |
| プロコン賞金10万円ごとに | 10点 |
| プロコンでオンサイト決勝出場 | 50点 |
| Kaggle 上位25% | 5点 |
| Kaggle 上位10% | 10点 |
| ニコ生放送200枠分（=100時間） | 10点 |
| 海外でプロコンオフ会をやる | 10点 |
| Codeforcesで栗原市ランキングいり | 10点 |
なお、得点表は、難度だけではなく、自分がやりたいかどうかも含めて決めています。
ところで…
ほっほー。
2015年の目標を振り返ってみたところ、40点のところをみたら、
| 30～59 | 怠惰・堕落(FUJIYAMAに乗る) |
と、書いてあったのじゃ。絶対にこんな低い点は取らないと思って、てきとーに書いたのに…。しかも、不幸は重なるもので、甲府に行く用事ができてしまったので、ついでに行ってきたのじゃ…。
頭がおかしいアトラクションだらけですね。わしは死にたくないのじゃ。
でも勇気を振り絞って、以下の乗り物に乗ってきたのじゃ。天にも届くようなスロープに、背後にそびえる富士山が、一層の恐怖をかきたてるのじゃ。変な生き物もいたし、地獄だったのじゃ。さすがFUJIYAMA！
…では、さらばじゃ。ほっほー()
