2018 TCO MM : Poland Lightning Round
はじめての TCO
問題ページはここ
provisional 34th
錚々たるメンツの中でまあまあ良い順位が取れたので個人的には満足している
以下考察メモをそのまま貼り付けたやつ
～～～～～～～～～～
# memo.txt
Submission 1
テスターを丸コピして投げる
Example scores:
0) 1600400.0
1) 1.29039964E8
2) 2.1410032E7
3) 1.6422789E8
4) 8303509.0
5) 2.0706226E7
6) 8.5416217E7
7) 8.0615315E7
8) 2.2705886E7
9) 3.5907544E7
Overall Score: 18874.59
---
ありえん低くて草
平面グラフの彩色問題？4色で塗れるかが勝負？
よく見たら飛び地があるので平面グラフではなさそう
k-彩色問題
まずは Welsh-Powell のアルゴリズムを試してみる
グラフはとりあえず隣接行列を作ってから隣接リストを作る（結構スパースになるので）
どうも 9 色以下で塗れるっぽいことが分かる
Welsh-Powell アルゴリズムで得られた彩色についてランダムに色 swap して最もピクセル変更の少ない配色を選択
---
Submission 2
Example scores:
0) 700256.0
1) 932516.0
2) 908087.0
3) 922682.0
4) 902743.0
5) 804928.0
6) 913211.0
7) 912540.0
8) 804549.0
9) 806034.0
Overall score: 604648.95(28)
---
pixel 変更数を一回 O(H * W) 掛けて求めるのはアホくさい
initial color を c とすると c は 2 ~ 5
s[i] : region[i] に存在するマスの総数
a[i][j] : region[i] に存在する色 j のマスの総数 (0 <= j < c)
とすれば
pixchanges[i][j] : region[i] の色を j に変えた時の pixel 変更数
は
pixchanges[i][j] = s[i] - a[i][j] (0 <= j < c)
s[i] (otherwise)
で求められる
これで O(nRegions) になった
さらに彩色に応じたグループ分けを行うことで O(nColors) まで抑えることができる
これで彩色数 10 や 11 の場合でも全通り順列を試して(彩色後における)最適解を時間内に求められるようになった．
あとは彩色問題をがんばればいい．
だいたい 9 色以下に収まるがまれに 10 色になることもある
11 色以上になるケースが存在するかは不明
---
http://siio.jp/pdf/grad/2007/2007grad39.pdf
ここに Welsh-Powell より少し良くなるらしいアルゴリズムがあるので使ってみる
二種類試していいほうを採用
---
Submission 3
Example scores:
0) 700250.0
1) 932516.0
2) 908087.0
3) 922682.0
4) 702708.0
5) 804796.0
6) 913078.0
7) 912257.0
8) 804549.0
9) 806034.0
Overall score: 565560.54(??) → 576700.86(54)
---
http://dopal.cs.uec.ac.jp/okamotoy/lect/2012/graphtheory/lect13.pdf
貪欲彩色
・貪欲彩色の出力は全順序 σ に依存する
・.うまく全順序を選べば，貪欲彩色の費やす色数が染色数になる
全順序の swap で山登りができる
example test で TLE したので rdtsc を使うようにした
---
Submission 4
Example scores:
0) 700250.0
1) 932516.0
2) 907722.0
3) 922682.0
4) 702449.0
5) 804650.0
6) 913078.0
7) 912257.0
8) 804366.0
9) 806034.0
Overall score: 574121.09(56) → 597751.76(47)
---
彩色数ばかり気にしていたが，スコア計算法からして
色変更数とのバランスを取るのが重要なのでは？？？（raw-score にばかり目が行っていた）
グループ分けし終わった後の色シャッフルでは不十分
Welsh-Powell の頂点彩色時に最もピクセル塗替えが少なくなるよう色選択
→ぜんぜん効果なし．彩色数が増えることもある
全頂点 shuffle ではコストが大きい 近傍 swap にできないか
現時点での彩色数より隣接する色が少ない頂点があれば，そのような頂点においては色変更が可能
色変更を山登りで適当に実装 スコアがどのくらい変わるか見てみる
---
Submission 5
Example scores:
0) 700250.0
1) 928086.0
2) 907328.0
3) 921740.0
4) 702463.0
5) 804443.0
6) 911928.0
7) 910854.0
8) 804104.0
9) 805818.0
Overall score: 589554.51(77?) → 632962.46(61)
---
やっぱ重要だったっぽい スコア計算方法からしてそれはそうという感じ
全 swap 貪欲彩色よりマシな結果を焼き鈍しで得たいが…
単一頂点の色 swap について
・焼き鈍しでもうちょいスコア改善
・Welsh-Powell で彩色したとき添字最大の色の頂点はかなり少ない(1 個とかの場合もある)ので
その近傍をゴチャゴチャ弄って色数を減らせる気がする
・newColors から oldColors への遷移に高スコアを与える
・maxColor からそれ以外への遷移は無条件で実行する
・maxColor への遷移は弾く
・oldColors 同士の swap は生のスコアで
とりあえず Example Test 投げる
---
example submission 8
0) 700305.0
1) 836838.0
2) 708562.0
3) 724101.0
4) 602966.0
5) 705101.0
6) 714445.0
7) 713528.0
8) 704828.0
9) 706696.0
---
彩色数がめちゃくちゃ良くなってる
ただ温度を超適当にセットしているためピクセル塗り替えのスコアはひどい
～～～
温度の正負を間違えるゴミをやっていた
直して順位爆上がりを期待して submit
---
Submission 6
Example scores:
0) 700250.0
1) 730895.0
2) 707983.0
3) 721895.0
4) 602802.0
5) 704641.0
6) 712723.0
7) 712099.0
8) 704418.0
9) 705936.0
Overall score: 636540.40(64) → 685763.47(50)
---
は？もうちょい行くと思ってたが 魔境か
なんかちょっとバグってたのを直す
焼き鈍し終了後にグループごとに色チェンジして最適求める悪足掻き処理を入れる
---
Submission 7
Overall score: 684862.90(54) → 690522.34(50)
---
全然上がらず
確率で添字最大の色にまれに遷移させるようにしたら
6 色彩色が 100 ケース中 4 → 27 ケースに向上
最初の 3 秒で彩色数を減らして残りの 7 秒で 色変更数を減らす
後半 7 秒の焼きなましをちゃんとやるとかなりスコアが上がるらしい
---
Submission 8
Example scores:
0) 700250.0
1) 725454.0
2) 706898.0
3) 719870.0
4) 602693.0
5) 703770.0
6) 710601.0
7) 709649.0
8) 604342.0
9) 705404.0
Overall score: 691273.22(57) → 811319.65(19)
---
順位バカ上がって草
前半 3 秒で時間切れになって取り逃してる 6 色ケースがまだある
・今は頂点数 V に依存する確率で最大色への遷移を許容しているがこれも焼くことでうまくいかないか
後半 7 秒に関しては単純に焼いてるだけ
・入力サイズに応じたパラメータ設定
・高速化をがんばる
bit で color の情報を保持して高速化 数百万イテレート増えた
seed 2, 8 で何故か焼きなましイテレート回数が減る キャッシュに乗らない？
→ TopCoder 上ではちゃんと増えてる
Example scores:
0) 700250.0
前半 3 秒 後半 7 秒
高速化前 25197239 41805152
高速化後 31885766 53613027
1) 725454.0
18128382 24775105
23703520 33095601
2) 706898.0
16068368 21130119
25325068 38423491
3) 719870.0
16068368 21130119
21191771 28131199
4) 602693.0
38043729 49443989
45233463 61674502
5) 703770.0
20434262 29448784
25625809 38181029
6) 710601.0
18904599 22975291
23723721 29973865
7) 709649.0
18895925 23667883
23530903 30459979
8) 604342.0
29833150 45324095
37450086 57622491
9) 705404.0
18390829 24876320
22999283 32945148
---
Submission 9
810998.04(22) → 815079.05(21)
---
結局 6 色彩色をより精度よくできるアルゴリズムは思い付かなかった．
焼きなましの冷却も微妙に間に合ってなさそう & 評価関数が微妙そうな感じがある．
トップとの差はその辺にありそうな気がするので感想戦に期待したい．
ソースコードは一応こんな感じ
#pragma once #include "bits/stdc++.h" #include <random> using namespace std; #define LOCAL class timer { vector<timer> timers; int n = 0; public: double limit = 9.85; double t = 0; timer() {} timer(int size) : timers(size) {} bool elapses() const { return time() - t > limit; } void measure() { t = time() - t; ++n; } void measure(char id) { timers[id].measure(); } void print() { if (n % 2) measure(); for (int i = 0; i < 128; ++i) { if (timers[i].n) cerr << (char)i << ' ' << timers[i].t << 's' << endl; } cerr << " " << t << 's' << endl; } static double time() { #ifdef LOCAL return __rdtsc() / 2.6e9; #else unsigned long long a, d; __asm__ volatile ("rdtsc" : "=a" (a), "=d" (d)); return (d << 32 | a) / 2.8e9; #endif } } timer(128); //呪文 #define DUMPOUT cerr #define dump(...) DUMPOUT<<" ";DUMPOUT<<#__VA_ARGS__<<" :["<<__LINE__<<":"<<__FUNCTION__<<"]"<<endl;DUMPOUT<<" ";dump_func(__VA_ARGS__) typedef unsigned uint; typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef pair<double, double> pdd; typedef pair<string, string> pss; template <typename _KTy, typename _Ty> ostream& operator << (ostream& ostr, const pair<_KTy, _Ty>& m) { ostr << "{" << m.first << ", " << m.second << "}"; return ostr; } template <typename _KTy, typename _Ty> ostream& operator << (ostream& ostr, const map<_KTy, _Ty>& m) { if (m.empty()) { ostr << "{ }"; return ostr; } ostr << "{" << *m.begin(); for (auto itr = ++m.begin(); itr != m.end(); itr++) { ostr << ", " << *itr; } ostr << "}"; return ostr; } template <typename _Ty> ostream& operator << (ostream& ostr, const vector<_Ty>& v) { if (v.empty()) { ostr << "{ }"; return ostr; } ostr << "{" << v.front(); for (auto itr = ++v.begin(); itr != v.end(); itr++) { ostr << ", " << *itr; } ostr << "}"; return ostr; } template <typename _Ty> ostream& operator << (ostream& ostr, const set<_Ty>& s) { if (s.empty()) { ostr << "{ }"; return ostr; } ostr << "{" << *(s.begin()); for (auto itr = ++s.begin(); itr != s.end(); itr++) { ostr << ", " << *itr; } ostr << "}"; return ostr; } template <typename _Ty> ostream& operator << (ostream& ostr, const stack<_Ty>& s) { if (s.empty()) { ostr << "{ }"; return ostr; } stack<_Ty> t(s); ostr << "{" << t.top(); t.pop(); while (!t.empty()) { ostr << ", " << t.top(); t.pop(); } ostr << "}"; return ostr; } template <typename _Ty> ostream& operator << (ostream& ostr, const list<_Ty>& l) { if (l.empty()) { ostr << "{ }"; return ostr; } ostr << "{" << l.front(); for (auto itr = ++l.begin(); itr != l.end(); ++itr) { ostr << ", " << *itr; } ostr << "}"; return ostr; } template <typename _KTy, typename _Ty> istream& operator >> (istream& istr, pair<_KTy, _Ty>& m) { istr >> m.first >> m.second; return istr; } template <typename _Ty> istream& operator >> (istream& istr, vector<_Ty>& v) { for (size_t i = 0; i < v.size(); i++) istr >> v[i]; return istr; } namespace aux { // print tuple template<typename Ty, unsigned N, unsigned L> struct tp { static void print(ostream& os, const Ty& v) { os << get<N>(v) << ", "; tp<Ty, N + 1, L>::print(os, v); } }; template<typename Ty, unsigned N> struct tp<Ty, N, N> { static void print(ostream& os, const Ty& value) { os << get<N>(value); } }; } template<typename... Tys> ostream& operator<<(ostream& os, const tuple<Tys...>& t) { os << "{"; aux::tp<tuple<Tys...>, 0, sizeof...(Tys)-1>::print(os, t); os << "}"; return os; } template<typename A, size_t N, typename T> inline void Fill(A(&array)[N], const T &val) { std::fill((T*)array, (T*)(array + N), val); } void dump_func() { DUMPOUT << endl; } template <class Head, class... Tail> void dump_func(Head&& head, Tail&&... tail) { DUMPOUT << head; if (sizeof...(Tail) == 0) { DUMPOUT << " "; } else { DUMPOUT << ", "; } dump_func(std::move(tail)...); } #define PI 3.14159265358979323846 #define EPS 1e-11 #define FOR(i,a,b) for(int i=(a);i<(b);++i) #define REP(i,n) FOR(i,0,n) #define all(x) (x).begin(), (x).end() #define SZ(x) ((int)(x).size()) #define fake false struct SXor128 { unsigned x, y, z, w; SXor128() { x = 123456789; y = 362436069; z = 521288629; w = 88675123; } SXor128(int _w) { x = 123456789; y = 362436069; z = 521288629; w = _w; } void setSeed() { x = 123456789; y = 362436069; z = 521288629; w = 88675123; } void setSeed(int _w) { x = 123456789; y = 362436069; z = 521288629; w = _w; } unsigned nextUInt() { unsigned t = (x ^ (x << 11)); x = y; y = z; z = w; return (w = (w ^ (w >> 19)) ^ (t ^ (t >> 8))); } unsigned nextUInt(unsigned mod) { unsigned t = (x ^ (x << 11)); x = y; y = z; z = w; w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)); return w % mod; } unsigned nextUInt(unsigned l, unsigned r) { unsigned t = (x ^ (x << 11)); x = y; y = z; z = w; w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)); return w % (r - l + 1) + l; } }; const int di[] = { 0, -1, 0, 1 }; const int dj[] = { 1, 0, -1, 0 }; class MapRecoloring { random_device seed_gen; mt19937 engine; SXor128 rnd; int H, W, N; int V, E; int nRegions; vector<int> regions; int nOldColors; vector<int> oldColors; vector<int> pixSum; vector<vector<int>> pixSumColor; vector<vector<int>> G; public: vector<int> graphColoring1() { vector<int> colors(nRegions, -1); vector<pii> deg(nRegions); for (int i = 0; i < nRegions; i++) deg[i] = pii(G[i].size(), i); sort(all(deg), greater<pii>()); for (int i = 0; i < nRegions; i++) { vector<bool> usedColor(nRegions, false); pii p(deg[i]); int d = p.first; int from = p.second; for (int j = 0; j < G[from].size(); j++) { int to = G[from][j]; if (colors[to] == -1) continue; usedColor[colors[to]] = true; } for (int j = 0; j < nRegions; j++) { if (!usedColor[j]) { colors[from] = j; break; } } } return colors; } vector<int> graphColoring2() { vector<int> colors(nRegions, -1); vector<pii> deg(nRegions); for (int i = 0; i < nRegions; i++) deg[i] = pii(G[i].size(), -i); sort(all(deg), greater<pii>()); for (int i = 0; i < nRegions; i++) deg[i].second *= -1; vector<bool> vertices(nRegions, false); for (int i = 0; i < nRegions; i++) { vector<bool> usedColor(nRegions, false); pii p(deg[i]); int d = p.first; int from = p.second; vertices[from] = true; for (int j = 0; j < G[from].size(); j++) { int to = G[from][j]; if (!vertices[to] || colors[to] == -1) continue; usedColor[colors[to]] = true; } for (int j = 0; j < nRegions; j++) { if (!usedColor[j]) { colors[from] = j; break; } } } return colors; } int calcScore(vector<int>& colors) { int nColors = *max_element(all(colors)) + 1; int score = 100000 * nColors; for (int i = 0; i < nRegions; i++) { int c = colors[i]; score += pixSum[i] - pixSumColor[i][c]; } return score; } bool getOptimalColor(vector<int>& colors, int& bestScore) { vector<int> bestPerm; int nColors = *max_element(colors.begin(), colors.end()) + 1; vector<vector<int>> groups(nColors); for (int i = 0; i < nRegions; i++) { groups[colors[i]].push_back(i); } vector<int> pixSumGroup(nColors, 0); vector<vector<int>> pixSumGroupColor(nColors, vector<int>(nOldColors, 0)); for (int i = 0; i < nColors; i++) { for (int j = 0; j < groups[i].size(); j++) { pixSumGroup[i] += pixSum[groups[i][j]]; for (int c = 0; c < nOldColors; c++) { pixSumGroupColor[i][c] += pixSumColor[groups[i][j]][c]; } } } bestScore = INT_MAX; vector<int> perm(nColors); for (int i = 0; i < nColors; i++) perm[i] = i; do { int score = 0; for (int i = 0; i < nColors; i++) { int col = perm[i]; score += pixSumGroup[i] - (col < nOldColors ? pixSumGroupColor[i][col] : 0); } if (score < bestScore) { bestScore = score; bestPerm = perm; } } while (next_permutation(all(perm))); for (int i = 0; i < nRegions; i++) colors[i] = bestPerm[colors[i]]; bestScore += nColors * 100000; return true; } double getTemp(double startTemp, double endTemp, double deg = 1.0, double t = timer.time() - timer.t, double T = timer.limit) { return endTemp + (startTemp - endTemp) * pow((T - t) / T, deg); } // annealing bool colorShuffle(vector<int>& colors, int& bestScore) { int nColors = *max_element(all(colors)) + 1; vector<int> changeable(nRegions, (1 << nColors) - 1); for (int from = 0; from < nRegions; from++) { changeable[from] &= ~(1 << colors[from]); for (const int& to : G[from]) { changeable[from] &= ~(1 << colors[to]); } } const unsigned R = (1 << 24), mask = (1 << 24) - 1; while (!timer.elapses()) { int reg = rnd.nextUInt(nRegions); if (!changeable[reg]) continue; vector<int> cols; for (int i = 0, x = changeable[reg]; i < nColors; i++) { if (x & 1) cols.push_back(i); x >>= 1; } int from_col = colors[reg]; int to_col = cols[rnd.nextUInt(cols.size())]; int dif = pixSumColor[reg][from_col] - pixSumColor[reg][to_col]; int score = from_col - to_col + dif; double temp = getTemp(100, 0.1); double prob = exp(-score / temp); if (R * prob < (rnd.nextUInt() & mask)) continue; bestScore += dif; changeable[reg] |= (1 << from_col); changeable[reg] &= ~(1 << to_col); colors[reg] = to_col; // reg の周りの頂点の情報を更新する for (const int& v : G[reg]) { changeable[v] = ((1 << nColors) - 1) & ~(1 << colors[v]); for (const int& w : G[v]) { changeable[v] &= ~(1 << colors[w]); } } } return true; } bool colorReduce(vector<int>& colors, int& bestScore) { int nColors = *max_element(all(colors)) + 1; vector<int> nColorVertices(nColors, 0); vector<int> changeable(nRegions, (1 << nColors) - 1); for (int from = 0; from < nRegions; from++) { nColorVertices[colors[from]]++; changeable[from] &= ~(1 << colors[from]); for (const int& to : G[from]) { changeable[from] &= ~(1 << colors[to]); } } const int P = max(100, V); while (timer.time() - timer.t < 3.0) { int reg = rnd.nextUInt(nRegions); if (!changeable[reg]) continue; vector<int> cols; for (int i = 0, x = changeable[reg]; i < nColors; i++) { if (x & 1) cols.push_back(i); x >>= 1; } int from_col = colors[reg]; int to_col = cols[rnd.nextUInt(cols.size())]; if (to_col == nColors - 1 && rnd.nextUInt(P) != 0) continue; int dif = pixSumColor[reg][from_col] - pixSumColor[reg][to_col]; bestScore += dif; changeable[reg] |= (1 << from_col); changeable[reg] &= ~(1 << to_col); colors[reg] = to_col; // reg の周りの頂点の情報を更新する for (const int& v : G[reg]) { changeable[v] = ((1 << nColors) - 1) & ~(1 << colors[v]); for (const int& w : G[v]) { changeable[v] &= ~(1 << colors[w]); } } nColorVertices[to_col]++; nColorVertices[from_col]--; if (nColorVertices[from_col] == 0) { nColors--; for (int i = 0; i < nRegions; i++) { changeable[i] &= ~(1 << nColors); } bestScore -= 100000; } } return true; } bool init(int _H, const vector<int>& _regions, const vector<int>& _oldColors) { regions = _regions; oldColors = _oldColors; engine.seed(seed_gen()); N = regions.size(); H = _H; W = N / H; nRegions = V = *max_element(regions.begin(), regions.end()) + 1; nOldColors = *max_element(oldColors.begin(), oldColors.end()) + 1; pixSum.resize(nRegions, 0); pixSumColor.resize(nRegions, vector<int>(16, 0)); vector<vector<int>> regions2D(H, vector<int>(W)); for (int i = 0; i < H; i++) for (int j = 0; j < W; j++) { const int n = i * W + j; const int reg = regions[n]; const int col = oldColors[n]; regions2D[i][j] = reg; pixSum[reg]++; pixSumColor[reg][col]++; } // create graph G.resize(nRegions); // 隣接行列表現 vector<vector<bool>> _G(nRegions, vector<bool>(nRegions, false)); for (int i = 0; i < H; i++) for (int j = 0; j < W; j++) { int reg = regions2D[i][j]; for (int d = 0; d < 4; d++) { int ni = i + di[d]; int nj = j + dj[d]; if (ni < 0 || H <= ni || nj < 0 || W <= nj) continue; int nreg = regions2D[ni][nj]; if (reg == nreg) continue; _G[reg][nreg] = _G[nreg][reg] = true; } } // 隣接リストに変換 E = 0; for (int i = 0; i < nRegions; i++) { for (int j = 0; j < nRegions; j++) { if (_G[i][j]) { G[i].push_back(j); E++; } } } E /= 2; return true; } vector<int> recolor(int _H, vector<int> _regions, vector<int> _oldColors) { timer.measure(); init(_H, _regions, _oldColors); vector<int> bestColors = graphColoring1(); int nBestColors = *max_element(all(bestColors)) + 1; int bestScore = calcScore(bestColors); getOptimalColor(bestColors, bestScore); vector<int> colors = graphColoring2(); { int nColors = *max_element(all(colors)) + 1; if (nColors <= nBestColors) { int score = calcScore(colors); getOptimalColor(colors, score); if (score < bestScore) { nBestColors = nColors; bestColors = colors; bestScore = score; } } } colorReduce(bestColors, bestScore); colorShuffle(bestColors, bestScore); getOptimalColor(bestColors, bestScore); vector<int> ret(nRegions); for (int i = 0; i < nRegions; ++i) { ret[i] = bestColors[i]; } return ret; } };
