狠狠撸

ねんがんのカグルマスターになったぞ！

サンタコンペとは？
? 毎年Kaggleで開催されている最適化系のコンペ
? 2013/14:なんか箱にいっぱい詰めるやつ
? 2014/15:小人の労働スケジュール最適化
? 2015/16:TSPのややこしいやつ
? 2016/17:ナップサック問題のややこしいやつ（スポンサーなし）
? 特徴：
? 年末年始に40日程度の短期間で開催されるので、平日は忙しい社畜さんでも安心！
? Private Leaderboardがなくて、手元で投稿しなくても答えがわかる（2016/17は例外）
? どっちかというとプロコンなので得意な人は得意

チームseed71とサンタコンペ
? PROJECT EULER引退(もうアカウント消えたみたい)
? 2014/15:やろうかなーと思ったら最適解がもう出ていた（その後リスタートしたらしい）
? KDDCUP2015で2位になる
? 2015/16:主に貪欲法でゴリゴリやって39位
? あにーりんぐ？なにそれおいしい？のレベル
? サンタの修行のためにKUPC(京大プロコン)に参加
? サンタの修行のためにAtCoder始める
? 2016/17:本気出す

サンタ2016/17の問題
? データ：7166個のGIFTID
? ただし各GIFTのWEIGHTはひ?み?つ
? 投稿ファイル:1000行以下のCSV
? 各行にスペース区切りでGIFTIDを入力
? 評価指標
? WEIGHTの合計、ただし各行(BAG)のWEIGHTの合計が50を超えたらその行[BAG]のWEIGHTは0で評価
? GIFTは9種類あり、各種類のGIFTのWEIGHTが従う確率分布は与えられている（ってかその乱数で作成され
ている）、コンペ中の値の変更はなし
? ちなみにSEEDリバースエンジニアリングできるレベルの乱数だったらしい

分布一覧
? horse: max(0, np.random.normal(5,2,1)[0])
? ball: max(0, 1 + np.random.normal(1,0.3,1)[0])
? bike: max(0, np.random.normal(20,10,1)[0])
? train: max(0, np.random.normal(10,5,1)[0])
? coal: 47 * np.random.beta(0.5,0.5,1)[0]
? book: np.random.chisquare(2,1)[0]
? doll: np.random.gamma(5,1,1)[0]
? block: np.random.triangular(5,10,20,1)[0]
? gloves: 3.0 + np.random.rand(1)[0] if np.random.rand(1) < 0.3 else np.random.rand(1)[0]

オーソドックスな解法その１
? 期待値を最大化する
? 1. 可能なBAGの詰め込み方を列挙（増やすと期待値が下がるようなら探索終了）
? 2. 上記の組み合わせを合計1000以下、かつGIFTの個数の範囲内に収まるように、期待値最大化
? 1. いいエクササイズ
? 2. よくある整数計画問題、どっかからパッケージ取ってくればすぐできる
→ 35670.41542

解法その２（計量）
? 1回の投稿で1個のGIFTだけ投稿すれば、その重さがわかる
? 正確には、1行に3個以上入れないとだめなので、ちょっと変わる
? 7,166回投稿するとただの整数計画問題で50,000ギリギリつける！
? 投稿の上限は1チーム126回なのでそこまでは無理
? 友達を60人集めて情報共有
? LEADERBOARDから得られる情報を最大化する、という問題である

解法その３（シャッフル）
? 同じ種類のGIFTでIDを入れ替えると、50を超える
BAGが変わるので、シャッフルしてたくさん投稿して、
最大値を期待する
? Seedはもちろん71、常識だよな！
? 全体をシャッフルするよりも現状のベストをちょっと
ずつシャッフルする方が良い
? やりすぎは危ない
? 純粋な乱数ではないので

Kernelの答え
? SEED変えて100個ファイル作っといたから、好きなの使いなよ、という斬新なものが出る
? バージョン込みでその数倍
? うち１つが大当たり(0.1%点くらい)という情報が拡散される
→ 36289.17158

本題：Seed71の解法
? 1. シャッフルする前提での期待値が高くなるように、整数計画問題を解いておく
? 2. Kernelの解を分割して投稿し、低い部分は1.の解に変換、高い部分は放置
? 事前にKernelのBAGSから1.の解への変換方法を作っておき、その変換が効くように分割
? 着眼：Kernelの解がそんなに完成度が高くはない
? やることはただの算数だけど、これでシャッフル対象を約半分に減らした
? 3. 分割して投稿してシャッフル
? 細かいところで投稿数を減らす(@ONODERA)
? 4. 計量とballまぶし

Seed71の整数計画問題
? 「あとでシャッフルできる」を反映
? 例えば25パーツに分けて、投稿数が100あるとするな
らば、最大化すべき報酬の項を「（乱数の）平均値」で
はなくて、「上位25%の平均」にする
? ハイリスクハイリターンな解が出てくる
? 環境はpythonでpulpというものを使用
? 自分でLP緩和とか書かなくていい
? あれ整数計画ってこんなに早かったっけ？ってくらい
には早い

Seed71の計量
? 期待値が低いBAGを2つを計量すると、35, 35だったとする
? 使っていないbike*2を投稿して、26だったとする
? ちなみにこれで50超えた場合、各bikeの期待値が上がって、再利用できる
? このとき、ball*23のBAGを１つバラして、35+ball*6, 35+ball*6, 26+ball*11にリフォーム
? なんということでしょう、たった3回の投稿で今まで使われていなかったbike*2を取り込み、26点UP
? 実際にはこの例のようにぴったりにはならないが、もう少し効率が良く、期待値は10/投稿くらい

Seed71のballまぶし
? 最終日付近のTシャツ欲しさのヤケクソ
? 幸運にも5投稿で50点くらい増やした（結果的にこれがなければ12位以下転落だったかも）
? もう少し運があれば最後の投稿で20点くらいさらに増えた
? ball*23のBAGを１つバラして、思い切って他のBAGに移す
? 運よく50を超えなければトータルは変わらずに空白のBAGができ、そこに新しく何か入れられる
? (9X%)^23の賭け
? Seedを71にすればそのくらいは???
? 失敗しても、幾つそんなBAG(推定47以上)があるのかはわかる

Seed71のシャッフル
? 多分上位に入った最大の要因は、シャッフルを「した」ことではなく、シャッフルを「やめた」こと
? 何度もシャッフルして、それでも下位に溜まってくるものは、もはや乱数ではない
? 1000パターン奥贰滨骋贬罢を割り振って検証

次のサンタコンペに向けて
? 次のサンタはソロで頑張りたい
? チーム組んだ方がソロより本気で頑張れるけど
? 「進めば進む程道はけわしくまわりに人はいなくなる
自分で自分をメンテナンスできる人間しか
どのみち先へは進めなくなるんだよ」（３月のライオンより）
? 蟻本買ってAtCoderで勉強します

狠狠撸

Santa2016_seed71

More Related Content

Santa2016_seed71