Created
November 30, 2017 14:53
-
-
Save yowa/45bf597e0449804220dc7745d8ccbe0b to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
-*- 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