2017-11-29

Topcoder Arenaを起動する方法とJavaブロックの回避

TopCoder

はじめに

Topcoderで競技プログラミングをする場合、以下の２つの方法があります。

ウェブ版（ベータ）TopCoder Arena
アプリ版 Competition Arena

ウェブ版はずっとベータ版で開発終了停止している模様なので、懐かしのアプリ版を立ち上げたいところ（パスワード平文疑惑がありますが…）。でも、昔参加していた人が戻ってきても、ホームページが大改造されていて、はまりやすいのでメモ。Topcoderの登録は無事できているものとします。

アプレットArenaをダウンロードする

直接リンク Competition Arena

ちなみに、本家ページは以下の場所から行けます。一番目につくCOMPETE→COMPETITIVE PROGRAMMINGと行ってしまうと、ウェブ版（ベータ）が立ち上がるので注意
f:id:shindannin:20171129101957p:plain

アプレットArenaをダウンロードする

そのままですと、「セキュリティ設定によってブロックされたアプリケーション」というエラーで、Javaにブロックされて起動できません。以下のように、例外サイトにhttp://www.topcoder.comを追加しましょう。

f:id:shindannin:20171129102230p:plain

f:id:shindannin:20171129102432p:plain

2017-11-15

最小カットを使って「燃やす埋める」問題を解くスライドのフォロー

TopCoder

この記事は競技プログラマー向けです。

はじめに

以前、最小カットを使って「燃やす埋める」問題を解くというスライドを書きました。

最小カットを使って「燃やす埋める問題」を解く from shindannin

www.slideshare.net

これに対して、tokoharuさんから、『燃やす埋める』よりも『Project Selection Problem』を使うべきという、提言がありました。
『燃やす埋める』と『ProjectSelectionProblem』 - とこはるのまとめ
 続：『燃やす埋める』と『ProjectSelectionProblem』 - とこはるのまとめ

この記事は、それに対するフォローの記事です。

tokoharuさんの記事では、解法と問題名の双方について指摘されてると思いますが、この記事ではスライドの解法についての意見だけ書きます。（問題名については、twitterで別に考えを書きます。）
スライドに載っているのは、私の解法や解釈で、元の『燃やす埋める』の記事に載っていた解法とは違うので、ご注意ください。そちらに押しかけないように。
「全部一緒でしょ」と思う人は、おそらく理解している人だと思うので、この記事を読む必要はないと思います。

解法について

解法の種類

主に以下の[A][B][C]のような解法があります。

[A] スライドの解法

カットする辺が選択に対応します。小問題を並列に、選択肢を直列に並べます。
最小カットになる辺の容量の合計が総コストになります。

スライドP14
f:id:shindannin:20171115014923p:plain

[B] プログラミングコンテストチャレンジブックの解法

カット後の頂点が、s側に属するか、t側に属するかで、選択を決めるという考え方です。
最小カットになる辺の容量の合計が総コストになるのは[A]と同じです。

[C] Project Selection Problemのよく知られた解法

tokoharuさんの記事の説明通りです。
講義スライド　http://www.cs.princeton.edu/~wayne/kleinberg-tardos/pdf/07NetworkFlowII.pdf のProject Selectionの引用です。

f:id:shindannin:20171115003256p:plain

基本は、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 から引用です）
f:id:shindannin:20171115015238p:plain
辺 $(u,v)$ をカットする・しないを選択肢に対応させると、

$d_{uv}=1$ のカットする辺が、「選択する」
$d_{uv}=0$ のカットしない辺が、「選択しない」
辺容量 $c_{uv}$ は、選択した場合にかかるコスト
目的関数は $\sum c_{uv}d_{uv}$ 、かかるコストの総和、これを最小化する選択肢の組み合わせを探すということです。
制約条件は、カットの条件で、小問題ごとに選択肢を１つ選ばなければならないのに対応しています。

最小カット問題とグラフが、特に変形などもせず、直接結びついています。これは以下のメリットにも、つながります。

【メリット2】選択肢の入れ替えをして良いというのが、分かりやすい。

選択肢の入れ替えは、制約条件が追加するにあたって、重要テクニックになってきます。スライドのP34～の内容です。その際、[B]のような解釈をすると、そもそも小問題ごとに選択肢を自由に入れ替えていいのか？という点で、少し迷うと思います（実際は可能です）。
f:id:shindannin:20171115024636p:plain

[A]の解釈であれば、（制約条件の辺を追加する前であれば）選択肢の順番が、最小カットに影響を与えないのは明らかです（どちらのケースでも、コストの最小値は20+30=50です）。
f:id:shindannin:20171115025114p:plain

【メリット3】3択以上でも適応可能というのが、分かりやすい。

[B][C]の解釈ですと、s側とt側の2つなので、3択には適応できないのでは？と、少し迷うと思います（実際は可能です）。
[A]の解釈であれば、3択以上に拡張しても問題ないというは、明らかです。（実際には、3択の場合、制約条件の追加が限定されて難しいのですが、それは、おそらく[A][B][C]どれも一緒だと思われます。）
f:id:shindannin:20171115025915p:plain

【デメリット】負辺の処理で間違える可能性が残る

tokoharuさんの指摘にあった、解法[A][B]のデメリット、負辺で間違う可能性がある（解法[C]では負辺がでてこない）ので間違えないということでした。それは正しいのですが、ただ、このスライドを読んだ人で、このP21が理解できず引っかかる人はあまりいないような気がします、自分はデメリットは些細だと思っています。
f:id:shindannin:20171114235119p:plain

また、[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日

2017-05-11

TCO17 Marathon Round 1 (GraphDrawing) の反省

TopCoder マラソンマッチ

問題と1位の方（chokudaiさん）の解法

TCO2017R1

結果

力学モデル（バネ）で、長さ比に応じて力を加える。その後、貪欲法（一番悪い辺の点を、最も高得点になる場所へ移動）で解を改善。
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の移動先を全部試して一番良いところに移動させる。というか、なぜこれを最初に試さない。

高速化する。得点ハイトマップを作成して、関数形を見る限り、そんなに山の数が多いかんじではないので、焼きなましで探していいのでは？（ドーナツを重ねてくり）

f:id:shindannin:20170511103243p:plain

- 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とか)」というのもある。

このブログは、マラソン開催中に非公開で書くべし

絶対にマラソン中に書いたほうが効率がよい。
他の人の解答をまだあまり検討していない⇒復習としては最悪！

2017-05-04

ビームスタックサーチについての勉強メモ

マラソンマッチ TopCoder

マラソンマッチ界隈でよく知られている通称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の部分なので、今回は無視する。
f:id:shindannin:20170504213938p:plain

ビームスタックサーチの流れ

ビーム幅2で、ビームスタックサーチを使って、最小値を求める場合を考える。（注意：まだ不明な点があるので、グラフをわざと簡単な木にしてます）

各ノードnを状態とし、それぞれのノード内の数字は評価値を表す（f-costと呼ぶ。ノード番号では無い！）。評価関数f(n) は
f(n) = g(n) + h(n)

g(n)は、スタートノードからノードnまでのコスト
h(n)は、許容的なヒューリスティック関数、ノードnからゴールノードまでのコストの下限（絶対に過大評価しない値）

スタートノード（f-costが0）から、最小値を求めていく。
f:id:shindannin:20170504092512j:plain

Layerごとに、

f-costでソートする。
fmin・fmaxという範囲を示すペアの値を持つ。初期値は fmin=0, fmax=U。(Uは現在までの最適解。Uの初期値は+∞で良い)。

fmin・fmaxのペアをレイヤーの小さい順からスタックにpushしていったものを、ビームスタック(beam stack)と呼ぶ。
f:id:shindannin:20170504092516j:plain

スタートノードから、ビームサーチをしていく（8行目）。注意点は、f-costが[fmin,fmax)に入るノードだけを探索するところ21行目?。ビーム幅が2なので、上位2つ（低いコスト）しか入れない。ビーム幅から漏れたノードの評価値が新たにfmaxとなる（3行目）。つまり範囲が狭まる。
f:id:shindannin:20170504092519j:plain

ゴールノードにたどりついたので、最小値を更新し、U=6となる。もし、fmax>Uとなった場合は、そのLayerはEmpty Layerとなる。Empty Layerが、ビームスタックのtopに来たら除去される。つまり深いLayerから探索から外れていく（46～48行目）。
f:id:shindannin:20170504092525j:plain

（ここが全く分かってない可能性あり！）最深層までたどり着いたら、最深層のfminとfmaxが更新される。fminが今までのfmax、fmaxがUになる（50～51行目）。
f:id:shindannin:20170504101615j:plain

ここはfmaxはそのまま。評価値5のノードは辿っておらず、ビーム幅2からあぶれたわけではない。
f:id:shindannin:20170504101619j:plain
深さ優先探索順に新しい訪問先を辿っていく
f:id:shindannin:20170504092532j:plain

別のゴールノードにたどり着いたので、最小値を更新し、U=5となる。常に後で見つかった解のほうが、良い最適解になるのに注意する(44～45行目)。これでビームスタックが空になったので、終了（49行目）。
f:id:shindannin:20170504092537j:plain

私見と疑問点

アルゴリズムの観点から

疑似コードで、どうやってバックトラッキング（深さ優先探索）を実行しているのか？
- 普通は深さ優先探索をするには、再帰にするか、stackにpush・popをするか、どちらかだけど、8～37行目を見る限り、popはしていないし、再帰呼び出しもない。
- 関数searchは毎回スタートから行われているので、新たに訪問するノードの順が、深さ優先探索順になるだけかもしれない。
  - ただ、そうだとすると、毎回スタートから同じノードを何度もたどり、計算量がひどいことになりそうな…。
以下の例は大丈夫なのか？f-cost3のノードを訪問する前に、f-cost4と5のノードを訪問するので、fmaxが6になり(3行目)、その後すぐfminが6になるので、f-cost3のノードを訪れずに終わってしまいそう。

f:id:shindannin:20170504224853j:plain

wikipediaでビームサーチを見たら、そこでもヒューリスティック関数の例がでていたし、先行する論文のいくつかもそうだった。もしかして、それが普通？
ビームスタックサーチを分枝限定法（branch and bound）と呼ぶのは大げさな感じが…。ただの枝刈りでは…。でも、英語版wikipedia見ると、ヒューリスティック関数で枝刈りするだけでも、そう呼べるみたい。

マラソンマッチの観点から

許容的なヒューリスティック関数が必要だとすると、使用箇所は限定されそう。
- 最短距離のようにコストが増えていくだけなら、許容的なヒューリスティック関数を常に0とみなしても、よさげですが。自由に値をとりうる評価関数だと、枝刈りが行われず、ビームスタックサーチは、ただの探索になってしまいます。
マラソンマッチの探索上手な人だと、そもそも、幅優先だか深さ優先だか最良優先だかあまり区別のつかないような、自由な探索を書く人も多く、まさにビームスタックサーチは、その中に含まれそう。
ビームスタックサーチとほぼ同じと言われてたchokudaiサーチとは、アルゴリズムも目的も全然違うっぽい。

2016-12-25

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のようにコード提出形式のもはじまったようです。
  - 上位の情報は書いてないので、上位の人たちは、別にこのままのルールでも、公平な競争ができてると感じているかも。でも、中位以下の人のモチベーションがどうなるか気になります。

書いたコードを、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って書いてあるってことは、これを使っていいのか？同じぐらいの得点の人もたくさんいるし、ぱくってそう…。

f:id:shindannin:20161226002752p:plain

(00:43:49) そのまま実行できるの？どれぐらい時間かかるんだろう…。

f:id:shindannin:20161226003012p:plain

(00:52:37) 提出できるし、Dockerすごい。まぁ、パクってるけど、最低限の解答ということにする。

f:id:shindannin:20161226003205p:plain

(02:36:56) 罪悪感をかんじてきたので、せめて自分で実行する。Linuxのほうがインストールが簡単そうだけど、家にLinuxがないので、Amazon Web Service(AWS) EC2で、無料のUbuntuインスタンスを借りてみる。

f:id:shindannin:20161226003920p:plain

スクリプトで使われてるパッケージ（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スクリプトをちゃんと整備。

f:id:shindannin:20161226054019p:plain

(10:37:38) 動くようになる。ただし、単に自分でスクリプトを実行しただけでなので、スコアは同じ。この時点で、527位/1700ぐらい。
(11:30:22) スクリプトの中身とxgboostのパラメータなどを理解しようとする。
(12:30:57) データセット・スコアの理解につとめる
(13:27:10) フォーラムをみる。 Lagと呼ばれる特徴量を追加すると0.03点いけるらしいのでやってみる。*1

f:id:shindannin:20161226063348p:plain

(16:04:55) 簡易版のLagを入れてみると、実際0.03にかなり近い得点にいけた！てきと～なことこの上ないけど、上位10%まであと少し。ただ、終了まで3時間しかない…。

f:id:shindannin:20161226065853p:plain

ちゃんとLagを入れてみるが、点が下がる。実装ミスかもしれないけど、AWS上だとIDEはさすがに使えないので、デバッグしづらい…
5分程度しか計算してないので、短すぎかも？
(18:09:16)もう高いEC2インスタンスC4.8XLarge借りちゃえ。1時間$3ぐらいだし、もう1時間30分しかないので、問題ないでしょう。

f:id:shindannin:20161226071750p:plain

うわー、それでも結果伸びない。他人のを借りてきただけど、いろいろちゃんとセットアップしないので、結局損。xgboostしか使ってないのは、そこまで大問題ではないと思うけど、特徴量選択の自動化・ハイパーパラメータ調整・クロスバリデーションも何もやってない。眠い。天啓による調整に頼る（ダメ）。
最後、結構時間ギリギリ（打ち切れるように改良してないのもだめだし、そもそもギリギリまでやってるのがダメ）
なんとか間に合って
(19:38:59) あぁぁぁぁ、あせって間違ってデータではなく、pythonスクリプトを提出してることに気づく。つい、TopCoderの癖が…。バカすぎる…。

f:id:shindannin:20161226071207p:plain

マッチ終了
(19:42:19) Post Deadlineと表示される。提出遅れには厳粛に対応、しかし、遅れた結果はしっかり見せる、優しいのか鬼なのか分からないけど、ちゃんとしてる仕様。

f:id:shindannin:20161226071050p:plain

最終結果は、215位/1784(上位13%)でした。TopCoderのように、レート下がるってことはなさげなので、下位に沈んだら放棄する人も多いのかも。
徹夜したので、次の日は即寝落ち。

2日後、高額なインスタンスにつなげっぱなしだったのに気づく！
結果

f:id:shindannin:20161226072340p:plain

…わしはバカすぎじゃ。

Kaggle体験記まとめ

普段からLinuxを使っている人や、AWS EC2やS3を使っている人であれば、もっとすんなり行くと思います。
今回は全部AWS EC2上のUbuntu上で行いましたが、自分のPCにも開発環境を用意したほうがいいと思います。IDEが使えないのが痛い…。
Kaggleの流れを知りたいのであれば、最初の1回は今回のように他の人のスクリプトを足がかりにスタートするのは悪くないと思います。
ただ、成功例をたどるだけでは、勉強にはならなそう（短時間のわりに良いスコアは得られるかもしれませんが）。試行錯誤したり、アルゴリズムを導入・改良したり、自動化など環境をより便利にしたりってところは、自分でやったほうが、長期的にみると、スコア的にも勉強の観点からも得だと思います。
Forumでの解法の事後公開やディスカッションもとても盛んなので、読みましょう。そのあとの復習が大事。
日本人のKaggle参加者の参戦記もたくさん落ちているので、ぜひ読みましょう。

おわりに

来年こそはKaggleもがんばりたい…といいたいところですが、本職が大変になりそうなので、ぜひ、これをみた皆さんは、わしの分まで、Kaggleをやるのじゃぞ！

*1:（同じお客様IDの過去5年間のデータを探し、それも特徴量に加えるという方法です。過去の記事　ランダムフォレストのつかいかた - じじいのプログラミング -> 同種の説明変数を追加する。 -> （1）同種のデータとのかかわりを表す変数を追加するぽいやつ）

2016-01-10

競技プログラミングの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に乗る)

と、書いてあったのじゃ。絶対にこんな低い点は取らないと思って、てきとーに書いたのに…。しかも、不幸は重なるもので、甲府に行く用事ができてしまったので、ついでに行ってきたのじゃ…。
f:id:shindannin:20160105160851j:plain

頭がおかしいアトラクションだらけですね。わしは死にたくないのじゃ。
f:id:shindannin:20160105145828j:plain

でも勇気を振り絞って、以下の乗り物に乗ってきたのじゃ。天にも届くようなスロープに、背後にそびえる富士山が、一層の恐怖をかきたてるのじゃ。変な生き物もいたし、地獄だったのじゃ。さすがFUJIYAMA！
f:id:shindannin:20160105152400j:plain

…では、さらばじゃ。ほっほー()

2015-12-23

累積和を使う動的計画法

TopCoder

この記事はCompetitve Programming Advent Calendar 2015の23日目の記事です。tanzakuさんに感謝
www.adventar.org

今回は、累積和を使う動的計画法についてです。TopCoderのDiv2上位ぐらいの人向けの難易度です。

問題

AtCoder Typical DP Conestの問題です。
F: 準急 - Typical DP Contest | AtCoder

Problem Statement
ある路線には駅 1 から駅 N までの N 個の駅がある。すぬけ君は、この路線に準急を走らせることにした。
準急は、駅 1 に止まり、{駅 2, ..., 駅 N-1} の部分集合に止まり、駅 N に止まる。
連続する K個以上の駅に止まると、客が飽きてしまうので、そのようなことはしない。
準急の停車駅の組み合わせとして何通り考えられるか、mod 1,000,000,007 で求めよ。

Constraints
2≤K≤N≤1000000

最初の方針（ただし、計算時間が間に合わない）

まず答えがでる実例N=9, K=5で手計算すると、以下のように112通りになります。図は矢印にそって足していくだけです。駅1と駅9は絶対に停まるのには注意してください。
f:id:shindannin:20151224005704p:plain:w700

状態は、
- 何駅目まで来たか
- 現在何駅連続で停まっているか
遷移は
- 次の駅に停まる→連続で停まった回数が+1
- 次の駅に停まらない→連続で停まった回数が0に戻る

となるので、動的計画法で
dp[何駅目まで来たか][現在何駅連続で停まっているか]
とすれば、コードは以下のようになります。

#include <iostream>
using namespace std;

long long dp[123][123];

int main()
{
	int N,K;
	cin >> N >> K;

	long long  MOD = 1000000007;

	dp[1][1]=1;
	for (int n = 1; n <= N-1; ++n)
	{
		for(int k = 0; k <= K-1; ++k)
		{
			dp[n+1][k+1] += dp[n][k];  // 駅にとまる
			dp[n+1][k+1] %= MOD;
			dp[n+1][0]   += dp[n][k];  // 駅にとまらない
			dp[n+1][0]   %= MOD;
		}
	}

	long long ans = 0;
	for(int k = 1; k <= K-1; ++k )
	{
		ans += dp[N][k];
		ans %= MOD;
	}

	cout << ans << endl;

	return 0;
}

しかし、この問題ではNもKが1000000まで取りえます。計算時間もメモリも間に合いません。

累積和で状態数を減らす

動的計画法の計算量は、ざっくりいうと、以下のように状態数×（１状態あたりの）遷移数になります*1。
f:id:shindannin:20151224005712p:plain:w700
つまり、計算量減らして高速化するには、

状態数を減らす
遷移数を減らす

のが基本です。今回は、状態数が多いので、状態数を減らしましょう。1連続停車～K-1連続停車までを1つの状態にします*2
f:id:shindannin:20151224005718p:plain:w700
駅に停まらないケース（青線）は、矢印元と矢印先が同じ状態なので、そのまままとめられます。簡単。
f:id:shindannin:20151224005722p:plain:w700
ただし、駅に停まるケース（赤線）はどうでしょう？１番上のK-1回連続（先の例だと4連続）のケースは、駅にこれ以上停まれないので失われています。この部分は差し引かないとダメですが、状態をまとめてしまってはK-1連続停車の回数がわかりません。この部分をどうやって求めるかが、累積和を使った動的計画法のポイントです。
f:id:shindannin:20151224005727p:plain:w700
最初の図をよく見ると、回数が斜め方向に同じになることがわかります。改めて考えてみると、n駅でK-1連続停車した回数は、n-(K-1)駅で0連続停車した回数といっしょです。
f:id:shindannin:20151224005733p:plain:w700
0連続停車した回数は分かるので、これで計算できます。例えば駅5の1連続～K-1回連続は、4+4-1=7と求められます。
f:id:shindannin:20151224005738p:plain:w700
これで計算量はO(N)まで落とせます。コードは以下のようになります。

#include <iostream>
using namespace std;

long long dp[1234567];  // dp[n] = n駅まできて、現在0連続停車
long long sum[1234567]; // sum[n] = n駅まできて、現在1～K-1連続停車

int main()
{
	int N,K;
	cin >> N >> K;

	long long  MOD = 1000000007;

	dp[0]=1;
	sum[1]=1;
	for (int n = 1; n <= N-1; ++n)
	{
		dp[n+1]=sum[n]+dp[n];
		dp[n+1]%=MOD;
		sum[n+1]=sum[n]+dp[n];
		sum[n+1] %= MOD;
		if(n+1>=K)
		{
			sum[n+1]=sum[n+1]-dp[n+1-K]+MOD;
			sum[n+1] %= MOD;
		}
	}

	cout << sum[N] << endl;

	return 0;
}

まとめ

動的計画法の高速化には、状態数を減らすのが方法の１つです。累積和を使って減らすことができます。累積和の部分と累積和ではない部分の関係をどう立式するかで、アイディアが必要になってきます。
ただ、今回の方針は一例にすぎず、同じ問題でも多数のやり方があります。ぜひ「Typical DP 準急」で検索して、他の方針との違いも見てみてください。

応用問題として、ちゃっかりこの問題をあげておきます。累積和だけではありませんが、チャレンジしてみてください。
Contest Page | CodeChef

あす24日クリスマスイブは、競技プログラミングアドベントカレンダー創始者のtanzakuさんと、実際に役立った例を紹介してくださるuvarimeronさんです。楽しみですね。それでは、楽しいクリスマスを！

*1:本当は１遷移あたりの計算量も掛けないといけませんが、O(1)の問題のほうが多いでざっくり

*2:着想は、自分の場合は、１連続停車～K-1連続停車まで、だいたい同じような遷移をしているところから思いつきました。