Skip to content

Instantly share code, notes, and snippets.

@yowa
Created Nov 30, 2017
Embed
What would you like to do?
-*- mode:my-memo; coding:utf-8 -*-
Hokkaido Univ.& Hitachi 1st New-concept Computing Contest 2017 の
参加中メモ。上が一番新しいので、下から読んでね
------------------------------------------------------------
[2017-11-28 23:40:35]
最終submitで
- 現状維持(s026)
- 差し戻す(s025)
- 新しいやつ(s026 を改善した?でもローカルで s026 に 0.012% 負けてる)
ローカルですべてほぼ同じスコアなので、
ローカルと鯖の環境違いが効いてる可能性を考えると、
鯖で高得点の s025 に差し戻すのが正解っぽいなあ
------------------------------------------------------------
[2017-11-28 23:35:56]
[s026] (gaiko.cpp rev1.1)
uniform をやらない感じ
s025 s026
#150 4970.68 < 4970.89 (+0.213 / +0.004%)
">"(66) "="(15) "<"(69)
163399 (-175)
たぶんガシャ運の範囲だよなあ
------------------------------------------------------------
[2017-11-28 20:09:59]
[s025] (fina.cpp rev1.8)
この伸びは submit ガシャ運っぽい
163574 (+ 493)
------------------------------------------------------------
[2017-11-28 20:07:11]
gettimeofday() は重い?
コードテストで試してみよう (test_gettimeofday.cpp rev1.1)
10000回呼んで 3~4ms だった。
気にすることではないのう
------------------------------------------------------------
[2017-11-28 20:01:23]
(fina.cpp rev1.8)
- sa_t(10.0, 0.1) -> sa_t(3.0, 0.5)
------------------------------------------------------------
[2017-11-28 15:50:43]
[s024] (fina.cpp rev1.1)
なんだかんだでうまく行ってないので、s023 をそのまま 9.0sec -> 9.8sec に。
163081 (+114)
------------------------------------------------------------
[2017-11-28 01:49:47]
sa.accept(0) が常に true なのマズくね?
- enumerate すると、全部反転して戻ってくる感じになるやん
独立だとすると 1/2 で accept か?
芳しくない
------------------------------------------------------------
[2017-11-28 01:48:35]
edge とか関係なく、隣接マスswap はやるべきなのでは?
sparse でノードを端に詰めたりみたいな
-> すでに隣接してる状態の pivot が隣接マスswapの役目を果たしてる的な
------------------------------------------------------------
[2017-11-28 01:04:50]
expってどのくらい重いのん?(test_exp.cpp)
------------------------------------------------------------
[2017-11-27 21:17:32]
偏りがあるから sparse なヤツだと 8*V に特定の頂点の edge が
ゼロってありうるかもだ?
さすがになかった
------------------------------------------------------------
[2017-11-26 22:17:07]
next_cell[].size() は 3, 5, 8 がありえるけど、
rng.get(5) はロスい。
ところで uniform_int_distribution だと 3, 5, 8 に時間差ないっぽいけど
どう実装されてるん?
あー別に 5/8 で accept じゃなくて、
たとえば 255/256 で accept した後に 51 で割ればいいのか
next_cell[].size() はほぼほぼ 8 で、
4/W くらいの確率で 5 だから(中央によるからもっと低い)
特別に何かするほどのことでは無いだよ
------------------------------------------------------------
[2017-11-26 22:15:48]
(edge.cpp rev1.9)
ランダムで edge を swap するんじゃなくて、swap したやつも
候補に突っ込んどいて shuffle しとく
速度は大差なし。デメリットがあるはずなのでやめとく
------------------------------------------------------------
[2017-11-26 21:18:42]
(edge.cpp rev1.8)
es を vector<edge_t> から vector<pair<int16_t,int16_t>> にして、iter +1%くらい
------------------------------------------------------------
[2017-11-26 18:38:53]
[s023] (edge.cpp rev1.6)
密なとき(E > 0.3*Ec)は、W を大きめに
#150 4956.47 < 4962.81 (+6.340 / +0.128%)
">"(54) "="(16) "<"(80)
162967 (+95 / +0.058%)
------------------------------------------------------------
[2017-11-26 11:30:20]
[s022] (edge.cpp rev1.4)
#150 4950.20 < 4956.47 (+6.267 / +0.126%)
">"(56) "="(18) "<"(76)
162872 (+346 / +0.212%)
------------------------------------------------------------
[2017-11-26 10:17:29]
0.1*Ec というのがてきとーすぎる。
Vに対して定数倍、というのはありえる
(edge.cpp rev1.4)
8*V でやってみる
------------------------------------------------------------
[2017-11-26 00:24:54]
[s021] (edge.cpp rev1.3)
162526 (+859)
------------------------------------------------------------
[2017-11-26 00:16:30]
(edge.cpp rev1.3)
dense なグラフも(スコアの低い)辺を減らして、エッジベースで回すか。
とりあえずmax(100, 0.1*Ec) まで選ぶ
Ec は完全グラフの辺数 = V*(V-1)/2 な。
s020 edge r1.3
#150 4919.83 < 4950.20 (+30.367 / +0.613%)
">"(37) "="(13) "<"(100)
伸びすぎてヘンな声が出た
何かおかしいのでは?
あ、あと uniform を 0.1 で打ち切ってる
------------------------------------------------------------
[2017-11-25 23:18:32]
[s020] (edge.cpp rev1.2)
edge ベースを実装した。
s019 s020
#150 4922.13 > 4919.83 (-2.293 / -0.047%)
">"(71) "="(14) "<"(65)
まあ伸びてない(むしろ落ちてる)けど投げるだけなげる
161667 (+131)
謎うpだけど、誤差だよ誤差
------------------------------------------------------------
[2017-11-25 00:22:22]
序盤に、距離dだとスコア +w/d みたいな、なんらかの拡張問題としてやる?
近くにあるとなんとかなるかもじゃん?
------------------------------------------------------------
[2017-11-25 00:22:05]
SA のパラメータいじりは闇なので保留
------------------------------------------------------------
[2017-11-24 12:53:28]
[s019] (climb.cpp rev1.7)
s017 s019
#150 4892.93 < 4922.13 (+29.193 / +0.593%)
">"(38) "="(12) "<"(100)
5th 161536 (+856 / +0.530%)
ほぼ予想通りだのう
------------------------------------------------------------
[2017-11-24 06:22:00]
s017-s018 のいいとこどりで 161739。
sparse が s017、それ以外がs018 だと 161636。
dense_factor が 0.05 あたりで sa(10.0,1.0) と sa(5.0,2.0) を切り替え?
(climb.climb rev1.7)
------------------------------------------------------------
[2017-11-24 05:28:38]
[s018] (climb.cpp rev1.6)
10xx 5403.41 < 5443.70 (+40.290 / +0.740%)
">"(29) "="(9) "<"(62)
ローカルではすごい伸びた!と思ったら、
160595 (-85)
ケース別で見ると、sparse で悪化してるのう。
20xx 3116.95 > 3035.01 (-81.940 / -2.629%)
">"(83) "="(7) "<"(10)
たしかに sparse でガタ落ちしてる
いい加減、テストケースに sparse も入れようぜ
本番は
random 50
complete 60
sparse 40
の計150ケースっぽい。
------------------------------------------------------------
[2017-11-24 05:28:01]
(climb.cpp rev1.6)
pivot も sa(5.0, 2.0) にした
これ前やって、鯖ではアカンやったやつな気もする…
とりあえず投げるか
------------------------------------------------------------
[2017-11-24 03:50:23]
(climb.cpp rev1.3, 1.4)
next_node や next_cell を選択するのも rand じゃなくて
enumerate にしてみた
けど、(多分)互いに素制約が満たせないのでスコアはダメですわ。
rev 1.2 に revert する。
------------------------------------------------------------
[2017-11-24 03:49:33]
ちょっとclimbを切り分ける
(climb.cpp)
(climb.cpp rev1.2)
uniform を sa(5.0, 2.0) にする
------------------------------------------------------------
[2017-11-23 23:19:57]
dense な方が、局所スコア大きくなるから、初期温度高くないといけない?
------------------------------------------------------------
[2017-11-23 22:16:01]
部分グラフをまとめて移動できたらいいのにねえ
------------------------------------------------------------
[2017-11-23 16:31:48]
あー重さ0の辺が存在するから、pivot のときは除外した方がいいはず
------------------------------------------------------------
[2017-11-23 14:30:43]
アイデア
- 3点 swap
- 盤面の一部分をシフトする
------------------------------------------------------------
[2017-11-23 07:12:37]
[s017] (pivot.cpp rev1.11)
- sa(10.0, 0.5) -> sa(10.0, 1.0)
------------------------------------------------------------
[2017-11-23 06:43:35]
(table_result.rb)
result-* を比較してみた
sparse 以外は s014 がいいっぽい。
sa(10.0, 1.0) だな?
投げてみるか。
------------------------------------------------------------
[2017-11-23 06:15:57]
[s016] (pivot.cpp rev1.10)
- e/e_c > 0.5 なら SA_uniform() 旧来
- e/e_c < 0.5 なら、progress < 0.6 なら uniform、超えたら pivot。
14th: 159927 (+341)
------------------------------------------------------------
[2017-11-23 05:18:24]
e/v**2 が低いと pivot 有利なはず
(th.rb)
比較して e/v**2 でソートして th より上か下かで切り替えるやーつ
0.25 より小さいなら pivot、かなあ
あー気持ち的には complete graph の E = v*(v-1)/2 との比率にしたいかも?
となると e/e_c < 0.5 かなあ
------------------------------------------------------------
[2017-11-23 03:59:26]
(pivot.cpp rev1.3)
> a = rng.get(V)+1
じゃなくて
> a = (same as uniform)
したらスコア上がるんですけどー
一様性なのか局所性なのか。確かめる?
いや、一様性だろ。a -> a+1 には局所性は無い
------------------------------------------------------------
[2017-11-23 03:30:04]
なんか pivot うまくいってない感じ (sparse なケースで s015 よりだいぶ落ちる)
sparse に特化したはずなのに sparse だと 2% 落ちるの問題外って感じでは
s015 pivot r1.2
10xx 5375.06 > 5359.61 (-15.450 / -0.287%)
">"(53) "="(11) "<"(36)
s015 pivot r1.2
20xx 3074.57 > 3018.50 (-56.070 / -1.824%)
">"(80) "="(5) "<"(15)
------------------------------------------------------------
[2017-11-23 03:29:47]
seed: 2004
V: 295
E: 294
(double)E/V: 0.99661
------------------------------------------------------------
[2017-11-23 02:24:25]
(pivot.cpp)
↓ これやる
------------------------------------------------------------
[2017-11-23 00:31:23]
sparse なヤツ、大抵のswap が無効なので
エッジのあるやつでしかやらないとか?
cell r (node c) を選ぶ
c と辺のある a (node p) と
r に隣接してる q (node b) を swap、みたいな?
------------------------------------------------------------
[2017-11-22 23:41:14]
s013 と比べて 1.5倍くらい回ってる
SA のパラメータ変えたときの挙動が全然思った風じゃないので
単純速度UP以外に、何をチューニングすべきかわっかんねー
------------------------------------------------------------
[2017-11-22 23:05:18]
generator に E を V*4以下、次数を8以下に抑えるオプションつけて生成
(testcase/tc-20xx.txt)
[log-uniform-r1.2-20xx.txt]
Error: "phi" must be injective function
seed:2079 -> 0
再実行したけどエラーじゃない。再現性はないのう
解が単射じゃないということ。
出力時に a は 1~V を舐めてるので uniq。
よって
- fo[a] がかぶってる or
- fo[a] の分解→結合でかぶる
のどっちか。
あー seed: 2079 で
> lq*INNER_ITER: 100860000
> cur_score: 586
> best_score: 611
> assign.score(): 611
> == hill climbing
> cur_score: 617
> best_score: 617
> assign.score(): 618
hill climbing の後の score() が計算違ってる。これか?
無理やり hill climbing するように sa をでかくして走らす
あー Error: "phi" must be だ
あー for(a) for(j) を、for(j) for(a) をひっくり返したんだから
p = q じゃなくて q = p だ。
------------------------------------------------------------
[2017-11-22 22:32:31]
[s014] (uniform.cpp rev1.2)
WA もらってるんですけどー。
sparse_05 0 / 1000000 C026_scrambled
sparse_06 0 / 1000000 C027_scrambled
------------------------------------------------------------
[2017-11-22 21:46:50]
(uniform.cpp rev1.1)
a, q を 乱数じゃなくて enumerate してみたよー
- V == V_emb のとき 互いに素じゃないからアレ
------------------------------------------------------------
[2017-11-22 19:22:00]
[s013] (quiet.cpp rev1.10)
- q の範囲を a から距離1以内に制限
s012 s013
#100 5354.82 < 5358.55 (+3.730 / +0.070%)
">"(54) "="(8) "<"(38)
s010 s013
#100 5347.91 < 5358.55 (+10.640 / +0.199%)
">"(38) "="(7) "<"(55)
14th 159310
------------------------------------------------------------
[2017-11-22 16:23:28]
- int q = rng.get(W*W)*(W+1)/W + W+2;
+ int q = pre_computed[rng.get(W*W)];
にするだけで、2割くらい速くなったんだけどマジか…
------------------------------------------------------------
[2017-11-22 15:35:57]
- 評価値の出現回数で遷移するやつ
------------------------------------------------------------
[2017-11-21 23:48:49]
[s012]
- sa(10.0, 2.0)
- 山登
------------------------------------------------------------
[2017-11-21 23:46:52]
アイデア
- ws[] (コストテーブル)を半分に
- W を一回り大きく取る
------------------------------------------------------------
[2017-11-21 17:55:48]
[s011] (guessiter.cpp rev1.2)
鯖で何回くらい回ってるのか知るために、
score が lq/2 になるように寄せてみる
------------------------------------------------------------
[2017-11-21 04:20:41]
[s010] (quiet.cpp rev1.1)
s008 の log 出力とかを削ったバージョン
12th 159057 (+600)
------------------------------------------------------------
[2017-11-20 23:18:20]
(smemo.cpp rev1.10)
too_bad は実装できたはず
どこから too_bad 使うのに切り替えるかがねぇ。
s008 smemo rev1.10
#100 5335.49 < 5342.79 (+7.300 / +0.137%)
">"(45) "="(8) "<"(47)
s009 smemo rev1.10
#100 5351.54 > 5342.79 (-8.750 / -0.164%)
">"(56) "="(7) "<"(37)
------------------------------------------------------------
[2017-11-20 15:51:51]
swap評価値の受理確率が eps を下回ったらメモ
それは選択しない、
swap 起きたらメモクリア、みたいな?
発展的には、
vector と set で二重に持っておいて、
vector.sample() で選ぶ感じ?
------------------------------------------------------------
[2017-11-20 15:51:23]
いまの SA-mod のやり方はいったん保留
------------------------------------------------------------
[2017-11-20 15:08:54]
smemo.cpp rev1.8 seed:1098 で落ちる
sc_memo[] の範囲外代入が原因っぽい。
なんで範囲外に?
> for (int j=0; j<=W*W; j++)
jをW*W まで(inclusive)回してたのが原因。
------------------------------------------------------------
[2017-11-19 23:29:37]
(smemo.cpp rev1.8)
SA-mod に着手
------------------------------------------------------------
[2017-11-19 17:31:58]
[s009] (smemo.cpp rev1.6)
s008 s009
#100 5335.49 < 5351.54 (+16.050 / +0.300%)
">"(39) "="(5) "<"(56)
(13th 158457)
158396
うーん、スコア落ちたのう。
鯖とはiteration が違うからにゃんとも言えないんだよなあ
------------------------------------------------------------
[2017-11-19 17:20:24]
(smemo.cpp rev1.6)
- 焼きなましを冷やしすぎない
-- sa_t(10.0, 0.5) -> sa_t(10.0, 1.0)
-- 最後に山登り
安定しない感じだなあ…
でも s008 よりは上なはずなので投げるか
------------------------------------------------------------
[2017-11-18 02:39:13]
[s008] (smemo.cpp rev1.3)
- ローカル用の画像出力のコードのっけてるけどー
- まあ rev1.2 と同じということにして log もそれ保存しとく
s007 s008
#100 5322.44 < 5335.49 (+13.050 / +0.245%)
">"(37) "="(7) "<"(56)
------------------------------------------------------------
[2017-11-18 02:36:55]
(smemo.cpp rev1.2)
空白にも置くように。
かなりムダがあるけどどうか
いちおープラス。
s007
#100 5322.44 < 5335.49 (+13.050 / +0.245%)
">"(37) "="(7) "<"(56)
rev1.1
#100 5327.18 < 5335.49 (+8.310 / +0.156%)
">"(37) "="(7) "<"(56)
------------------------------------------------------------
[2017-11-17 17:52:49]
(smemo.cpp rev1.1)
グラフの変形にそなえて、 memo_sc を a じゃなく p で記憶
局所性があがる恩恵がある?
------------------------------------------------------------
[2017-11-17 15:01:07]
[s007] (assign.cpp rev1.10)
6th 158274
------------------------------------------------------------
[2017-11-17 14:58:32]
[assign.cpp rev1.10]
- SA は int なので、accept 確率はテーブルを引くように
- xor128_t (64x2) の実戦投入
(s006) (assign.cpp rev1.10)
#100 5285.66 < 5322.44 (+36.780 / +0.691%)
">"(31) "="(6) "<"(63)
------------------------------------------------------------
[2017-11-17 13:49:07]
- 形決め打ちなのを何とかする?
- 時刻における遷移確率を見てみる
------------------------------------------------------------
[2017-11-17 02:34:36]
仮に10倍速くなったら何が起きる?というのを知るために
TIME_LIMIT を 10倍にして走らせてみる
#100 5307.83 < 5434.75 (+126.920 / +2.335%)
">"(3) "="(7) "<"(90)
うーむ、これで16.1万相当だから、このレベルのスコア上昇が必要か
------------------------------------------------------------
[2017-11-17 02:33:07]
(assign.cpp rev1.9)
キャッシュを意識してデータ型をint8_t とかに
s006 -> assign.cpp rev1.9
rev1.8 よりちょい速いけど、iteration数が少なかったとこほど伸びが大きい
------------------------------------------------------------
[2017-11-16 23:39:53]
局所スコアをメモるか。
(assign.cpp rev1.8)
s006 -> assign.cpp rev1.8
iteration が 1.1~1.3倍ってとこかなあ
------------------------------------------------------------
[2017-11-16 23:39:02]
SAパラメータいじりとかしてる
してる場合じゃないよ
とりあえず
(2.0, 2.5)
(2.0, 0.5)
(100.0, 0.05)
(10.0, 0.5) <- これ
------------------------------------------------------------
[2017-11-16 16:11:32]
[s006] (assign.cpp rev1.3)
s005 s006
#100 5034.71 < 5285.66 (+250.950 / +4.748%)
">"(3) "="(7) "<"(90)
3rd 157372
------------------------------------------------------------
[2017-11-16 15:57:38]
[assign.cpp rev1.3]
- V = 1 のとき出力おかしかったので修正
-- E = 0 だから initial_assignment() で初期値が 0 になってた
- ログが大量すぎるから出力量を減らす
-- lq%100 == 0 のときだけ
-- [FIXME] というか鯖では出力抑制すべきでは
------------------------------------------------------------
[2017-11-16 15:40:27]
[assign.cpp]
- assign_t: 順方向(fo), 逆方向(ba) を vector にした
-- 入力の Gemb じゃなくて、必要最小限サイズの King's Graph で持つ
--- 出力時はノード番号の変換が必要なので注意!
-- 番兵に空白行・列を入れることで、隣接ノードをノード番号で直指定できるように
s005 vs (assign.cpp rev1.2)
あんま iteration かわらん、と思ったら1桁違ってた
#100 5034.71 < 5285.87 (+251.160 / +4.752%)
">"(1) "="(7) "<"(92)
------------------------------------------------------------
[2017-11-16 00:03:49]
[s004] (simple.cpp rev1.16)
- 隣接辺を特別扱いしない
- sa_t(10.0, 0.1) -> sa_t(10.0, 0.5)
24th 150708
------------------------------------------------------------
[2017-11-15 23:48:19]
隣接ノードのswapはノードごとにスコア計算すると
同じ辺を2回カウントするからダメ、みたいに思い込んでたけど、
同じ辺だとswap前後での差分は0なんだから、2回カウントしても無問題だった。
------------------------------------------------------------
[2017-11-15 18:24:45]
[s003] (simple.cpp rev 1.14)
- SA
- 出力logを簡素化
18th 146273
------------------------------------------------------------
[2017-11-15 14:47:57]
SAにする。
差分スコアを持っておく。
絶対遷移するSA。
------------------------------------------------------------
[2017-11-15 14:44:32]
[s003] (simple.cpp rev1.8)
swap で山登り。swapした8近傍だけのスコアで差分計算
21st 135231
------------------------------------------------------------
[2017-11-15 03:18:36]
King's Graph で最密な(頂点数について最も辺の多い)選択って?
ちょっと舐める(dense_king.rb)
八角形?
------------------------------------------------------------
[2017-11-15 02:21:37]
(simple.cpp rev1.2)
seed: 1097 が out of range (output)
V と V_emb が近いせいで wrap すると K*K を超えちゃってた。
wrap を sqrt(V) じゃなくて ceil(sqrt(V)) にするよ
------------------------------------------------------------
[2017-11-15 02:17:03]
(simple.cpp rev1.1)
seed: 1031 で SEGV
おー、seed: 1031 は V=1, E=0 だ。
コーナーケース引くとかやるじゃん
------------------------------------------------------------
[2017-11-15 02:08:48]
[s001] (simple.cpp rev1.1)
いくつかのケースでエラーがでるけど、あえて投げて挙動を見てみるか
WA があるけど順位表に乗るな。WAは単に0スコアとして扱われるもよう。
各テストケースのスコアが見れるのな
[提出一覧]→[自分の提出]→[詳細]
result-sXXX.txt にコピペしとこう
------------------------------------------------------------
[2017-11-15 02:04:21]
upper bound を考える。
G_emb は高々degree:8 なので、
G の各頂点について高々8個しか辺を充足できない
ので高い方から8個が upper bound。
全頂点について↑を足した上で(二度数えてるから)2で割ると、全体の upper bound
------------------------------------------------------------
[2017-11-15 01:10:00]
辺に重みの付いた頂点を、
既知の定形グラフの頂点に対応付けて、
対応先でも辺があるような辺の重みの和、を最大化。
これ相対スコアじゃないから、最大ケースで高スコアとればいいって話だよね?
うーん。
ランダムグラフの最大スコアは MAX_E*MAX_C で抑えられる
と思ったら、MAX_E は 20000 で
ランダムグラフは |V| <= 500 だけど
完全グラフは |V| <= 200 ( |E| <= 200*199/2 = 19900 ) だから
まあそんな感じか
------------------------------------------------------------
[2017-11-15 00:23:17]
readme が Markdown で読みにくい(こなみ)。
フォーマッタとか探してたけど手頃なのがわからんから諦める
------------------------------------------------------------
[2017-11-15 00:22:38]
グラフの実用(用途のある)問題らしいけど、マラソン的に面白い問題なことを祈る
chokudai さんを信じよう
------------------------------------------------------------
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment