TopCoder Open 2012 Marathon Round 3参戦記

見せるフォーマットになってませんが、せっかくなので公開しておきます。
自分が組むプログラムは最低限説明出来るレベルになければならないと思うので、コンテスト中にそのことを意識したメモです。でも全く説明になってません。
自分のプログラムを追いかけたい！みたいな奇特な方がいればどうぞ

5/31(1日目)

問題を確認　http://community.topcoder.com/longcontest/?module=ViewProblemStatement&compid=26332&rd=15101
rnd(A,B)は、ランダムにA〜Bの値を意味する、という表記で
- ケーキがC個あります。C=rnd(1,10)
- ケーキを食べる人がG人居ます。G=rnd(2*C,10*C)
  - 一つのケーキにつき2〜10人
- ケーキの材料がI個あります。I=rnd(2,10)
- ケーキは正方形で、S*Sマスで表わされます。S=rnd(20,100)
- iさんが材料jをどれくらい好きかを表すint[] preferencesが与えられます。preferences[k]=rnd(1,10)
- i番目のケーキの(row,col)に、材料jどれくらい好きかを表すint[] cakesが与えらえます。cakesの生成方法は後程
- あなたは、ケーキを切り分けます。一人には１つのケーキしか出すことが出来ず、２分割とかされていちゃダメです。
- ケーキを食べたiさんの満足度は、Σ*1で決定されます。
- ケーキを食べた人の満足度の最小値を最大化しなさい。
- スコアは相対スコアで、１ケースにつき、YOU/BESTが加算されます。
とのこと。なるほど。ケーキの生成方法はが複雑そうだし、こちらも確認
- 材料は、土台とデコレーションで出来ていて、土台がI/2個、デコレーションがI-(I/2)個らしい
  - 奇数の時に土台がデコレーションより多いのがポイントかな。土台1種類が結構あり得る。
- まずは土台作り。
  - ケーキiのケーキの高さcakeHeight[i]をrnd(200,250)で決定します。
  - 土台の材料ごとに、layerHeight[i][j]をrnd(0,cakeHeight[i])で決定します。なぜか素材I/2-1だけはlayerHeight[j] = cakeHeight[i]みたい。
  - ケーキiの(r,c)の素材jが使われている量cake[i][row][col][j]を、max(0, layerHeight[i][j] + rnd(-5,5))で決定します。土台終わり。
- 次にデコレーション
  - デコレーションは、外枠rimと、なんだかよく判んないroseってので構成されています。
  - まずrimから。存在する確率は各ケーキにつき1/2
    - 外枠に使われている材料は１種類で、ランダムに1つ選ばれます。これをrimCompとする
    - 距離widthをrnd(2,S/6)で決定。デコの量layerHeight[i][rimComp] = rnd(10,40)で決定
    - 外枠からの距離がwidth以下のrow,colに対して、cakes[i][row][col][rimComp] = layerHeight[i][rimComp] + rnd(-5,5)とする。
  - 次にrose
    - 各デコ材料jについて、使うかどうかの判定を1/2で行う。
      - 上記rimComp決定後にこれが行われているから、rim存在率は1/2となっている
    - デコの量layerHeight[i][j] = rnd(10,40)で決定
      - rimが存在する場合は、layerHeight[i][rimComp]はrimの時と同じ。
    - roseを作る数nl[i][j] = rnd(S*S/40, S*S/100) 面積に対して1/40〜1/100個かな。Sが面積に見えるけど、横の長さなのに注意
    - nl個のroseの作り方
      - r=rnd(1,S/2), c=rnd(1,S/2)で場所決定
      - 線対称な箇所4つに作る。パターンは3種類で、ランダムに選ばれる
        
        縦、横の線に対して線対称なパターン (r,c),(S-r-1,c),(r,S-c-1),(S-r-1,S-c-1)
        
        対角線２本に対して線対称なパターン (r,c),(c,r),(S-r-1,S-c-1),(S-c-1,S-r-1)
        
        r,cの縦の線に対して線対称な位置から、対角線２本に対して線対称なパターン(r,S-c-1),(c,S-r-1),(S-r-1,c),(S-c-1,r)
      - こうして決定された場所に対し、マンハッタン距離１以下の場所row,colに、cakes[i][row][col][j] += layerHeight[i][j] + rnd(-5,5)する。

んー、少なくとも戦える問題だとは思う。
ただの焼きなましで戦える問題じゃないし、何度も関数が呼び出される形式でないのも良い。
ビジュラライザがないのはちょっと良くない。けどどう作るのが妥当か良く判らんね。作成コスト高そう。
直感的に、あんまりケーキを好きでない人がいる場合、ケーキ1つ占有してる人が最小値とかにならないか？
- 材料の種類数が少なく、土台が苦手な人がいる場合、って感じかな。そこまで頻度としては多くないし、満点ゲーの心配はないか

まぁ、とりあえず方針、２パートに分けよう
- 誰がどのケーキを食べるか決定する・・・A
- 1つのケーキに対し、最低満足度の最大化を行う・・・B
  - 余裕があるケーキに対しては、適当な処理で高速に行うのも大切かな。
Bを良い感じにアルゴリズムで作って、Aを焼きなます人が多そう。
けどAの焼きなましって結構局所解嵌り易そう。安易にやったらすぐ死ぬよね。
そもそもAを焼きなます時にBを使うのは微妙で、そこは概算で作らないと焼きなまし回数が酷いことになる。Bは2つに分ける
ということでまずは概算から考えよう

ケーキの分析
- 土台
  - 土台はrnd(-5,5)が入っているだけで、ほぼ一様。
  - 切り分け時に非常に扱いやすい。土台はどこにでもある。
  - I/2-1の土台は、常にmaxで入っているので最重要。１マスに付き平均200〜250
  - その他の土台は、期待値的に半分程度は入っている。１マスに付き100〜125
    - 適切なのを選べばまぁ半分以上の価値はありそう。
- rim
  - 存在率1/2。ない時もあるのに注意
  - 切り分け時に扱いやすい。
  - 量自体は、まず存在する箇所が、ケーキ自体に対して、ほぼ0〜5/9くらいまで。
  - デコの量は、rimが有効な範囲に対して、10〜40
  - 取り出しやすいし、考慮すべきものだけど、影響が超でかいか、と言われると疑問。土台が1でデコが10にとかだとまぁ超でかいけど
- rose
  - ランダムに存在
  - 切り分け時に意図的に回収するのはほぼ無理？
  - 完全に無理ではないので、概算時には適当な係数をかけて、「これくらいは取れるといいな」くらいにしてあげるのがいいのかな
  - 存在する面積が、個数がS*S/40〜S*S/100なので、これに５倍して、1/8〜1/20くらい。
  - 量も10〜40と控えめ。
  - 最初は完全無視しても殆ど問題ない範囲かも。

ということで最初の方針。全部適当だけど、基本方針はこんなもんでしょう。
- 人を分けるアルゴリズムをA、１つのケーキに対して概算するアルゴリズムをBとする。実際にケーキを切り分けるアルゴリズムCを最後の１回に使う。
- A
  - 適当に人を配置してBをやってスコア算出。前の状態から焼きなましするけど、最悪だった部分の人は必ず動かすように
    - 定義通りの厳密な焼き鈍し法はあんまり好きでないので、自分好みの適当な関数で。正確には焼きなまし法でないかも。
  - ある程度好みとか考えて動かしてあげるべきなんだろうけど、とりあえずは適当にランダムにみょんみょんと。一番悪かったところからランダムに１個別の所に移動、くらいでも良いかもね。それなら再計算２つで済むし
  - 状態遷移させるかの条件は、今まで見つけた答えを越えていないのがいくつ存在するか、でよさげかな。
    - １個なら100%、２個なら20%、３個なら4%くらい。直感的に。ここ最小値でやっちゃいけない
  - さすがに酷いから後で直すけど、焼きなまし覚えたての人がやりそうなアルゴリズムにはなってると思う。
- B
  - rimと中央部分に分け、各人が全部食べた時に、どれくらい満足度が得られるかを計算しておく。（１マスあたりの満足度も算出できる）
  - それを使うと、誰がどちらのケーキを優先して食べるべきか、が割り算してソートで算出できる。なので、最小値が小さい人に１マスずつ食べさせてあげる。
  - ・・・ってやるとO(S*S*logN)なので、答えを二分探索。定数20回もループすりゃ十分として、O(20*N)くらい。Nは平均2〜10くらいなので、まぁ妥当でしょう。
- C
  - 残り2秒くらいになった所で、答えを実際に生成する
  - ・・・・余裕だと思ってたけど、これめんどいなぁ。
  - とりあえずroseガン無視でいけばどうにでもなりそう。二分探索しながら外側と内からくるくるでいいかな。1ケーキに付きO(S*S*20)。
    - 実はくるくるさせると、線対称の4rose同時に取れるのね。そんな嬉しくないけど。
    - 二分探索はどう見ても甘えなので、もう少し後でなんか考える。
これくらいなら、そこそこのスコアのが30分もかからず組めそう。明日から関西だし、提出しておいて周りのスコアを見ておきたい。rim検出がちょっと面倒かな？
多分基本形はここから最終日まで変わらないんじゃないかな。Bがなくなる可能性はあるけど。
うん、シンプルだし、初提出としては良いんじゃないかな。泥臭さが出てくるのは、開始１週間後からでいい。

提出する前に上記アルゴリズムの問題点の列挙。ここに挙がらない問題点が見つかったら要検証
A
- ちょっと動かし方が適当過ぎる気がする。けど相当緩めに動かしてあげれば上手く行きそうな気もする。
- 工夫しようとして無駄が増えてて死んだのが去年のTCO11Finalなので、じっくり考えて使おう
- 概算しかしてないので、best100くらいは保持するようにしたい。
B
- 今回は最小値最大化の問題。「土台が嫌いな人を如何に満足させるか」がかなり焦点となる
- 全部嫌いだとどうしようもないのだけど、「如何にrimとroseだけで満足させるか」も結構大切
- となると、この概算は弱い。もっとも、現在Cがrose回収出来ないので、Cに合わせてBを変化させる形になるのだけれども
C
- 上記と同じ理由、現在roseを全く回収出来ないアルゴリズムなので弱すぎる
- 連続性を保ちつつ、roseを回収するにはどうすれば良いかを考察するべし。A,Bが重要なので、Cに凝り過ぎないようにするのも大切だけど。
- けどなんか、ケーキの数考えるとAあれで十分いけちゃうよね。確実にC勝負だけど、今の所有効なアルゴリズムは全く浮かんでないし辛いなぁ。

提出前スコアチェック

olg2002 9983.65 1 05.31.2012 00:50:56 Java 3 3
hama_du 7893.80 2 05.31.2012 05:59:55 Java 3 3
albert 7570.37 3 05.31.2012 02:30:14 C++ 1 1
ytau 6485.11 4 05.31.2012 05:41:16 C++ 1 1
Gowill_Yellow 6182.16 5 05.31.2012 06:46:54 C++ 10 3
amigooo 5811.10 6 05.31.2012 05:29:51 Java 1 2
ainu7 5687.65 7 05.30.2012 15:40:01 C++ 2 2
tloinuy 5621.64 8 05.31.2012 02:10:45 C++ 2 1
TrePe 5550.29 9 05.31.2012 04:22:36 C++ 1 1
Stefan70 5297.23 10 05.30.2012 16:15:42 Java 1 1

C=1でもほぼベスト取れてるっぽいし、Cちゃんとやってそうなスコアだね。
自分のが7000越えなかったら考察しなおし。

提出後スコアチェック(submit1)

chokudai 9772.11 1 05.31.2012 07:09:35 C# 1 1
olg2002 9705.84 2 05.31.2012 00:50:56 Java 3 3
hama_du 7671.00 3 05.31.2012 05:59:55 Java 3 3
albert 7334.51 4 05.31.2012 02:30:14 C++ 1 1
ytau 6292.98 5 05.31.2012 05:41:16 C++ 1 1
Gowill_Yellow 5989.11 6 05.31.2012 06:46:54 C++ 10 3
amigooo 5637.18 7 05.31.2012 05:29:51 Java 1 2
ainu7 5529.55 8 05.30.2012 15:40:01 C++ 2 2
tloinuy 5461.43 9 05.31.2012 02:10:45 C++ 2 1
TrePe 5399.48 10 05.31.2012 04:22:36 C++ 1 1
　

んー、olg2002さんは多分方針一緒。それ以外の人はまだまともにやってないか。
C部分が違いそうではある。ぐるぐるじゃなくて上から塗りつぶしとか。
まぁ基準としては十分だし、これで遠征しながらでも大丈夫かな

細かい修正(ex2)
- 修正前：if (Math.Pow(0.2, count - 1) > rnd.nextDouble())
- 修正後：if (precount >= count || Math.Pow(0.2, count - 1) > rnd.nextDouble())
- bestより悪い答えを出してしまっているケーキの数をカウントして、状態遷移させるかを判断していたけれども、前と状況が変わらないor良くなる時に、弾いちゃうバグを修正
- おおよそ1%弱の改善

細かい修正
- 一番悪い所から１個選んで移す時、移す先に重み付け。
- 重み付けを(自分のスコア-最悪スコア)でとりあえず。
- また1%弱の改善

細かい修正(ex3)
- 今までのこれ平らにしてるだけだよね。「この人はこのケーキを食べるべきだ」という意思に基づいて焼きなましされるべき。
- だったら、遷移先を選んだ時に、移りたい度みたいなのを出してあげよう。
- Pow(遷移先ave/遷移元ave,5)くらいかなぁ。重すぎるとあんまり良くないだろうけど。直感的には定数なら5、あとでcake数とかを入れてみても良いかも。
- うん、なんか良い感じにプログラムが可愛くなってきた。
- 2%強の改善
- Cにしたら0.3%の改善。最終調整必要な箇所の１つになりそう

細かい修正(ex4,submit2)
- 「こういう風に動いてね」と指示するのは、上記ので大体問題ないと思う。
- 「こういう風に動いたら偉いね」って褒めてあげるのが足りない。焼きなまし法は褒めて伸ばすアルゴリズム。正しく褒めてあげないとスコアは伸びない。
- ってことで、「この人はこのケーキを食べるべきだ」という意思を、きちんと数式にしてあげる。
- 相対値であれば、さっきのやり方で良いんだけど、絶対値となると難しい。さてどうしよう。そんなに数学的に厳密にしてあげなくても良いと思うのだけど。
- 適当にどれくらい好きかーみたいなのをノリで作ってあげよう。
  - まずlike1[i,j]=(ケーキiのjさんの1マスの平均満足度)/(jさんの1マスの平均満足度の最高値)　自分がどのケーキが好きかを0〜1で
  - 次に、like2[i,j]=(like1[i,j]/（任意のkに対し、like1[i,k]の最高値）)　周りと比べて自分がそのケーキをどれくらい食べるべきかを。範囲は0〜1
  - これを適当に3乗くらいしておいてあげれば良いんじゃないかな。
- このlike2[i,j]に対して、現在の状態のsumを取って、bestとの差をcountに足してあげたりすればちょうどいいんじゃないかな。
- 0.7%の改善
- スコア変化見てると、ちょっと小さいケースでAが窮屈そうにしてる気がする。もうちょい何とかしてあげたいなぁ

スコアの確認

chokudai 9997.61 1 05.31.2012 09:11:58 C# 4 2
olg2002 9528.32 2 05.31.2012 00:50:56 Java 3 3
discover. 7679.48 3 05.31.2012 08:59:57 C++ 4 2

前半１週間は気持ちよく勝たせてもらえるから良いね

細かい修正(ex5)
- さっき、「好きなのに移動させる」って言ったけど、どちらかというと大切なのは「嫌いなのに移動させない」ことだよね。
- ということで、さっきのは逆数を取ってあげる。で0〜1に調整。これでどうだろ。
- 0.15%の改善。んー、微妙
- こっちも３乗をC乗にすりゃいいか。→びみょ
- 係数まともに考えたら、Math.Pow(C * I * G, 1.0 / 3)*一定値みたいなのが良さげ？雰囲気だけど。　変化条件付けてあげると良い感じ？
- 0.1%の改善
- うん、適当にやり過ぎだ。もうちょっとちゃんと考えるべき。もうちょっと数学的に詰めて後でちゃんと実装しなおそう。
  - 公開用メモ取ると、こういう暴走して馬鹿なことやってる時にすぐ止められるから良いよね。
- 適当に数値表示してみたら、なんか累乗しなくても全然よさげだし。もうちょっとちゃんと見るべき。
- Bが若干大きい誤差出してる時があるのが気になる。どういうケースなんだろ？まぁCが優秀になれば、Bよりだいぶ小さい値をCが出すことはなくなるはず？
- Cはゆっくり考えよう。とりあえず細い形にしちゃうと後で変化させ辛いので、くるくるでない形にしたい。rimとそれ以外が区別出来ていれば良い、というのを忘れちゃいけない。
  - つーかCも初期配置だけ決めたら焼きなましちゃえば良いやん、という気分になっている。
  - こっちからやる人がいると思って、C=1で虐殺される予定だったのだけど、なんか微妙なのよね。

他の仕事しながらでも出来る実験
- ローカルで30秒で動かしてみる。これによるスコアの変化で、焼きなましがちゃんと出来てるかが判る。
- 色数が少ないケースでは特に変化なし。色数の多いケースで1%〜2%負け。全体で0.3%負け。
  - 色数少ないケースでは大体収束してるのかな。色数が多いケースだと全然収束遠い感じ。
- 何度も実行して結果が大きく変わったりするのもまずいんだけど、そちらは問題なさげ。
- うん、まぁなかなか良く動いてる感じがする。Aはかなり完成に近いのでは
- んじゃC頑張るかぁ。Aの焼きなましが超速で終わる、ってことはなさそうなので、Cは１ケースに絞って焼きなましで大丈夫かな。
- Cに合わせてB変えないといけないのがむずいね。面積やらroseの数やらにそこそこ依存しそうだから大変。

6/1(2日目)

祖父母孝行のためおやすみ

6/2(3日目)

祖父母孝行のため大体おやすみ

とりあえずC部分酷いのをどうにかしよう。
Cはくるくる大雑把なアルゴリズムで良い気もするので、Dちゃんを作ろう
Dは、くるくるをするのだけど、くるくるの順番を全通り試すアルゴリズム、ということで
１個のケーキにn人居るとして、適当にやると、
- permutation数 O(n!)
- １回の試行 O(S*S)
- 合わせてO(n! * S^2)
うん、まぁn=7くらいから死ぬね。
ということで二分探索で。bitで今まで使ったのを管理して、スコアを一定以上にしたい時にどこまで進めるかを管理する
- 状態数 O(2^n)
- 状態遷移先 O(n)
- 状態遷移コスト O(S*S/n)
- 二分探索回数　20回くらい
- 合わせてO(2^n * S^2 * 20)
- マシになったけど、20<=S<=100だしn==9くらいで死にそう
んじゃ、前計算してあげる。特定のケーキの、食べる順番が決まっているとき、Aマス目から何マス食べれば、目的スコアを越えるかは、尺取法により、一人に付きO(S*S)で求められる。
これを使うと計算量はこんな感じ
- 前計算
  - 人数 O(n)
  - 尺取法コスト O(S*S)
- DP部分
  - 状態数 O(2^n)
  - 状態遷移先 O(n)
  - 状態遷移コスト O(1) ←ここが前計算により改善
  - 二分探索回数 20回くらい
- 合わせて、O((20 * 2^n + S*S) * n)
うん、n=15程度が上限だろうし、楽勝っぽくなったね
0.5%程度の改善

そだ、A問題の、どれを遷移させるかの重み付け
sumscore += Math.Pow(Math.Max(rimave[to, item], centerave[to, item]) / Math.Max(rimave[from, item], centerave[to, item]), C);
like作る前だったからこれでやったけど、like使うと多分良いんじゃないかな
Math.Pow(like[from, item], C) / Math.Pow(like[to, item], C);とかに。
これだけで0.5%の改善。やっぱ焼きなまし弱かったかー
ここで提出(submit3)。17点差くらいで1位だったかな
旅行先だし、殆ど時間もないのでこれくらいでおしまい。

6/3（４日目）

この日も祖父母孝行→ICPC凱旋パーティーのため殆ど何もできず

なんか抜かれて２位とかになってるけど、Aの重み付けまだ適当だし修正すりゃ抜かせるだろう。
交換元は一意に決めてたけど、交換先の重み付けが適当だった気がする
Math.Pow(tscore[i] - tscore[minnum], 1 + (double)C * sw.ElapsedMilliseconds / Alimit)とかでいいや。AlimitはAに使う時間。現在は5000に設定
- tscoreのtってなんだろ。tmpかなんかかなぁ・・・なんかノリでtって付けること多い気がする
- doubleは甘えかなぁと思いつつ、ボトルネックじゃなければ判り易いからガンガン使う
とりあえずこれで提出して１位奪還
0.025%の改善だったらしいけど、このレベルだと100ケースじゃもう充てにならんね

6/4（5日目）

東京帰ってきたしそろそろ本気出す

ランキングチェック
- ６位以下は気になる人を選出
- 多分現ランキングで言うと通過ラインは10300あたりなんじゃないかなぁ。適当な予想だけど
- olgさんどこいった
- 強豪ちょっと出て着すぎじゃないですか
- そもそも焼きなましで均等に振り分けてあげるだけで9300くらいなはずなのだけど、それより下の人は何をしているのだろう
  - 一応rim考慮して外側から配置してるのが効いてるのかな。それでも9000未満はなんかおかしいよね。どういう方針違いをしているのだろう
  - 最初っからケーキの切り取り方を焼き鈍ししてるのかな。だとしたら自分のプログラムと合体させたいなぁ。そこまだ作ってないもん
  - 最低値のみ取り扱う焼きなましになっちゃって、上手く動いてないパターンもありそう。焼きなまし法をちゃんと習うと出てくる弊害みたいなイメージ

chokudai 9983.27 1 06.03.2012 11:37:42 C# 8 4
venco 9977.73 2 06.03.2012 10:49:49 C++ 7 6
ainu7 9936.73 3 06.02.2012 00:12:51 C++ 15 7
koda 9903.60 4 06.03.2012 18:11:44 C++ 11 8
Mojito1 9855.15 5 06.03.2012 15:27:05 C# 8 9
okazaki 9805.03 6 06.03.2012 13:34:41 C# 20 17
protocolocon 9755.95 7 06.03.2012 14:25:33 C++ 5 5
lyrically 9688.41 8 06.03.2012 19:34:09 C++ 3 3
jlahd 9628.68 10 06.01.2012 18:11:48 C++ 3 3
wata 9351.78 13 06.03.2012 14:49:41 Java 4 1
hama_du 9305.21 15 06.04.2012 00:12:33 Java 5 5
Komaki 9024.88 19 06.01.2012 07:54:54 C++ 12 4
yowa 8702.64 26 06.01.2012 13:44:20 C++ 4 4
doudouille 8382.33 28 06.02.2012 08:48:54 C++ 1 2
crussell 6589.30 41 06.03.2012 17:16:51 C# 1 1
olg2002 2182.29 70 06.03.2012 16:56:35 Java 6 8

さて、やるべきものは幾つかあるので、とりあえず列挙
- A
  - 調整不足が見つかっているので、そのあたりをもう少し点検
    - 選択基準だったり、likeが妥当かどうかだったり。
- B
  - 高速化。20回の二分探索でも、そこがボトルネックになっていることを考えると改善するべき。
  - ソートした段階で適当に結果メモしときゃいいんじゃないかな。どうせ同じ計算何度もやってるだろうし
- C
  - この子はもうこのままでいいや。
  - もうちょいなんかするとしたら高速化だけど、そんな早い必要もないからなぁ
- D
  - この子も大丈夫。十分早くしたつもり
  - と思ったらkの探索範囲を狭められたので即直す
- E(new!)
  - Dでやった結果を焼き鈍す。もしかしたらDとの間になんか入れてあげるかも。
  - Dだと環状になっていて自由度が低いので、ちょっと弄ってあげないとかも。
  - 環状でも良いのだけど突き破れるかどうかの判定が超大変。突き破りはナシで考えるのが良いかなぁ。突き破りなしだと、実は連結判定超簡単なんだよね
  - なんか、未だとABCDEF...みたいな層のでき方なのが、ABABCDECFみたいな感じで、突き破って新しい層が出てくる、みたいなのを許容してあげたいなーとか
  - まぁどちらにしろE自体の実装は変わらないだろうから、早めに組んじゃっても良いかも。そんなに活躍する子じゃないから、将来的に使わない可能性もあるけど。

とりあえず、Bの結果をメモ化したいなー
A側でメモ化。dictionary使って送信 0.1%くらいの改善(submit5)
A側は配列で十分なので、配列に変更。B側でもメモ化。
5秒で1000000回くらい回ってるし、まぁこんなもんかなー。
ってあれハッシュ衝突してる　あれ
{0,1,2}と{1,2}を同一視しているバグでした。修正終わり(ex10)
あんまり高速化してもスコア伸びてない感あるけどいいや。寝る前に60sec testしよう

んで、Bだ。C,D,Eで伸びるかどうかを調べたい。
今なぜか整数マス単位でやってるけど、別に小数マスでもいいよね。概算だし。あとで修正効くし
- あー、でもデコなしの時十分に強力なのかなぁこれ
- 小数マス数を許容できる感じにして組み直し。本質的じゃないけどとりあえずテスト回しとこう
- 0.01%悪くなってる。誤差過ぎて何とも
今度こそ、C,D,Eの過程で伸びるかどうかを調べる
- 伸びる条件って、多分roseの個数と、どれくらいの人数で食べようとしているかだよねー
- どーやって出すかな。point収集してるとこでやらんとまずいよね。
- もっと厳密に言うなら、層ごとのrose差とかやらんといけないのか　何それめんどい
- んー、ヒューリスティックに調整しないといけない所だと思うのだけど、もう500caseに増やすのはちょっと微妙な気がするなぁ
- 保留。Eの出力結果見てから考える。

つーことでEを組まなければならない。
- O(S*S)していいのはまぁ前計算くらい。これで、「このマスが切断して大丈夫か」を格納する。
- 切断してはいけない条件は、「上・右が同じ色　＆＆　右上が違う色」＊４と、「上・下が違う色　＆＆　左・右が同じ色」＊２の６つ。これを格納してあげる。
- 0の奴を連想配列かなんかに格納しておけば、隣接マスのみ考えてあげる感じになる。交換コストも、隣接8マスについてこれしてあげるだけ。
- Aと同じく、一番悪い所から、良い所を選んで焼きなましてあげれば、まぁそこそこ良い感じになりそう
- 組む。そこそこ良い感じ。0.5%程度の改善。ainuさんに抜かれていたので提出する　(ex11,submit6)

スコアチェック
- まぁとりあえずは勝ってるけど・・・
- んー、Eの処理はみんな出来ることで、C,Dでもっと良い戦略取られてるとEの差も出るし普通に負けそうなのが怖い
  - Eは実装めんどいし、やってない人がそこそこいそう
- あとはroseを積極的に取りに行ったような配置。作るのむずいけどねー。
  - roseを取らせるために狭いとこ走らせるのはまぁほぼ無理で、となると、最初から変な形にしないといけない。むずい

chokudai 9993.11 1 06.04.2012 11:44:33 C# 11 6
ainu7 9954.32 2 06.04.2012 11:39:22 C++ 21 12
venco 9940.93 3 06.03.2012 10:49:49 C++ 7 6
koda 9866.98 4 06.03.2012 18:11:44 C++ 11 8
Mojito1 9818.80 5 06.03.2012 15:27:05 C# 8 9
　

Eの調整
- どうせ重み付けとか足りてないよねこれ
- (point[to]/point[from])^3とかやってたけど、ぬるい。貪欲に取るくらいの勢いで十分なので、30に(ex.12
- 0.17%くらいの改善　暫定１位の状態で弾残せるのは素晴らしい
- しかしまぁ、最終的にはこういう形になるわけで、Eはそこまで変えなくても、D部分をどうにかしないと、このパターンに持ち込めないよね　http://screencast.com/t/By8gXcMIZN
- この辺はじっくり考えたいところ。 x=S/2,y>=S/2の時だけ、横の切っちゃだめを無視できる、みたいな適当な手法も選択肢としてあり得るけど
- つーか最初環状にしなければここら辺解決するんじゃね？（多分しない

Eが出来たので、Bの調整
- とは言ってもどう調整するのが良いのかわかんねーｗ
- ちゃんと統計取らないと無理だね
- Bの結果と色んなデータを出力して重回帰分析とかするかなぁ。R使って分析するの、本番じゃ出来ないのがちょっと嫌なんだよね
  - もっとちゃんとやるなら重回帰分析じゃ温いのだけど、今回は焼きなましで超使う部分なので、計算量が軽めのものを選択
- そこまでやるのはD,Eがもうちょっと良くなってからでも良い気がするのだけど、Bの精度は上げたいなぁ
- 考えられるデータの種類を列挙しよう。目的変数は(D→E)/Bなので、説明変数を考えないといけない。
  - まず人の数。これは多い方が伸びそう（８日目訂正　嘘でした）
  - rim。Dでの入れ替え数が制限されるから、ない方がよさそう。あったら全部一緒なんじゃないかな。
  - rose。多い方が良さそう。
    - 多い方が、ってのをどう判定するかなぁ。デコの割合とか判定可能かなー
    - 標準偏差とか調べた方がいいのかなぁ。ケーキの情報だけなら、ある程度計算量掛けても、前計算だからどうにかなる。
- んー、なんかイメージが出来てない。良くない。
- 頭が働いてる時にしよう。寝よう。

6/5（6日目）

スコアチェック。あんまり変わってない。
- wataたんが自分と同じ上がり方してて判り易い。olgさんとかdoudouilleさんがどういう方針なのか全然分からん。
- doudouilleさんはBすっ飛ばしてCやっちゃってたりとかして、焼き鈍しが重い、とかかなぁ。
- olgさんはただの潜伏っぽい気がするけど、相対で潜伏はどうなのかなー。１位の時のスコア隠しは自分もやるけど。（っていっても今17点分しか隠せてないけど）

wata 9571.63 13 06.05.2012 00:17:57 Java 5 2
doudouille 8351.02 36 06.02.2012 08:48:54 C++ 1 2
olg2002 2170.09 86 06.03.2012 16:56:35 Java 6 8

B直そう。
B直し方浮かばん。0.2%くらい変動する肝な部分だと思うんだけど、なんか有効な要素の列挙で詰まってるなー
Aの調整甘そうだから直そう、多分ここの調整まだ0.1%くらい上げれるっしょ（現実逃避
0.06%の改善。ほら。・・・ただ、なんか重み付け重くすればする程上手く行ってるこの感じ、ちょっと嫌だなぁ
もうちょい改善、
- if (tscore[i] <= best) count += 1だった部分。これだと、１つの場所に負債を抱え込んでる状態が良いみたいになってしまう。
- if (tscore[i] <= best) count += 0.8 + (best - tscore[i]) / best * li[i].Count /10;　に変更していた。負債をきちんと影響させてあげるため
- if (tscore[i] <= best) count += 0.8 + (best - tscore[i]) / best * li[i].Count;　と、影響力を10倍にしてチェック。やり過ぎでスコア落ちる。
- というかng頻度高いしcount += 0.4 + (best - tscore[i]) / best * li[i].Count / 5;とかで良いのでは。ノリで決めてるけど。→結局悪い。むむむ・・・
- いい加減適当に弄っても増えなくなってきた。そりゃそうか。

ここで学校に行こうとしてノートパソコンと同期しようとしたら、逆側に上書き保存してしまう。そんな馬鹿な。

Marathon Matchで大切なのはバージョン管理です！（開き直り

2012-05-27 03:27:11 via P3:PeraPeraPrv

SVMとSVNを言い間違えたこのツイート、フラグになるとは思わなかったよ・・・ｗ
しゃーない。これからちょうど学校だし、過去にbest出したやつだけ再現させて、それとの直接比較でどうにかしよう。データ数減っちゃったのはちょっともったいないけど
- そしてやはり悪くなっていたという・・・

B直そう
- Bを直せばスコアが良くなるという自信を付けよう
- 適当にそれっぽく調整をしてあげる
  - min *= 1 - num.Length * 0.04 / S;
  - if (rim[c] != 0) min *= 0.995;
  - if (num.Length != 1) min *= 1 + decoave / 10;
- これくらいで良くなってそう。実験
- 0.13%の改善　ｲｲﾈ!
- デコレーションを同一視してるのはさすがに酷いのでは。
- 分離。計算量重いかなーと思ったけど意外とそんなことなかった。
- 0.07%の改善。うん、悪くないね。
- 調子乗って重み付けを増してみる
- 色々やったけど微妙な印象
- 要素不足感はあるのだけど、やっぱり良くはなった。真面目に統計取れば後0.1%は行けそうかな。
  - 焼き鈍しが十分に早いのであれば、CやDと並列でやるのも検討。Eは無理。DとEの間の子がいるかなぁ。ってかE遅いのかなぁ。もうちょい高速化は確かに出来るけど。６倍くらい？

6/6（7日目）

今日を乗り切れば前半折り返しで１位

さて、どうしよう。ainuさんと5点差。30点くらいストックあるけど、すぐひっくり返されるよね。
とりあえずEの高速化。
- 定数倍っぽい地道なのは後で。絶対必要になるから今でもいいんだけどねｗ
多分焼き鈍そうとして収束しなくてみょーんとなっているので、重み付けを超増やす。 0.005%の改善。んー？ｗ
出力結果、roseを拾い集めてる感のあるものが全然出たことがないのだけど、これは何なんだろうなぁ・・・
まぁなんかpoint関数作る時の重み付けがまずいんだろうけど・・・んー
重み付けたっぷりで良いから、収束しちゃった時に、崩してあげたいよね。
- となると現状の問題点は、「崩してあげた後に、『それ崩すと次のを回収できなくなっちゃう』みたいなのを平然と崩していくことだよね
- 基本的に1個ずつのトレードしか行われないわけだし。
- スコア適当に出してみたら収束してるんだろうなー→交換先が結構ランダム性があるから、意外と収束してなかった。けど多分広めに見ると収束してそう

Bの最適化をしよう
つってもまぁ無理があるのでDで色々やってみよう
しかし平均化考えるとBのが精度良くね・・・？Eで平均化するし。Dはそこの精度悪すぎるし
え、じゃあ予測どう立てるのよ
あれ、ってかEまでやった時の予測スコアってB凄く良くね。なんでこんな悪くなってんの馬鹿なの死ぬの
結局何もできず。むむむ

6/7(8日目)

折り返しー　出版社に缶詰なので午前中だけ。

とりあえず適当にテスト、seed 37が1653762安定なのに、なんか1291661とか出してる。なんぞこれ
多分焼きなましがヤバイ。変に収束してる。もうちょっと時間の影響上げてあげないとまずいかな。最初は色々変化させて、ほぼ貪欲は最後だけでおｋ
と思ったけど、変に変化させない方がよさげ。
単純に、配置数0の時にそこにしかいかなくなってて、1-0間で無限に交換している感じになっていたので、上限値みたいなのを付けてあげればなんとかなった
とりあえず提出して２位と50点差くらいに。これが12日目とかだったら逃げ切りっぽいんだけど、まだ８日目だからなぁ。

6/8(9日目)

あと100点取れれば逃げ切りだろうけど、ローカル相対評価で今提出してるのが9969点（これで最高点）。31点分落としてるわけだけど、新規にbestそんなに出せるのかね・・・。
やっぱ肝はBだよね。D予測は時間かかる上に現在のBと大差ないし、Eは時間かかるしで、Bのうちに高精度な予測を出すことが超重要
Cは二分探索２０回として、今O(20*S*S)とかで、累積和使うとO(20*N*logS)とかになって超縮むから、これ8回やってもかなり強いっちゃ強いのだけど、多分単純Bより弱いよねぇ・・・
けど、重回帰分析とかで大丈夫か、って言われたら、ちょっと怪しいよね。どうやろうか
とりあえず明日！忙しい！ｗ

6/9(10日目)

もっかいBについての考察
Bがやってる事は、rim平均値とrim以外の平均値を取って、rim/rim以外が高い方から割り当ててる。
- この際、割り当てるマス数は、以前は整数だったけれども、小数に変更した
要するに、「roseや誤差を完全に無視した上で、完全にバランス良く配置出来た時の点数」
- これをC,D,Eで軽く超えてるんだから、そこらの性能も捨てたもんじゃない気はする。
次に、単純B→Eでの影響要素を列挙
- 人の数。これは前「多い方が良い」と言ったけれども、少ない方が良いのでは。
  - 確かに人数が多い方がDで色々試せるのだけど、その色々試さないといけないのって、結局バランスが取れないからでは。
  - 99 100 100 101と99 101だったら絶対後者のが実現しやすいよね。同じ数でそういう差が出るとしたら、1マス単価が小さいはずだから、198 202と実質同じ。
    - ってそうか、1マス単価考えるべきか。S*Sのサイズによって全然平らにしやすさが違うよね。
    - 「マス数整数制限による誤差」が、１タイル分より確実に小さいことを考慮すべき。
ここで時間切れ

6/10(11日目)

多忙のため何もせず

6/11(12日目)

大学だけど、ainuさんに10点差まで追いつかれてるし、そろそろ本気でやるよー！

さ、Bをやろうか
単純Bの結果と途中経過、Eの結果を出力します！
5000個くらい出力出来たら、Bの評価関数を適当に作りまくるよ！
統計を取って良いものを作ろう！
とりあえず適当に出力。(予想値)/（実測値)-1　を0に近づけるのが目標で
- aveが単純平均、paveが二乗平均、aaveが絶対値とったあとの平均 Sがサイズ、Lが人数、Rはrimの有無
まずは単純なBをそのまま使った場合



overall

average :	 -0.0134712384

paverage:	 0.0185636706

aaverage:	 0.0136664347

for S

S 20-29 data: 526 -0.0102337 0.0160532 0.0113724

S 30-39 data: 583 -0.0137998 0.0194235 0.0139522

S 40-49 data: 583 -0.0137811 0.0186225 0.0139282

S 50-59 data: 516 -0.0137516 0.0186983 0.0137978

S 60-69 data: 468 -0.0142860 0.0191180 0.0143050

S 70-79 data: 527 -0.0144334 0.0195552 0.0144527

S 80-89 data: 479 -0.0142347 0.0192303 0.0142539

S 90-99 data: 528 -0.0133837 0.0176318 0.0134009

for L

L 1 data: 82 -0.0000010 0.0000010 0.0000010

L 2 data: 329 -0.0147798 0.0212639 0.0147807

L 3 data: 525 -0.0138368 0.0195527 0.0138461

L 4 data: 565 -0.0152814 0.0201332 0.0153092

L 5 data: 505 -0.0151224 0.0196590 0.0151645

L 6 data: 504 -0.0159367 0.0204414 0.0159932

L 7 data: 471 -0.0150290 0.0194125 0.0151529

L 8 data: 415 -0.0132928 0.0177595 0.0134750

L 9 data: 348 -0.0123305 0.0160926 0.0125955

L 10 data: 263 -0.0110064 0.0153827 0.0113112

L 11 data: 146 -0.0077920 0.0122897 0.0087312

L 12 data: 64 -0.0044586 0.0093469 0.0059864

L 13 data: 38 -0.0032158 0.0078124 0.0049038

L 14 data: 11 0.0003393 0.0013476 0.0008616

L 15 data: 7 0.0031389 0.0080809 0.0059041

L 16 data: 7 0.0025711 0.0077533 0.0051094

L 17 data: 2 0.0044029 0.0058899 0.0044029

L 19 data: 1 0.0060689 0.0060689 0.0060689

for R

R 0 data: 2123 -0.0114841 0.0178176932 0.0118528

R 1 data: 2160 -0.0154243 0.0192687480 0.0154490

aveが0になるように調整してあげます



overall

average :	 -0.0001620262

paverage:	 0.0128078966

aaverage:	 0.0096480564

for S

S 20-29 data: 526 0.0032003 0.0128896 0.0103670

S 30-39 data: 583 -0.0005857 0.0136821 0.0094894

S 40-49 data: 583 -0.0003072 0.0126479 0.0098659

S 50-59 data: 516 -0.0006628 0.0125857 0.0094217

S 60-69 data: 468 -0.0009597 0.0127738 0.0092159

S 70-79 data: 527 -0.0011873 0.0132424 0.0096448

S 80-89 data: 479 -0.0009598 0.0129735 0.0100299

S 90-99 data: 528 -0.0000184 0.0115141 0.0090282

for L

L 1 data: 82 -0.0000010 0.0000010 0.0000010

L 2 data: 329 -0.0012252 0.0155462 0.0113990

L 3 data: 525 -0.0002692 0.0140075 0.0099513

L 4 data: 565 -0.0017337 0.0134012 0.0099997

L 5 data: 505 -0.0015725 0.0128310 0.0095721

L 6 data: 504 -0.0023980 0.0131971 0.0101451

L 7 data: 471 -0.0014778 0.0125435 0.0092687

L 8 data: 415 0.0002822 0.0119425 0.0095693

L 9 data: 348 0.0012578 0.0105581 0.0087318

L 10 data: 263 0.0026002 0.0112004 0.0090240

L 11 data: 146 0.0058587 0.0112760 0.0095877

L 12 data: 64 0.0092380 0.0124376 0.0112291

L 13 data: 38 0.0104980 0.0127398 0.0115540

L 14 data: 11 0.0141019 0.0141637 0.0141019

L 15 data: 7 0.0169400 0.0185459 0.0169400

L 16 data: 7 0.0163644 0.0179661 0.0163644

L 17 data: 2 0.0182214 0.0186481 0.0182214

L 19 data: 1 0.0199104 0.0199104 0.0199104

for R

R 0 data: 2123 0.0019409 0.0138851166 0.0107996

R 1 data: 2160 -0.0022289 0.0116524898 0.0085162

paverageを最小化したいなーと思っているので、0.0128のを縮めればおｋ。
誤差0.013%ってどうなんだろ。多いのか少ないのか。0.005%くらいに減らせたら結構よさげではあるのかな。
- ただ、がくっと変化させちゃうと色々酷いことになるので、そういう調整はしないように。（Sについては全ケース固定だし良いのだけれども）
適当に頑張った結果がこちら

overall
average : 0.0001254251
paverage: 0.0066375509
aaverage: 0.0041691388
for S
S 20-29 data: 1033 0.0012927 0.0075304 0.0051181
S 30-39 data: 1059 0.0002797 0.0073049 0.0044730
S 40-49 data: 950 0.0000516 0.0061567 0.0039841
S 50-59 data: 932 -0.0005047 0.0065033 0.0039352
S 60-69 data: 818 -0.0002763 0.0064411 0.0040248
S 70-79 data: 930 -0.0000420 0.0064023 0.0037721
S 80-89 data: 918 -0.0003084 0.0066900 0.0042572
S 90-99 data: 912 0.0004173 0.0058378 0.0037080
for L
L 1 data: 147 -0.0000010 0.0000010 0.0000010
L 2 data: 608 -0.0009813 0.0089367 0.0051976
L 3 data: 954 0.0006379 0.0081952 0.0051828
L 4 data: 974 0.0003647 0.0073647 0.0047669
L 5 data: 938 -0.0000745 0.0070854 0.0045832
L 6 data: 926 -0.0004604 0.0065089 0.0043648
L 7 data: 852 0.0001656 0.0060957 0.0039697
L 8 data: 764 0.0002019 0.0050592 0.0034918
L 9 data: 607 0.0005362 0.0050501 0.0035983
L 10 data: 455 0.0004291 0.0055813 0.0034984
L 11 data: 248 0.0012624 0.0043734 0.0026964
L 12 data: 126 0.0005910 0.0033877 0.0023407
L 13 data: 69 -0.0004190 0.0028023 0.0020161
L 14 data: 25 -0.0015850 0.0033450 0.0028032
L 15 data: 17 -0.0003196 0.0041990 0.0032446
L 16 data: 11 -0.0022730 0.0055957 0.0047928
L 17 data: 3 -0.0017805 0.0035949 0.0034185
L 19 data: 1 -0.0012764 0.0012764 0.0012764
for R
R 0 data: 3778 0.0000394 0.0053349779 0.0030152
R 1 data: 3947 0.0002077 0.0076801324 0.0052737
for D
D 0 data: 3598 0.0004155 0.0033004894 0.0020439
D 1 data: 2300 0.0012873 0.0059814445 0.0044644
D 2 data: 1102 -0.0009114 0.0086847764 0.0064851
D 3 data: 470 -0.0028971 0.0115294562 0.0087052
D 4 data: 178 -0.0048078 0.0152873100 0.0117797
D 5 data: 46 -0.0071847 0.0191792001 0.0156246
D 6 data: 21 0.0032841 0.0203066521 0.0165239
D 7 data: 7 0.0022488 0.0129811744 0.0110637
D 8 data: 2 -0.0212247 0.0466979758 0.0415958
D 9 data: 1 0.0233068 0.0233068324 0.0233068
for DS
for DS sum

0.0016 +0.0006 +0.0003 +0.0001 0.0000 +0.0002 +0.0001 +0.0003
0.0026 +0.0016 +0.0013 +0.0002 +0.0009 +0.0010 +0.0012 +0.0016

0.0001 -0.0010 -0.0002 -0.0015 -0.0008 -0.0007 -0.0021 -0.0005
0.0025 -0.0014 -0.0034 -0.0031 -0.0047 -0.0046 -0.0031 -0.0020

0.0001 -0.0077 -0.0070 -0.0062 -0.0014 -0.0053 -0.0076 +0.0019
0.0038 -0.0029 -0.0136 -0.0121 -0.0196 -0.0116 -0.0096 -0.0040

0.0020 +0.0020 +0.0065 -0.0195 ------- +0.0121 ------- +0.0111

for DS Psum
0.0038 0.0027 0.0027 0.0030 0.0028 0.0028 0.0043 0.0039
0.0066 0.0064 0.0058 0.0064 0.0056 0.0049 0.0063 0.0058
0.0098 0.0099 0.0074 0.0077 0.0100 0.0083 0.0086 0.0074
0.0129 0.0127 0.0109 0.0102 0.0109 0.0138 0.0102 0.0101
0.0155 0.0185 0.0136 0.0132 0.0130 0.0164 0.0180 0.0106
0.0185 0.0148 0.0201 0.0291 0.0207 0.0145 0.0108 0.0105
0.0259 0.0173 0.0110 0.0195 ------ 0.0209 ------ 0.0111
for DL sum
0.0000 0.0000 +0.0002 -0.0001 +0.0007 +0.0007 +0.0004 +0.0007 +0.0008 +0.0009 +0.0010 +0.0006 -0.0007 -0.0016

- - - - +0.0006 +0.0015 +0.0015 +0.0010 +0.0008 +0.0018 +0.0010 +0.0015 +0.0012 +0.0031 +0.0011 +0.0017 -------
        
        -0.0038 +0.0019 -0.0002 -0.0004 -0.0016 -0.0021 -0.0007 -0.0015 -0.0011 -0.0003 -0.0022 ------- -------
        
        -0.0046 +0.0006 -0.0003 -0.0043 -0.0055 -0.0020 -0.0054 -0.0023 -0.0070 -0.0078 ------- ------- -------
        
        -0.0080 -0.0017 -0.0029 -0.0058 -0.0069 -0.0055 -0.0050 -0.0043 -0.0122 ------- ------- ------- -------
        
        -0.0057 -0.0158 +0.0022 -0.0110 -0.0085 -0.0131 -0.0064 -0.0144 -0.0015 ------- ------- ------- -------
        
        +0.0036 -0.0009 +0.0127 -0.0031 ------- +0.0076 ------- ------- ------- ------- ------- ------- -------

for DL Psum
0.0000 0.0050 0.0032 0.0037 0.0032 0.0027 0.0029 0.0029 0.0031 0.0029 0.0038 0.0026 0.0028 0.0033

- - - - 0.0080 0.0071 0.0063 0.0050 0.0058 0.0051 0.0053 0.0056 0.0064 0.0049 0.0053 0.0029 ------
        
        0.0119 0.0093 0.0086 0.0082 0.0083 0.0088 0.0062 0.0066 0.0093 0.0069 0.0055 ------ ------
        
        0.0146 0.0108 0.0119 0.0134 0.0116 0.0095 0.0099 0.0097 0.0098 0.0118 ------ ------ ------
        
        0.0178 0.0170 0.0160 0.0145 0.0106 0.0150 0.0109 0.0056 0.0133 ------ ------ ------ ------
        
        0.0197 0.0310 0.0141 0.0193 0.0161 0.0198 0.0067 0.0144 0.0015 ------ ------ ------ ------
        
        0.0118 0.0258 0.0152 0.0300 ------ 0.0076 ------ ------ ------ ------ ------ ------ ------

for LS sum
0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000

0.0016 -0.0007 -0.0008 -0.0001 -0.0027 -0.0016 -0.0015 +0.0008

0.0001 -0.0008 +0.0004 -0.0001 +0.0014 +0.0016 +0.0014 +0.0021
0.0001 +0.0006 +0.0014 -0.0001 -0.0008 -0.0002 -0.0003 +0.0021
0.0007 -0.0009 -0.0004 -0.0005 +0.0004 +0.0004 +0.0005 -0.0003

0.0000 +0.0002 -0.0016 -0.0015 -0.0003 -0.0009 -0.0005 +0.0002

0.0024 +0.0014 +0.0002 -0.0019 +0.0001 -0.0003 -0.0003 -0.0005
0.0028 +0.0006 -0.0003 -0.0006 -0.0012 +0.0002 -0.0008 +0.0004
0.0036 +0.0020 +0.0005 -0.0003 -0.0002 -0.0008 -0.0013 -0.0001
0.0022 +0.0013 +0.0014 +0.0001 -0.0008 -0.0001 -0.0010 -0.0006
0.0044 +0.0027 +0.0017 +0.0004 +0.0003 +0.0007 -0.0005 +0.0000
0.0051 +0.0007 +0.0005 -0.0001 +0.0010 0.0000 -0.0004 -0.0014
0.0010 +0.0003 +0.0002 -0.0009 +0.0007 -0.0018 -0.0015 -0.0011
0.0076 -0.0015 -0.0015 -0.0033 -0.0024 -0.0025 -0.0029 -0.0026

for LS Psum
0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000
0.0091 0.0104 0.0058 0.0073 0.0106 0.0087 0.0093 0.0094
0.0090 0.0099 0.0090 0.0089 0.0071 0.0067 0.0068 0.0071
0.0063 0.0072 0.0073 0.0067 0.0080 0.0059 0.0104 0.0076
0.0089 0.0077 0.0069 0.0060 0.0057 0.0083 0.0052 0.0064
0.0075 0.0052 0.0066 0.0062 0.0061 0.0078 0.0071 0.0049
0.0072 0.0065 0.0053 0.0078 0.0046 0.0066 0.0057 0.0045
0.0055 0.0054 0.0050 0.0049 0.0052 0.0044 0.0056 0.0040
0.0069 0.0050 0.0047 0.0046 0.0049 0.0052 0.0040 0.0040
0.0082 0.0047 0.0038 0.0078 0.0047 0.0040 0.0047 0.0041
0.0063 0.0054 0.0026 0.0047 0.0018 0.0026 0.0050 0.0046
0.0059 0.0033 0.0023 0.0029 0.0024 0.0023 0.0045 0.0026
0.0049 0.0009 0.0034 0.0011 0.0021 0.0019 0.0028 0.0024
0.0076 0.0015 0.0023 0.0037 0.0024 0.0025 0.0030 0.0026
for LR sum
0.0000 0.0000

0.0007 -0.0022

0.0001 +0.0012
0.0002 +0.0008
0.0005 +0.0003
0.0005 -0.0005

0.0002 +0.0002

0.0001 +0.0005

0.0006 +0.0005
0.0003 +0.0006
0.0012 +0.0013
0.0006 +0.0005

0.0005 +0.0004
0.0014 -0.0036

for LR Psum
0.0000 0.0000
0.0050 0.0110
0.0073 0.0088
0.0056 0.0085
0.0058 0.0080
0.0057 0.0071
0.0051 0.0069
0.0043 0.0057
0.0044 0.0057
0.0054 0.0058
0.0038 0.0055
0.0033 0.0036
0.0029 0.0021
0.0033 0.0038

こいつでやり直して提出。13点くらいしか増えず。あれー？
なんか実は普通にやった方が良いのかなぁ、ということで、最小自乗法を使って重回帰分析



Residual standard error: 0.006834 on 8729 degrees of freedom

Multiple R-squared: 0.7326,     Adjusted R-squared: 0.7324 

F-statistic:  3986 on 6 and 8729 DF,  p-value: < 2.2e-16

まぁ適当にやるとゴミだよね。
さっき適当に作った関数を埋め込んでもっかい。



Residual standard error: 0.006641 on 8727 degrees of freedom

Multiple R-squared: 0.7476,     Adjusted R-squared: 0.7473 

F-statistic:  3230 on 8 and 8727 DF,  p-value: < 2.2e-16

0.006641。むむむ。あんまり変わっていない。
S^2を入れてなかったので入れてあげる



Residual standard error: 0.006614 on 8726 degrees of freedom

Multiple R-squared: 0.7496,     Adjusted R-squared: 0.7493 

F-statistic:  2903 on 9 and 8726 DF,  p-value: < 2.2e-16

んー、もうちょい寄って欲しいなぁ。
多変量解析スキルが全然足りない。
途中に出てくるdecoって変数、素材とかその他もろもろに対しての、得点の比率が、平均からどの程度離れてるかを足していたのだけど、なぜか二乗和でなく、絶対値の和でやっていた。二乗和に平均して取り直し
- 取り直してるけど微妙な気がするなぁ・・・・なんでだろ・・・ｗ

6/12(13日目)

そろそろ奥の手使うよー！

Aで保存する解を３つに。
1秒ずつぶん回す
一番良い奴を最後に1秒ぶん回す
多分これでも間に合うと思うのだけど、もしかしたらSが大きいケースで弱いかも。
そんなこともなかった
1. 7くらい。まぁ満足。TLEなければ死なないと思うし、9.3sならまぁ平気でしょう
- 一番重たい処理がDのO(2^n * n)だけど、2000ケース回して最高のnが19だし、実は100000ごとにbreak箇所作ってるしで、まぁ安全過ぎる

6/13(最終日)

これは大丈夫ーって安心していたら、wataたんが現れた。死ぬ

スコアチェック　残り１２時間

chokudai 9970.71 1 06.12.2012 14:12:57 C# 21 11
wata 9964.57 2 06.12.2012 14:48:11 Java 8 5
ainu7 9956.83 3 06.12.2012 14:08:41 C++ 56 26
venco 9908.01 4 06.11.2012 16:26:54 C++ 11 10
Milanin 9903.33 5 06.12.2012 12:53:51 C++ 51 19

うん、なにこれこわい。やばい。
速度が足りてないのでC++に書き換えはワンチャン
- んー、wataたんに抜かれても、２位か３位で終えられれば十分だし、リスク取ることないかな。C++だとデバッグしづらいし、異常終了0でちゃんと組める自信があんまりない。
慌てて３つの解→５つの解に→悪化→ふぇぇΣ
つーか0.01%まで考えないとダメなら、今の適当Eは辞めないとあかん・・・
- そこらの厳密性上げるだけでどうにかなったりしないかな？　しない？しないよね・・・みょーん
- まぁでも、とりあえず全コピーとか適当な処理してる部分を修正するだけでかなり良さそうなので、ちょこちょこと修正
- とりあえず、変更点をDictionaryでメモして、ある程度大きくなったら反映、みたいな感じに。これで差分しか変更をメモらなくて良くて、更新が多い時にかなり早くなるはず？
- やっぱE早くしてもあんまり意味ない・・・ｗ　というかDがもしかしたらこれボトルネック的になってるのかな。
Dをちょっと考えよう。
累積和から色々やったらもうちょっと早いのでは。
2^Nのケースに対してS*S*N回もやれば
- いやいやいやその時点で遅い
- なんか適当に見積もって最後の微修正だけそんな感じで出来ないかなー
- 今やるのは危ない気がする。やめた
残りが0の時に一気に変化してふぇぇ！ってなるのを修正
スコアチェック　残り４時間

wata 9981.98 1 06.13.2012 06:31:16 Java 8 7
ainu7 9954.46 2 06.13.2012 08:27:15 C++ 72 32
chokudai 9949.63 3 06.13.2012 08:22:35 C# 31 18
Mojito1 9896.83 4 06.13.2012 07:01:48 C# 34 26
Milanin 9893.52 5 06.13.2012 07:02:58 C++ 54 22

う、うん・・・。
ainuさんにも抜かれるかー。
んー、敗因があるとすれば3つ程。
- 分配候補の列挙方法が良くない(Aたんが弱い。
  - とりあえず、一定スコアになるように埋めていく方法とかも試したんだけど、思いつく限りでは一番良かったんだけどねー
- スコアの簡易予測が良くない(Bたんが弱い。
  - 思いつく要素は入れたし、しゃーないんじゃないかなぁ
- 人を決めた後のケーキの切り方が弱い(Eたんが弱い
  - 弱いとは思うのだけど、影響は小さいんじゃないかなぁ。頑張ってもainuさんとの点差分くらいだと思うのだけど。
んー、わからん。ローカル相対で99.7くらいなので、AたんBたん程々に弱いのだけど、ちょっと9981は遠い。
とりあえず終わり！

　
ということで、この時点で３位とかでした。いつも通り最終日に抜かれちゃいましたが、多分TCO Finalには行けるでしょう。
参加者の皆様、お疲れ様でした！

*1:iさんが食べたkの量) * (iさんがkをどれだけ好きか

chokudaiのブログ

chokudai（高橋直大）のブログです