Hatena::Grouptopcoder

横道にそれるTopCoder参加記録でもいいじゃないか

2015-05-05TCO MM round1 参加記録 このエントリーを含むブックマーク

machy320150505

反省会。

一言でいえば方針がよくなかった。

図の通り、対象の点を囲ってから多角形を凹ませていく方針

この方法にしたのは初手の選択肢が多いのがよいと思ったから。

内部にも外部にも自由な点をゆるしたのは、そのほうが動きが良く焼きなましやすいと思ったから。

そうしないとうまく焼きなませないと思い込んだから・・・。

思い込みはよくない。

2015-02-18要素数が2のべき乗ではないSegment Tree このエントリーを含むブックマーク

komiyamさんのブログ( http://d.hatena.ne.jp/komiyam/20131202/1385992406 )を参考にしてSegment Treeを書いていたところ、実装を間違えたのにテストが通ってしまったところから、どうも要素数を2のべき乗でなくてもそのまま動作することに気づいた。


素数は2のべき乗でなくてもいいのか?

考察してみたところ、問題なさそうなことがわかった。


■格納領域は重複しないか?

Nは2のべき乗とは限らない任意の自然数とする。

素数Nの配列src[0]..src[N-1]を

素数N*2の配列dataのdata[N]..data[N*2-1]に格納する。


data[k] の親ノードは data[floor(k/2)]

data[k] の子ノードは data[k*2+0] と data[k*2+1]

とする。floor()は小数点以下の切り捨て。


するとNの偶奇によらず floor((N*2-1)/2) < N だから、

末尾のデータdata[N*2-1]の親ノードdata[floor((N*2-1)/2)]と、先頭のデータdata[N]が交差することはない。


また、N' = floor(N/2) とすると、floor((N*2-1)/2) <= N'*2 - 1 だから、

ノードと親ノードの親ノードの関係についても再帰的に交差がないことが保証できる。


■親ノードに格納された値は正しいか?

もとの配列src[0]..src[6]の7要素だとすると、


data[0] は使わない


data[1] = data[2] とdata[3]の親 (data[2]が想定外で正しくない)

data[2] = data[4] とdata[5]の親


data[3] = data[6]とdata[7]の親 (data[6]が想定外で正しくない)

data[4] = data[8]とdata[9]の親

data[5] = data[10]とdata[11]の親

data[6] = data[12]とdata[13]の親


data[7] = src[0]

data[8] = src[1]

data[9] = src[2]

data[10] = src[3]

data[11] = src[4]

data[12] = src[5]

data[13] = src[6]


といったように親ノードに格納された値は正しくないこともある。


■正しくない値の親ノードは使われるのか?

上記の例では

data[3] は src[-1], src[0]

data[1] は src[-3], src[-2], src[-1], src[0]

といったように、正しくない親ノード実在しないリーフノードを参照している。


ノードは、そのすべての子ノードが範囲クエリーに含まれる場合のみ利用されるため、

正しくない親ノードの値が使われることはない。


また正しくない値のノードが、正しくあるべきノードの値を上書きすることはない。

(正しくあるべきノードの子ノードはすべて実在のリーフノードを参照しているから、子ノードからの更新で不正な値に更新されることはない)


以上の理由により、以下のように配列を2のべき乗に拡張せずに使っても問題ないようだ。


#include <vector>

using namespace std;

struct SegTree{
    vector<int> data_;
    static int operation(int op1, int op2){
        return op1 + op2;
    }
    SegTree(const vector<int>& src){
        data_.resize(src.size() * 2);
        for(size_t i = 0; i < src.size(); i++) update(i, src[i]);
    }
    int query(size_t begin, size_t end, int init) const{
        begin += data_.size()/2; end += data_.size()/2;
        for(; begin < end; begin /= 2, end /= 2){
            if(begin & 1) init = operation(init, data_[begin++]);
            if(end & 1) init = operation(init, data_[end-1]);
        }
        return init;
    }
    void update(size_t pos, int val){
        pos += data_.size()/2;
        data_[pos] = val;
        while((pos /= 2) > 0){
            data_[pos] = operation(data_[pos*2], data_[pos*2+1]);
        }
    }
};

#include <algorithm>
#include <random>
#include <iostream>
#include <cassert>
using namespace std;
mt19937 rand_gen(123123123);

int main(){
    int width = 999999;
    vector<int> v(width);
    for(int i = 0; i < width; i++){
        v[i] = rand_gen() % 1000;
    }
    SegTree seg(v);
    for(int t = 0; t < 10000; t++){
        int left = rand_gen() % width;
        int right = rand_gen() % width;
        if(right < left) swap(left, right);
        int ans1 = seg.query(left, right, 0);
        int ans2 = 0;
        for(int j = left; j < right; j++){
            ans2 += v[j];
        }
        cerr << left << ", " << right << ", " << ans1 << ", " << ans2 << endl;
        assert(ans1 == ans2);
    }
    return 0;
}

2015-01-08

Kaggle SantaHelper 参加記

22:35 | Kaggle SantaHelper 参加記 - 横道にそれるTopCoder参加記録でもいいじゃないか を含むブックマーク はてなブックマーク - Kaggle SantaHelper 参加記 - 横道にそれるTopCoder参加記録でもいいじゃないか

KaggleのSanta Helperは10位に終わった。悔しさで泣きはらす。

http://www.kaggle.com/c/helping-santas-helpers/leaderboard

colunさんとainu7さんのチームは2位、wleiteさんは7位、やっぱりred coderは強い・・・

2014年のクリスマスプレゼントを製造する問題かと思ったら、なんと2300年になっても出来上がらない。このサンタさんとエルフたちは人間と時間感覚が違うんでしょうね。

適当に簡単なタスクでやる気をアップさせて、100時間連続の非人道的なタスクを与える作業を繰り返せば済む問題かと思いきや、思ったより複雑でした。

生産性が1.0倍から2.0倍になったときは100時間タスクが50時間になるので50時間の改善があるけれど、1.0倍から4.0倍になったときは100時間が25時間になるので、2.0倍になったときからの改善は25時間だけ。生産性が高いほど、それ以上の生産性向上の効果は低くなる。

30時間タスクは、生産性1.0倍のときに実施すると30時間かかり時間外労働が多くて生産性が低下するが、生産性が3.0倍であれば10時間で終わるので生産性が向上する。生産性が高い状態であれば効率よく処理できるタスクがある。

5時間タスクは生産性0.5倍の時に実施すると10時間かかり、実施後の生産性向上が最も大きい。しかし生産性1.0倍のときに10時間タスクが品切れだったら、5時間タスクをやらなければならないかもしれない。

たとえばこんなジレンマがあるので、結局どう組み合わせたらいいの、ということになる。

なかなか面白かった。

生産性が下限の0.25まで下落するタスクであれば、実は何時何分に開始してもいいことに気づくと戦略が広がるところも面白かった。

良かった点。

いろいろ理論限界値みたいなものを試算して、改善余地のある部分を特定することができた。

要改善点。

テクニック、持ってる武器、手段が足りない気がする。強い人から盗み取らないと。

ビジュアライザを不精して作らなかったのも良くなかった気がする。

2014-12-16ひとりマラソン このエントリーを含むブックマーク

これは Competitive Programming Advent Calendar の12/16の記事として書かれました。

http://partake.in/events/9b53847a-3a97-4aac-b754-5e681c3c7197

■Problem Statement

ある駄菓子屋さんは10万個のお菓子を用意して、それらをいくつかの靴下の形の容器に販売しようとしました。

お菓子の大きさは2,000以上、5,000以下の整数の一様分布から生成されます。

靴下の容器はどれも同じ大きさで、1つにつき大きさの合計が10,000以下のお菓子を任意の組み合わせで入れることができます。

靴下の容器の数がなるべく少なくなるお菓子の詰め方を答えてください。

f:id:machy3:20141216085316p:image

これは「ビンパッキング問題」と呼ばれている問題で、何のオリジナリティもないですが、解法の特性を調べる上ではこういったシンプルな問題も良いのではないでしょうか。この記事では、この問題の解法をいくつか試した結果を書いみたいと思います。


まずgreedyな、つまり一度決めたら後戻りしない方法で解を作ってみましょう。


■greedyな解法の一例

大きいお菓子から、お菓子を入れたあとの隙間が最も少なくなる容器に入れる

今あるどの容器にも入らない時は、容器を1つ追加してそこにいれる


この解法の性能は以下のようになりました。


  • 容器の数 : 37,529
  • 充填率 : 93.35%
  • 処理時間 : 0.8sec

充填率は「お菓子の大きさの合計 / 容器の容量の合計」を表しています。

このデータセットで充填率が100%になるのは、容器の数が35032.8個の時です。

どうやら容器の数を35,033個より少なくはできないようです。


次に一度解を作ってから、少しずつ変更する方法を試してみましょう。


■解法A

10万個のお菓子を1つずつ10万個の容器に入れる。

ランダムに2つの容器i,jを選び、容器iからランダムにお菓子を1つ選び、容器jに移し替えようとする。容器が溢れてしまう場合は諦める。

移し替えた結果、空の容器ができた場合はそれを除去する。

上記の移し替えを30秒間繰り返す。


この解法の性能は以下のようになりました。


  • 試行回数 : 3.7億回
  • 容器の数 : 37,577
  • 充填率 : 93.23%
  • 処理時間 : 28.78sec

処理時間はずっとながいのに充填率は 93.35% → 93.23% でgreedy解法より悪いですね。


この解法を少し改善してみましょう。

以下の2つの図では、下の方が容器を1つ減らすのに近い状態であるといえます。


f:id:machy3:20141216085443p:image


充填率が高い容器を作っていけばいいわけです。そこで充填率が高い容器が減ってしまう時はお菓子の移し替えをやめることにします。


f:id:machy3:20141216085610p:image


■解法B

10万個のお菓子を1つずつ10万個の容器に入れる。

ランダムに2つの容器i,jを選び、容器iからランダムにお菓子を1つ選び、容器jに移し替えようとする。容器が溢れてしまう場合は諦める。

また容器iの元々のスキマが、移し替えたあとの容器jのスキマより小さかったときは移し替えるのをやめる。

移し替えた結果、空の容器ができた場合はそれを除去する。

上記の移し替えを30秒間繰り返す。


この解法の性能は以下のようになりました。


試行回数 : 3.4億回

容器の数 : 37,038

充填率 : 94.58%

処理時間 : 28.78sec


充填率は93.35% → 34.58% (+1.23pt) でgreedyを超えることができました!

このお菓子の大きさの分布(2000以上5000以下)はgreedyで解きにくいように調整してあります。お菓子の大きさの分布によってはgreedy解法もかなり良い性能を示しました。


もっと充填率を高めるにはどうしたらいいでしょうか。

1つのお菓子を移し替える方法には弱点があります。以下の図のように、悪い移動を使わないとならないケースが頻出することが予想できます。

一方、容器の中のお菓子を移し替えたり交換したりすることができれば、このケースは良い交換だけで最適化することができます。


f:id:machy3:20141216085609p:image


解の変化のさせ方の重要性についてはshindaninさんの「焼きなまし法のコツ」でも述べられています。

http://shindannin.hatenadiary.com/entries/2012/12/24


■解法C

10万個のお菓子を1つずつ10万個の容器に入れる。

ランダムに2つの容器i,jを選び、中のお菓子をすべて取り出す。ランダムに選んで容器iに入れていき、選んだお菓子が容器iに入らなかった段階で残りのお菓子を容器jに入れる。容器が溢れてしまう場合は諦める。

また容器i,jの元々のスキマのうち小さい方が、移し替えたあとの容器i,jのスキマの小さい方よりも小さかったときは移し替えるのをやめる。

交換した結果、空の容器ができた場合はそれを除去する。

上記の移し替えを30秒間繰り返す。


この解法の性能は以下のようになりました。


  • 試行回数 : 2100万回
  • 容器の数 : 35,800
  • 充填率 : 97.86%
  • 処理時間 : 29.37sec

94.58% → 37.86% (+3.28pt)とずいぶん充填率が高まりました。


まだ改善の余地はあるでしょうか。

必ず充填率が高まるように交換すればいいかというとそうではありません。

以下のケースでは、悪い交換をしなければ最適化することができません。


f:id:machy3:20141216085608p:image


そこで充填率が下がるとしても、それほど下がらないのであれば実施してあげることにします。


■解法D

10万個のお菓子を1つずつ10万個の容器に入れる。

ランダムに2つの容器i,jを選び、中のお菓子をすべて取り出す。ランダムに選んで容器iに入れていき、選んだお菓子が容器iに入らなかった段階で残りのお菓子を容器jに入れる。容器が溢れてしまう場合は諦める。

また容器i,jの元々のスキマのうち小さい方をspace_i、移し替えたあとの容器i,jのスキマの小さい方をspace_jとしたとき、space_i + margin < space_j のとき交換をやめる。margin = 200 * rest * rest で、restは残り時間の割合(1.0 〜 0.0)

移し替えた結果、空の容器ができた場合はそれを除去する。

上記の移し替えを30秒間繰り返す。


この解法の性能は以下のようになりました。


  • 試行回数 : 2200万回
  • 容器の数 : 35,660
  • 充填率 : 98.24%
  • 処理時間 : 29.84sec

充填率を97.86% → 98.24% (+0.42pt)に高めることができました。


最後に、もう一度交換方法を見なおしてみたいと思います。

容器の容量を超えない範囲で交換する、という制約をなんとか除去することはできないでしょうか?

容量制限を超えている容器がたくさんあると、いつ有効な解にたどり着くか分からないので、一つだけ、容量制限をこえた容器があっても良いことにします。


■解法E

10万個のお菓子を1つずつ10万個の容器に入れる。

左端の容器をiとし、容器iには容量を超えてお菓子を入れることもあることとする。

容器iを除く容器からランダムに1つの容器jを選び、容器jのお菓子をすべて一旦容器iに移す。もともと容器iにあったお菓子と合わせてランダムに選んで容器jに入れていき、選んだお菓子が容器jに入らなかった段階で移動を中止する。

また容器i,jの元々のスキマのうち小さい方をspace_i、移し替えたあとの容器i,jのスキマの小さい方をspace_jとしたとき、space_i + margin < space_j のとき交換をやめる。margin = 200 * rest * rest で、restは残り時間の割合(1.0 〜 0.0)

容器iが空になった場合はそれを除去し、左端の容器を新たに容器iとする。

上記の移し替えを30秒間繰り返す。


この解法の性能は以下のようになりました。


  • 試行回数 : 4600万回
  • 容器の数 : 35,267
  • 充填率 : 99.34%
  • 処理時間 : 29.25sec

充填率は 98.24% → 99.34% (+1.10pt) となり、かなり理想的な状態に近づいてきました。


使用したデータセットはこちらになります。

https://onedrive.live.com/?cid=A446049337A569DE&id=A446049337A569DE%21149

1行目の100000 10000は、お菓子の個数と容器の容量を表しています。

2行目以降はお菓子の大きさです。


よかったら挑戦してみてください。