SuperCon2023予選参加記
前提
あるハイカーに注目する。標高の遷移をv_0, v_1, ... , v_L-1とし、保有エネルギーの遷移をe_0, e_1, ... , e_L-1とする。
e_i+1 = e_i - (v_i+1 - v_i)
e_i+1 + v_i+1 = e_i + v_i
つまり標高と保有エネルギーの和は常に一定。これをPとおく。
P = e_i + v_i
e_i = P - v_i
(e_i >= 0) <=> (P - v_i >= 0) <=> (P >= V_i)
ハイカーは標高がP以下のうち最も標高が高い座標を選んで移動するということである。
アルゴリズム
方針:
ある地形Vにおいて、ハイカーiが最後に到達した座標を(LastY_i, LastX_i)とする。
スコア := ∑{(L - 1 - LastY_i) + |Xg_i - LastX_i|}
スコアは常に非負数であり、スコアが0のとき問題の条件は満たされる。スコアを最小化するよう地形Vを遷移し、山登り法を行う。
初期状態:
各y座標の行をランダムにシャッフルされた0からN-1の順列とする。
近傍遷移:
現在の地形において、目標座標に未到達のハイカーを一人選ぶ。そのハイカーの移動経路の近辺の1座標(y, x)とy座標が同じランダムな座標(y, x2)を選びswapする。
近辺とは
*@* *@* *@* *@* *@* *@* @*
といった座標のことである(@を含む)
swap後のスコアがswap前のスコアより増大していれば状態を戻す。
地形及びスコアの更新:
ある座標の標高を変更したとき影響があるのは
@ ***
*を通るハイカーのみ(y座標が0のときは@のみ)であるから、そのハイカーの寄与する分だけスコアを更新する。
感想
焼きなましてみたり初期状態をいじってみたりしたが、単純な山登り法を有意に上回ることはできなかった。焼きなまし法に関してはスコアが等しいならそこから解を出すまでの期待値も等しい(?)のでむしろ逆効果だったのだろうと思った。
提出コード
bit演算をする際、intよりbitsetを使った方が高速だったのですが、Homebrew GCCなるものが実はGCCの皮を被ったClang疑惑があり、intを使いました(_Find_first,nextが使えないので)。
速度:
配布されたテストケース10個について100回ずつ回してテストしました(つまり合計1000回)。何回か試しましたが、平均速度は2.7ms前後に収束しています。乱択山登りしかしていないため局所最適化に陥いる可能性は小さく本番でも100ケース合計で500msを上回ることはなかったのではないかと思っています。
手元環境:
CPU: Ryzen5 2400G
OS: Ubuntu 22.04.2 LTS
本番環境はM1とのことなので、これより速くなると思います。
#include <algorithm> #include <chrono> #include <random> #include "sc1.h" constexpr int TimeLimit = 590000; int Score = 0; // 現在のスコア int unreached = 0; // 目標座標に未到達のハイカーの集合(bitでもつ) int LastY[SC_M], LastX[SC_M]; // 現在の地形でハイカーiが最後に到達した座標 int Score_individual[SC_M]; // 各ハイカーのScoreへの寄与 int V[SC_L][SC_N]; // 現在の地形(実装の簡単のため、問題とは向きがことなっている) int Idx[SC_L][SC_M]; // ハイカーiのあるy座標でのx座標 int Path[SC_L][SC_N]; // 座標(y,x)を通るハイカーの集合(bitでもつ) std::mt19937 RNG; // 乱数 // bit関連の便利関数 -> inline bool bit_test(int x, int i) noexcept { return (bool)(x&(1<<i)); } inline void bit_set(int &x, int i) noexcept { x |= (1<<i); } inline void bit_reset(int &x, int i) noexcept { x ^= (1<<i); } inline int bit_find_first(int x) noexcept { if (x == 0) return 32; return __builtin_ctz(x); } inline int bit_find_next(int x, int i) noexcept { if ((x>>(i+1)) == 0) return 32; return __builtin_ctz(x>>(i+1))+i+1; } // <- // (y,x)からあるハイカーhikerの移動経路を探索 inline void search_path(int hiker, int y, int x) noexcept { while (y < SC_L-1) { int max_v = -1, next_x = -1; for (int i=x-1; i<=x+1; ++i) if (0<=i && i<SC_N) { if (V[y+1][i] > V[0][SC_Xs[hiker]]+SC_E0) continue; if (V[y+1][i] > max_v) { max_v = V[y+1][i]; next_x = i; } } if (max_v < 0) break; ++y; x = next_x; bit_set(Path[y][x], hiker); Idx[y][hiker] = x; } LastY[hiker] = y; LastX[hiker] = x; } // (y,x)からあるハイカーhikerの移動経路を更新 inline void update_path(int hiker, int y, int x) noexcept { bool flag = (y>0); while (y < SC_L-1) { int max_v = -1, next_x = -1; for (int i=x-1; i<=x+1; ++i) if (0<=i && i<SC_N) { if (V[y+1][i] > V[0][SC_Xs[hiker]]+SC_E0) continue; if (V[y+1][i] > max_v) { max_v = V[y+1][i]; next_x = i; } } if (max_v < 0) { for (int i=y+1; i<SC_L; ++i) { if (Idx[i][hiker] >= 0) { bit_reset(Path[i][Idx[i][hiker]], hiker); Idx[i][hiker] = -1; } else break; } LastY[hiker] = y; LastX[hiker] = x; return; } ++y; x = next_x; if (flag && x==Idx[y][hiker]) return; if (Idx[y][hiker] >= 0) bit_reset(Path[y][Idx[y][hiker]], hiker); bit_set(Path[y][x], hiker); Idx[y][hiker] = x; } LastY[hiker] = y; LastX[hiker] = x; } // (y,x)を通るハイカーについてスコア更新 inline void update_sub(int y, int x) { if (Path[y][x] == 0) return; for (int i=bit_find_first(Path[y][x]); i<SC_M; i=bit_find_next(Path[y][x],i)) { Score -= Score_individual[i]; update_path(i, y, x); Score_individual[i] = (SC_L-1-LastY[i])+abs(SC_Xg[i]-LastX[i]); Score += Score_individual[i]; if (Score_individual[i] > 0) bit_set(unreached, i); else bit_reset(unreached, i); } } // 座標(y,x),(y,x2)をswapした際のスコア更新 inline void update(int y, int x, int x2) noexcept { if (y == 0) { update_sub(y, x); update_sub(y, x2); return; } int updated = 0; for (int i=x-1; i<=x+1; ++i) if (0<=i && i<SC_N) { update_sub(y-1, i); bit_set(updated, i); } for (int i=x2-1; i<=x2+1; ++i) if (0<=i && i<SC_N) { if (!bit_test(updated, i)) update_sub(y-1, i); } } // 近傍遷移 inline void transition() noexcept { int k = bit_find_first(unreached); int y = RNG()%(LastY[k]+1); int x = Idx[y][k]; if (x == 0) x += RNG()%2; else if (x == SC_N-1) x -= RNG()%2; else x += (RNG()%3)-1; int x2 = RNG()%SC_N; while (x == x2) x2 = RNG()%SC_N; int old_score = Score; std::swap(V[y][x], V[y][x2]); update(y, x, x2); if (Score > old_score) { std::swap(V[y][x], V[y][x2]); update(y, x, x2); } } // 初期状態 inline void init() noexcept { for (int i=0; i<SC_L; ++i) { std::iota(V[i], V[i]+SC_N, 0); std::shuffle(V[i], V[i]+SC_N, RNG); } for (int i=0; i<SC_M; ++i) { bit_set(Path[0][SC_Xs[i]], i); Idx[0][i] = SC_Xs[i]; for (int j=1; j<SC_L; ++j) Idx[j][i] = -1; search_path(i, 0, SC_Xs[i]); Score_individual[i] += (SC_L-1-LastY[i])+abs(SC_Xg[i]-LastX[i]); Score += Score_individual[i]; if (Score_individual[i] > 0) bit_set(unreached, i); } } int main() { SC_input(); init(); std::chrono::system_clock::time_point start_time = std::chrono::system_clock::now(); int transition_count = 0; while (true) { if (transition_count%2000 == 0) { int current_time = static_cast<int>(std::chrono::duration_cast<std::chrono::microseconds>(std::chrono::system_clock::now()-start_time).count()); if (current_time > TimeLimit) break; } transition(); if (Score == 0) break; ++transition_count; } // y座標x座標が逆になっているので直す for (int i=0; i<SC_L; i++) for (int j=0; j<SC_N; j++) SC_ans[j][i] = V[i][j]; SC_output(); return 0; }
