AGC001の参加日記
AGC第一回。参加者1200人超でめでたい。2完で318位でした。
Editorial：https://agc001.contest.atcoder.jp/data/agc/001/editorial.pdf
A: BBQ Easy - AtCoder Grand Contest 001 | AtCoder
バーベキュー用の串が2N本ある。1つの串焼きに2本の串を使う。1つの串焼きに使える具材は、短いほうの串の長さに等しい。最大でいくつの具材を串焼きにできるか。
串をソートしてペアを作り、それぞれの短いほうの和を求めればよい。標準入出力の凡ミスで二回もWAを出してしまった。
public static int Solve(int[] l) { var ret = 0; l = l.OrderByDescending(v => v).ToArray(); for (int i = 0; i < l.Length - 1; i+=2) ret += Math.Min(l[i], l[i + 1]); return ret; }
B: Mysterious Light - AtCoder Grand Contest 001 | AtCoder
1辺の長さがNの鏡3つを、反射面を内側に向けて正三角形状に組み合わせる。三角形の頂点をa,b,cとする。
辺abのある点x(aからの距離X)から、辺bcと水平に光を発射する。この光は、鏡に当たると反射するが、さらに光の軌跡に当たっても反射する不思議な性質がある。この光は、必ず元の点に戻ってくることが証明できる。光の軌跡の長さを求めよ。
2<=N<=10^12、1<=X<=N-1、NとXは整数
dfs(a,b)を、現在地（上図）からの、残りの距離を返す関数と定義して再帰的に解いた。
なおNの最大値が大きいので、Intだとオーバーフローする。
public static UInt64 Solve(UInt64 n, UInt64 x) { var ret = x + (n - x); ret += dfs(x, n - x); return ret; } public static UInt64 dfs(UInt64 a, UInt64 b) { if (a == 0 || b == 0) return 0; if (b % a == 0) { return a * 2 * (b / a - 1) + a; } var ret = (2 * a) * (b / a); if (a % (b % a) == 0) return ret + ((b % a) * 2) * (a / (b % a)) - b % a; ret += ((b % a) * 2) * (a / (b % a)); return ret + dfs(a % (b % a), b % a); }
良く分からないが、なんと3*GCD()で一発で解くこともできるらしい。
C: Shorten Diameter - AtCoder Grand Contest 001 | AtCoder
N頂点の木がある。直径をK以下にするためには、最少でいくつの頂点を削除する必要があるか。
各頂点（Kが奇数なら辺）で、距離K/2を超える頂点の数をもとめ、その最小値が解答になる。
public class Solver { static int maxDist; static List<List<int>> edges; public static int Solve(int n, int k, List<List<int>> e) { maxDist = k / 2; edges = e; var ret = Int32.MaxValue; for (int i = 0; i < n; i++ ) { if (k % 2 == 0) ret = Math.Min(ret, Dfs(i, -1, 0)); else foreach(var j in e[i]) ret = Math.Min(ret, Dfs(i, j, 0) + Dfs(j, i, 0)); } return ret; } static int Dfs(int cur, int prev, int dist) { var ret = dist > maxDist ? 1 : 0; foreach (var next in edges[cur]) { if (next == prev) continue; ret += Dfs(next, cur, dist + 1); } return ret; } }
本番では、①木の直径を求め②Kを超えていたらに端を削除、を繰り返してTLEだった。
部分点がない問題なので、TLEになりそうな時点で、実装せず別解法を考えるべきだった。
D: Arrays and Palindrome - AtCoder Grand Contest 001 | AtCoder
長さMの数列Aが与えられる。Aの総和はNである。このとき、以下を満たす数列Bを解答せよ。
次の条件を満たす長さNの文字列が、すべて同じ文字になる
先頭のa1文字、続くa2文字、さらに続くa3文字...はすべて回文
先頭のb1文字、続くb2文字、さらに続くb3文字...はすべて回文
Aの中央にある奇数長の回文が3個以上なら、Bを作ることは不可能。
それ以外なら、まず奇数を左右の端に移動したのち、どちらかの端から１つずつずらして取ったものが解答になる。
// return value: a, b.length, b public static Tuple<List<int>, int, List<int>> Solve(int n, int m, List<int> a) { if (a.Count(v => v % 2 == 1) > 2) return null; if (m == 1) { List<int> ret; if (a[0] > 2) ret = new List<int>() { a[0] - 1, 1 }; else ret = a.ToList(); return new Tuple<List<int>, int, List<int>>(a, ret.Count(), ret); } //move odd items to first and last if (a.Count(v => v % 2 == 1) > 0) { var fst = a.First(v => v % 2 == 1); a.Remove(fst); a.Insert(0, fst); var lst = a.Last(v => v % 2 == 1); var lstIdx = a.LastIndexOf(lst); a.RemoveAt(lstIdx); a.Add(lst); } var b = new List<int>() { a.Last() + 1 }; for (int i = a.Count - 2; i > 0; i--) { b.Add(a[i]); } if (a[0] > 1) b.Add(a[0] - 1); b.Reverse(); return new Tuple<List<int>, int, List<int>>(a, b.Count(), b); }
こういう問題だとLINQがとても便利。
ARC053 - ARC057メモ（練習）
ARC057
A: 2兆円 - AtCoder Regular Contest 057 | AtCoder
所持金がt円ある。ある日の所持金がt円なら、次の日には1+Kt円増えている。二兆円に達するのは何日後か。
やるだけだが、k=0のケースを考慮しないとTLEになる。
public double Solve(double a, double k) { if (k == 0) return 2E12 - a < 0 ? 0 : 2E12 - a; double n = 0; while (true) { if (a >= 2E12) break; a += (1 + k * a); n++; } return n; }
B: 高橋君ゲーム - AtCoder Regular Contest 057 | AtCoder
N日間、それぞれa[i]回のゲームを行う。i日目の勝率が0~i-1日目までの勝率より真に高かったらその日は機嫌が良い。合計でK回ゲームに勝ったとすると、機嫌のよかった日数の最大値はいくつか。
なかなか解けずに苦しんだが、問題の読み違えのせいだった。
dp[i][j]を、i日目までにj回勝率があがる場合の、最小のそれまでの勝利日数とする。
dp[i+1][]は、負けた場合と、勝率が上がりギリギリの勝利数の2パターンで計算していけば求まる。
最終的に、dp[N][j]がK以下になる最大のjが答えになる。
public class Solver { const int INF = 500000 * 2000 + 1; int[] sum; List<int> _a; public int Solve(int n, int k, List<int> a) { if (a.Sum() == k) return 1; _a = a; sum = new int[a.Count()]; sum[0] = a[0]; for (int i = 1; i < a.Count(); i++) { sum[i] = sum[i - 1] + a[i]; } var dp = new int[n, n + 1]; for (int i = 0; i < n; i++) for (int j = 0; j < n + 1; j++) dp[i, j] = INF; for (int i = 0; i < n; i++) dp[i, 0] = 0; dp[0, 1] = a[0] > 0 ? 1 : 0; for (int i = 1; i < n; i++) { for (int j = 1; j < n + 1; j++) { dp[i, j] = Math.Min(dp[i - 1, j], GetMinWinNum(dp[i - 1, j - 1], i)); } } var ret = 0; for (int i = 1; i < n + 1; i++) { if (dp[n - 1, i] > k) continue; ret = Math.Max(ret, i); } return ret; } int GetMinWinNum(int prevWinSum, int idx) { if (prevWinSum == INF) return INF; var prevWinRate = (double)prevWinSum / (double)sum[idx - 1]; var needWinCnt = (int)Math.Ceiling(prevWinRate * (double)_a[idx]); if ((double)needWinCnt / (double)_a[idx] <= prevWinRate) needWinCnt++; if (needWinCnt > _a[idx]) return INF; return prevWinSum + needWinCnt; } }
ARC056
A: みんなでワイワイみかん - AtCoder Regular Contest 056 | AtCoder
K個以上のみかんを買いたい。みかんは1個A円、もしくはL個B円。最小の支払金額を求めよ。A, B, C <= 10^9、L <= 10^9、B <= A*L
ぜんぶA円で買う・なるべくB円で買って残りをA円で買う・ぜんぶB円で買う、の３パターンしかない。intだとオーバーフローする。
static ulong Solve(ulong a, ulong b, ulong k, ulong l) { return Math.Min(k * a, Math.Min((k / l) * b + (k % l) * a, ((k / l) + 1) * b)); }
B: 駐車場 - AtCoder Regular Contest 056 | AtCoder
駐車スペースがN個あり、それぞれ1~Nに番号が振られている。各駐車スペースは双方向にM本の道でつながっている。そして駐車スペースSが入口につながっている。車i(1~N)が順番に入口から入り、かつ自分の番号の駐車スペースに停めるとき、無事に駐車できる車はどれか。
駐車スペースiに車iが駐車できるというこは、Sからiまでに、i以上の頂点のみからなる経路が存在することと同じ。Dijkstra変種で解ける。
public class Solver { public static IEnumerable<int> Solve(int n, int s, List<List<int>> e) { var dist = new int[n]; for (int i = 0; i < n; i++) dist[i] = -1; var que = new PriorityQueue<ComparablePair<int, int>>(); //desc by score que.Push(new ComparablePair<int, int>(s, s)); while (que.Count() > 0) { var nextPair = que.Pop(); var score = nextPair.Item1; var node = nextPair.Item2; if (dist[node] >= score) continue; dist[node] = score; foreach (var next in e[node]) que.Push(new ComparablePair<int, int>(Math.Min(next, score), next)); } return Enumerable.Range(1, n).Where(v => dist[v - 1] >= v - 1); } }
TLEに苦しんだけど、標準出力をFlushしてないというオチだった（ずっとアルゴリズムを疑って改善してた）。
以下のコードを忘れずに付けるようにしなければ。
Console.SetOut(new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false }); foreach (var r in Solver.Solve(n, s - 1, e)) { Console.WriteLine(r); } Console.Out.Flush();
C: 部門分け - AtCoder Regular Contest 056 | AtCoder
社員がN人いて、各社員間は信頼度w[i,j]が定まっている。この会社をいくつかの部門に分けるとき、スコアを最大化せよ。
スコアは、(部門の数) x K - (異なる部門に属する2人の信頼度の総和)
1<=N<=17, 1<=w[i,j]<=10^16, 1<=K<=10^16
次のように言い換えることができる
- NxNの重み付き無向グラフの頂点を彩色する
- 使われた色の数xK-異なる色の間の重みの総和＝スコア
- スコアの最大値はいくらか
Nが最大17であることに着目する。
DP[S]を頂点集合Sの解答だとすると、Sの部分集合tとuについて
DP[S] = dp[t] + k - (t-u間の重みの総和)
となる。
ある集合xの重み総和sub[x]は、その部分集合y・zについて
sub[x] = sub[y] + suz[z] + (y-z間の重みの総和)
なので、
DP[S] = dp[t] + k - sub[S] + sub[t] + sub[u]
と変形することができる。
public int Solve(int n, int k, int[,] w) { // すべての部分集合のコスト合計 var sub = new int[1 << 17]; for (int b = 0; b < 1 << n; b++) for (int i = 0; i < n; i++) for (int j = i + 1; j < n; j++) if (((1 << i) & b) != 0 && ((1 << j) & b) != 0) sub[b] += w[i, j]; // dp[S] は集合Sの解 var dp = new int[1 << 17]; for (int i = 0; i < 1 << n; i++) dp[i] = k; // Sを集合tと集合uに分解したとき、 // dp[S]は dp[t] + k - sub[S] + sub[t] + sub[u] になる for (int s = 0; s < 1 << n; s++) { for (int t = (s - 1) & s; t > 0; t = (t - 1) & s) { dp[s] = Math.Max(dp[s], dp[t] + k - sub[s] + sub[t] + sub[s - t]); } } return dp[(1 << n) - 1]; //dp[1 << n - 1] は通らないので注意！ }
ARC055
A: 数え上げ - AtCoder Regular Contest 055 | AtCoder
1以上100以下の整数Nが与えられる。10^N+7を出力せよ。
1のあとN-1個のゼロを出力し、最後に7を出せばよい。
public string Solve(int n) { var ret = new StringBuilder(); ret.Append("1"); for (int i = 0; i < n - 1; i++) ret.Append("0"); ret.Append("7"); return ret.ToString(); }
B: せんべい - AtCoder Regular Contest 055 | AtCoder
大きさ1～Nのせんべいがランダムな順番に与えられる。大きさはそれぞれ１つずつ。与えられた時点で、食べるか食べないかを決定する。すでに見たせんべいの大小関係のみ分かる。最適戦略をとったとき、最大のせんべいNを食べることができる確率はいくらか。ただし、K枚までしか食べることはできない。
1<=K<=N<=1000
難しかった…。
今のせんべいが過去最大なら、(1)食べる(2)食べないのどちらかになる。
i番目のせんべいが過去最大になる確率は1/i、そうでない確率は1-1/i。
DFSで解けるが、「これまでの最大をすでに食べたか否か」を持たないとうまく遷移できない。
public class Solver { int _n; double[, ,] dp; public double Solve(int n, int k) { _n = n; dp = new double[n, k + 1, 2]; for (int i = 0; i < n; i++) for (int j = 0; j < k + 1; j++) for (int l = 0; l < 2; l++) dp[i, j, l] = -1; return dfs(0, k, 0); } double dfs(int idx, int k, int ateMaxVal) { if (idx == _n) return ateMaxVal; if (dp[idx, k, ateMaxVal] != -1) return dp[idx, k, ateMaxVal]; //current one is not max //rate: i - 1 / i var ret = ((double)(idx + 1 - 1) / (double)(idx + 1)) * dfs(idx + 1, k, ateMaxVal); //current one is max //rate: 1 / i //don't eat var temp = (1.0 / (double)(idx + 1)) * dfs(idx + 1, k, 0); //eat if(k > 0) temp = Math.Max(temp, (1.0 / (double)(idx + 1)) * dfs(idx + 1, k - 1, 1)); ret+=temp; dp[idx, k, ateMaxVal] = ret; return ret; } }
C: ABCAC - AtCoder Regular Contest 055 | AtCoder
長さNの文字列Sが与えられる。３つの空でない文字列A,B,Cを使い、S=ABCACと表現できる組み合わせは何通りか。
愚直に解いたら部分点になった。
public int Solve(char[] s) { var ret = 0; for (int ai = 0; ai < s.Length; ai++) for (int ci = s.Length - 1; ci > ai; ci--) if (Meet(s, ai, ci)) ret++; return ret; } bool Meet(char[] s, int ai, int ci) { var alen = ai + 1; var clen = s.Length - ci; var blen = s.Length - alen - alen - clen - clen; if(alen <= 0 || blen <= 0 || clen <= 0) return false; //check a while (ai >= 0) { if (s[ai] != s[alen + blen + clen + ai]) return false; ai--; } //check c while (ci < s.Length) { if (s[ci] != s[ci - clen - alen]) return false; ci++; } return true; }
ABC/ACの切れ目を全探索してゆく。このとき、AとCが両方存在できれば有効になる。
ACの存在を効率よく判定する方法は、ローリングハッシュでの二分探索や、Z-algorithmを使うやり方がある。
参考
ローリングハッシュ：蟻本(第二版)P.332
Z-algorithm：文字列の頭良い感じの線形アルゴリズムたち３ - あなたは嘘つきですかと聞かれたら「YES」と答えるブログ
ARC054
A: 動く歩道 - AtCoder Regular Contest 054 | AtCoder
円周Lの動く歩道がある。動く歩道は、時計回りに1秒間にs進んでいる。唯一の出口が最北点から時計回りに距離Dにあり、いま距離Sにいる。1秒間にY歩けるとき、最短で何秒後に出口に着けるか。
時計回りと反時計回りを試す。
public double Solve(int l, int x, int y, int s, int d) { double leftDist = s > d ? Math.Abs(s - d) : l - Math.Abs(s - d); double rightDist = d > s ? Math.Abs(s - d) : l - Math.Abs(s - d); return s == d ? 0.0 : Math.Min(rightDist / (double)(y + x), y - x <= 0 ? double.MaxValue : leftDist / (double)(y - x)); }
B: ムーアの法則 - AtCoder Regular Contest 054 | AtCoder
現在のコンピューター性能でP年かかるタスクがある。コンピューターは、1.5年ごとに処理能力が2倍になる。なるべく早いタスクの終了時間を求めよ。（タスクは中断できないものとする）
0<=P<=10^18
x年後にタスク処理を始めるとするとき、終了時間はx+P/(2^(x/1.5))になる。これは凸関数なので、三分探索で求めることができる。
間違えてタスクの開始時間を返していたのに気づかず手間取った。
ちなみに、微分すれば一発で答えが出せるようだ。
public double Solve(double p) { double l = 0; double r = p; //ternary search while(r - l > 1E-10) { var m1 = l + (r - l) / 3.0; var m2 = l + (r - l) * 2.0 / 3.0; var t1 = m1 + p / Math.Pow(2.0, m1 / 1.5); var t2 = m2 + p / Math.Pow(2.0, m2 / 1.5); if (t1 < t2) { r = m2; } else { l = m1; } } return (l + r) / 2.0 + p / Math.Pow(2.0, ((l + r) / 2.0) / 1.5); //この計算を忘れていた }
ARC053
A: ドミノ色塗り - AtCoder Regular Contest 053 | AtCoder
H x Wのタイルがある。上下または左右に隣り合う２マスを選びたい。選び方は何通りか。
2 x W x H - (W + H) が答え。
Console.WriteLine(2 * h * w - w - h);
B: 回文分割 - AtCoder Regular Contest 053 | AtCoder
英小文字からなる文字列Sを適当にならびかえ、それを分割していくつかの回文文字列を作る。この回文文字列の長さの最小値をなるべく大きくしたい。この値を求めよ。
奇数個の文字を１つずつ、出来上がる回文文字列の中心に配置する。そして残った文字（すべて偶数個）をなるべく均等に割り振ればよい。
public static int Solve(string s) { var num = new int[26]; foreach (var c in s) num[c - 'a']++; var devideNum = 0; foreach (var n in num) if (n % 2 == 1) devideNum++; if(devideNum == 0) return s.Length; var ret = 1 + (((s.Length - devideNum) / 2) / devideNum) * 2; return ret; }
C: 魔法使い高橋君 - AtCoder Regular Contest 053 | AtCoder
N個の魔法がある。i番目の魔法を唱えると、a[i]℃温度が上がったのち、b[i]℃温度が下がる。魔法を唱える順番を調整し、気温の最大値をなるべく小さくしたい。この気温を答えよ。
温度が下がる魔法と上がる魔法に分け、下がる魔法をa[i]の昇順、上がる魔法をb[i]の降順でソートする。あとは下がる魔法→上がる魔法の順番で唱える。
public static Int64 Solve(int n, Int64[][] m) { var magics_dec = m.Where(v => v[0] < v[1]).OrderBy(v => v[0]); var magics_inc = m.Where(v => v[0] >= v[1]).OrderByDescending(v => v[1]); Int64 ret = 0, cur = 0; foreach (var magic in magics_dec.Concat(magics_inc)) { ret = Math.Max(ret, cur + magic[0]); cur += magic[0] - magic[1]; } return ret; }
これもintだとオーバーフローする。
部分的に正答になったときは、まずオーバーフローを疑うのが基本になりそう。
Topcoder Open 2016 Marathon Match(Round 3)の参加日記
制約が多くて面倒な問題だった。そのせいか、レート中位~下位の参加者がずいぶん少なかった。
結果は暫定62位/101人の定位置。
問題概要
- 長さ１の正方形セルSxS個で構成されるマップがある
- 各セルはタイプ（0~9）が設定されている
- マップ上にはN個のアイテムとN個のターゲットがある
- アイテムの近く（距離10^-3以内）に止まると、該当アイテムを拾う
- ターゲットの近くで止まると、持っているアイテムを落とす
- 1つのターゲットに落とすのは1つのアイテム
- 持てるアイテムの最大値はcapacityで与えられる
- すべてのアイテムをターゲットに落とさなければならない
- スタート地点はマップの外周から距離10^-3以内ならどこでもよい
- このとき、なるべく小さいコストで全アイテムをターゲットに落とすのが目的
- コストは、セルタイプx移動距離。タイプの違うセルをまたぐときは、さらにタイプ差の二乗が可算される
- 1回のステップでは、1つ以内のセルしかまたげない
- セルボーダーから距離10^-3以内には止まってはならない。
- ステップ間は10^-3以上の距離をおくこと
- S:10~50、タイプ数2~10、アイテム数:5~S*S/10、capacity:1~10
https://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=16704&pm=14283
方針
- Dijkstraでアイテム・ターゲット・エッジセル間の距離を求める
- Dijkstraの結果を使い、アイテムとターゲットでTSP（ビームサーチ）
- TSP結果から有効解を作成（経路復元）
- 有効解を改善（貪欲＋焼きなまし）
上位との比較
- 全体的な方針は一緒
- TS部分で大きな差がついている
- TSは焼きなましの人と、2optなどTSP特有のアルゴリズムの人がいる
- Dijkstraも、単純なセル間ではなくセルをさらに分割してる人もいた
反省
TSP部分で大きなスコア差が付いている。TSPがイマイチなのは気づいていたが、それより4の改善部分に時間を使ってしまった。
目についた部分を適当に改善するのではなく、どこに手を付けるべきかまず分析するべきだった。
Topcoder Marathon Match Round90 勉強メモ
2位のEvbCFfp1XBさんのコードを読んでみる。
https://community.topcoder.com/longcontest/?module=ViewProblemSolution&pm=14094&rd=16495&cr=23100980&subnum=3
問題文はこちら。
https://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=16495&pm=14094
方針（Forumより）
- ランダムに
ポイント0ポイント1未満のターゲットを選ぶ ※コードより修正 - ターゲットにポイント1が入るか、ループ回数が10になるまで以下を繰り返す
- ターゲット近くの同色ボールを選ぶ
- そのボールの近くのボールを1~10個選ぶ ※上で選んだボール含む
- 選んだボールでビームサーチ（Max Depth=20、幅250)
情報の持ち方
class Board { public static final int WALL = 1 << 27; public static final int EMPTY = 1 << 28; public static final int[] DR = { 0, 1, 0, -1, }; public static final int[] DC = { -1, 0, 1, 0, }; public static final int[] DELTA = { -1, 64, 1, -64, }; public static final int SHIFT = 6; public static final int MASK = (1 << SHIFT) - 1; public static final int[] ballIndex = new int[64 * 64]; public static final long[][] hashes = new long[64 * 64][10]; public int[][] distanceFromTarget; public static final int[] targetIndex = new int[64 * 64]; public List<ColoredPoint> balls = new ArrayList<>(); public List<ColoredPoint> targets = new ArrayList<>(); public int R; public int C; public long hash = 0; int countPoint1; private ArrayList<State> moveHistory = new ArrayList<>(); // ボールを動かした履歴 /// 省略 /// // ボールをある方向へ動かす public void next(int ballIndex, int direction) { ColoredPoint ball = balls.get(ballIndex); State current = new State(null, ballIndex, ball.z, direction, 0); moveHistory.add(current); { int index1 = targetIndex[ball.z]; if (index1 != EMPTY && getTargetColor(index1) == ball.color) { countPoint1--; } } hash ^= hashes[ball.z][ball.color]; // ボールを転がす。この更新のやりかたは参考になる DELTA = { -1, 64, 1, -64, }; int delta = DELTA[direction]; int z = ball.z; this.ballIndex[z] = EMPTY; do { z += delta; } while (this.ballIndex[z] == EMPTY); z -= delta; ball.z = z; this.ballIndex[z] = ballIndex; hash ^= hashes[ball.z][ball.color]; { int index1 = targetIndex[ball.z]; if (index1 != EMPTY && getTargetColor(index1) == ball.color) { countPoint1++; } } } /// 省略 /// } class State { State parent; public int index; public int z; public int direction; public double score; public int numMoves; /// 省略 /// } class State2 implements Comparable<State2> { State2 parent; public int index; public int z; public int direction; public double score; public double distance; // ビームサーチ用。ターゲットまでの（最短）距離合計 public int numMoves; /// 省略 /// }
巨大なboardクラスを用意している。履歴はStateクラスで持つ。State2はビームサーチ用。
メインルーチン
private void solve() { for (; timeManager.getSecond() < 9.5;) { if (board.getScorePoint1() > 0.999) { break; } // スコアが1未満のターゲット ArrayList<Integer> targetsScore0 = getTargetsScore0(); // ランダムに１つ選ぶ IntArray targetIndexes = new IntArray(); int targetIndex = targetsScore0.get((int) (targetsScore0.size() * rng.nextDouble())); targetIndexes.add(targetIndex); // 近隣ボールの選ぶ数。ランダムに試す int[] ns = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, }; Utils.shuffle(ns, rng); for (int maxN : ns) { if (board.getTargetScore(targetIndex) > 0.999) { break; } if (timeManager.getSecond() > 9.5) { break; } // ターゲットから最寄りの同色ボール int nearestSameColorBallIndex = getSameColorScore0BallsDistanceFromTargetAscending(targetIndex).get(0).second; ArrayList<Pair<Double, Integer>> balls = getBallsDistanceFromBallAscending(nearestSameColorBallIndex); // 同色ボールの近くのボールmaxN個 IntArray ballIndexes = new IntArray(); int n = Math.min(maxN, balls.size()); for (int i = 0; i < n; i++) { ballIndexes.add(balls.get(i).second); } int currentNumMoves = board.numMoves(); int maxStep = 20; int maxBeamWidth = (int) (5 * 1000 / maxStep); countBeamsearch++; // ビームサーチ ArrayList<State> moves = beamsearch(ballIndexes, maxStep, maxBeamWidth, targetIndexes); if (moves == null) { continue; } for (State state : moves) { assert board.canMove(state.index, state.direction); board.next(state.index, state.direction); } // ベストスコアなら保持 if (board.getScorePoint1() > bestScore && board.numMoves() < board.maxNumRolls()) { bestScore = board.getScorePoint1(); bestSolution = board.getSolution(); } else { // ベストでなく、ターン数に余裕がないようなら棄却 if ((double) board.numMoves() / board.maxNumRolls() > 0.99 * timeManager.getSecond() / 9.5) { for (; board.numMoves() > currentNumMoves;) { board.previous(); } } } } } }
単純にN個のボールを選ぶのではなく、1個～10個と少ないほうから試している。後の参考になりそう。
ビームサーチの部分
// 動かすボール、最大深さ、ビーム幅、対象ターゲット（１つだけ） private ArrayList<State> beamsearch(IntArray ballIndexes, int maxStep, int maxBeamWidth, IntArray targetIndexes) { ArrayList<State2> currents = new ArrayList<>(); ArrayList<State2> nexts = new ArrayList<>(); ArrayList<State2> all = new ArrayList<>(); // 探索にでてきた全ノード。最後に一番いいやつを選ぶ int currentNumMoves = board.numMoves(); used.clear(); used.add(board.hash); // 初手の集合currentsを得る for (int i = 0; i < ballIndexes.length; i++) { int ballIndex = ballIndexes.values[i]; ColoredPoint ball = board.balls.get(ballIndex); int z = ball.z; // zはボール位置のIntパック for (int direction = 0; direction < 4; direction++) { if (!board.canMove(ballIndex, direction)) { continue; } board.next(ballIndex, direction); if (used.add(board.hash)) { double score = getSumScore(ballIndexes); double distance = getSumMinDistance(ballIndexes, targetIndexes); distance += 1e-2 * rng.nextDouble(); currents.add(new State2(null, ballIndex, z, direction, score, distance, 1)); } board.previous(); } } for (int step = 0; step < maxStep; step++) { if (currents.size() == 0) { break; } int beamWidth = Math.min(maxBeamWidth, currents.size()); Utils.select(currents, 0, currents.size(), beamWidth); // currentsをスコア＞距離でソートか？最初のビーム幅分のみ抽出？ for (int beam = 0; beam < beamWidth; beam++) { State2 currentState = currents.get(beam); all.add(currentState); { ArrayList<State2> currentStateList = reverse2(toList(currentState)); // 初手からcurrentStateまでの手のリスト ArrayList<State> res = new ArrayList<>(); for (State2 state : currentStateList) { res.add(new State(null, state.index, state.z, state.direction, state.score)); } board.set(res, currentNumMoves); // boardをcurrentStateにする } { assert getSumScore(ballIndexes) == currentState.score; if (currentState.score > ballIndexes.length - 1e-9) { break; } } for (int i = 0; i < ballIndexes.length; i++) { int ballIndex = ballIndexes.values[i]; ColoredPoint ball = board.balls.get(ballIndex); int z = ball.z; for (int direction = 0; direction < 4; direction++) { if (!board.canMove(ballIndex, direction)) { continue; } int nextZ = board.simulateNext(ball, direction); // 該当の方向へ動かしてみたときのz long currentHash = board.hash; boolean add = used.add(currentHash ^ (board.hashes[z][ball.color] ^ board.hashes[nextZ][ball.color])); // 使ってないHashになるなら if (add) { // scoreとdistanceを計算 double nextScore = currentState.score; { int index1 = board.targetIndex[z]; if (index1 != Board.EMPTY && board.getTargetColor(index1) == ball.color) { nextScore--; } } { int index1 = board.targetIndex[nextZ]; if (index1 != Board.EMPTY && board.getTargetColor(index1) == ball.color) { nextScore++; } } double score = nextScore; double nextDistance = currentState.distance; int targetIndex = targetIndexes.values[0]; if (board.distanceFromTarget[targetIndex][z] == 0 && board.getTargetColor(targetIndex) != ball.color) { nextDistance -= 1e9; } else { nextDistance -= board.distanceFromTarget[targetIndex][z]; } if (board.distanceFromTarget[targetIndex][nextZ] == 0 && board.getTargetColor(targetIndex) != ball.color) { nextDistance += 1e9; } else { nextDistance += board.distanceFromTarget[targetIndex][nextZ]; } double distance = nextDistance; distance += 1e-2 * rng.nextDouble(); // これは・・・？ // ちょっとバラけさせると探索が良くなるのか？ // 次手の集合nextsに加える nexts.add(new State2(currentState, ballIndex, z, direction, score, distance, currentState.numMoves + 1)); } } } } { ArrayList<State2> swap = currents; currents = nexts; nexts = swap; } nexts.clear(); } for (; board.numMoves() > currentNumMoves;) { board.previous(); } if (all.size() == 0) { return null; } Collections.sort(all); ArrayList<State2> allList = reverse2(toList(all.get(0))); ArrayList<State> res = new ArrayList<>(); for (State2 state : allList) { res.add(new State(null, state.index, state.z, state.direction, state.score)); } return res; }
ループで幅優先ビームサーチをしている。各NodeはState2クラスで保持していて、これが親へのポインタを持っているようだ。
この人のコードはかなり読みやすかった。
Javaだからか、それとも書き方が自分に似ているからだろうか。いずれにしても、とても参考になる。
かなり強い方なので、他のマッチのコードも読んでみても良さそうだ。
Topcoder Open 2016 Marathon Match(Round 1)勉強メモ
4位のnikaさんのコードを読んでみる。
https://community.topcoder.com/longcontest/?module=ViewProblemSolution&pm=10729&rd=16702&cr=20315020&subnum=18
Forumのご本人のポストによると、次の３つのフェーズに分かれているらしい。
パート１(30%)
rootが分割されるまでカットを足していく。足すカットは、いくつかの候補から、（コスト）/（新たに分割されるrootの数）がベストのものを選ぶ。
パート２(60%）
カットの増減を繰り返してスコアを改善する。カットをランダムに選んで取り除き、そしてrootがすべて分割されてないときは、パート１と同じ手段でカットを足す。スコアが改善するようならこれを使い、しないなら元に戻す。
パート３(10%)
カット位置を1ポイントずつ動かして改善をはかる。
カットを足す方法について。なるべく良い候補にするため①始点と終点をランダムに選ぶ②垂直・水平のどちらかを選ぶ③どちらかの方向の全パターンを見て、最も良いものを選ぶ、という処理を行っている。ここでコストの再計算を避けるため、スキャンラインテクニック（Scan Line Technique）というのを使っているらしい。
情報の持ち方
int m, n; // m: Plantの数、n: Endpointの数 int x[N], y[N] // x[], y[]: Endpointの座標 int parent[N]; // EndpointのPlant番号 int p[N]; // Endpointの親Endpoint番号 double edgeLength[N]; // Endpointとその親の距離 double edgeSum; // 距離の総合計 vector<int> plants[M]; // Plantに属するEndpoint vector<int> hull[M]; // Plantに属するEndpoint。外殻のみ。左下から時計回り // CutがPlantを切断するかどうかを判断するのに使う vector<int> ret; int separated[M][M]; // plantが分離されてるかどうか（いくつのカットで分離されたか） int phase; int minX[N], maxX[N]; int dead[N]; // 根が死んでいるかどうか int wouldKill[N]; int alive[N]; // 生きている根 int aliven; // 生きている音根の数 int wk; double aliveLength[N]; // 生きている根の長さ multiset<double> cutRatio[N]; // 根が切られた位置。multiset: sorted、重複OKのset typedef pair<Line, Mask> Cut; // Lineは始点ｘｙ・終点xyなどをもつ構造体 // Maskは120ビットのマスク。ビット位置ごとのXor、Orなどができる double bestSaved = -1e100; // 切り取られた根の長さ合計ベスト vector<Cut> bestSolution; double savedEdgeSum; vector<Cut> solution; // グループ： カットされてないPlantの集合 int group_n; // グループの総数 int group_cnt[M] // あるグループ番号に属するPlant数 int group[M][M]; // group[i][j]: グループ番号iに属する、j番目のPlant番号 int group_vis[M]; // ワーク
やはりClassを作るのは避けて、なるべく単純な配列等で保持している。
マスクは該当Cutが分割しているPlantの情報。Cut線からLeft集合とRight集合に分けている（ビット位置で保持）。この方法は汎用性がありそうだ。
メインルーチン
vector<int> makeCuts(int NP, vector<int> points, vector<int> roots) { Init(); m = NP; n = SZ(points) / 2; for (int i = 0; i < n; i++) { x[i] = points[2 * i]; y[i] = points[2 * i + 1]; } edgeSum = 0; for (int i = 0; i < n; i++) { if (i < m) { parent[i] = i; p[i] = -1; } else { p[i] = roots[2 * (i - m)]; parent[i] = parent[p[i]]; edgeLength[i] = hypot(1.0*x[i] - x[p[i]], 1.0*y[i] - y[p[i]]); edgeSum += edgeLength[i]; } plants[parent[i]].push_back(i); } F0(i, m) BuildHull(i); CL(0, separated); F0(i, m) separated[i][i] = 1; group_n = 1; group_cnt[0] = m; F0(i, m) group[0][i] = i; FirstPhase(); SecondPhase(); FinalPhase(); if (savedEdgeSum > bestSaved + 1e-4) { UpdateBestSolution(); } for (auto v : bestSolution) { v.first.AddToSolution(); } fprintf(stderr, "My score: %.2lf\n", bestSaved); c_o[9] = SZ(ret) / 4; Report(); return ret; }
BuildHullまでで必要な情報を取得したあと、フェーズ１～３を実行している。BuildHullのコードは今後の参考になりそうだった。
BuildHull
bool cmp_start(int a, int b) { int t = cw(startpoint, a, b); if (t != 0) return t>0; t = x[a] - x[b]; if (t != 0) return t<0; t = y[a] - y[b]; if (t != 0) return t<0; return 0; } int h[N+5]; void BuildHull(int k) { startpoint = plants[k][0]; for (int i : plants[k]) { if (x[i] < x[startpoint] || (x[i] == x[startpoint] && y[i] < y[startpoint])) startpoint = i; } // a[] はこのPlantに属するすべてのEndpoint // 左下のStartpointから、CWでソートされている vector<int> a; a.push_back(startpoint); for (int i : plants[k]) { // C++11の構文らしい if (x[i] != x[startpoint] || y[i] != y[startpoint]) a.push_back(i); } sort(a.begin() + 1, a.end(), cmp_start); // 外殻だけを取り出す vector<int>& h = hull[k]; h.push_back(a[0]); h.push_back(a[1]); int hn = 2; for (int i = 2; i < SZ(a); i++) { while (hn >= 2 && cw(h[hn - 2], h[hn - 1], a[i]) <= 0) { hn--; h.pop_back(); } h.push_back(a[i]); hn++; } h.push_back(a[0]); }
(1)左下を起点に、時計回りにソート(2)そのうち、cwが負になる点を除く。
パート1
void FirstPhase() { phase = 1; savedEdgeSum = edgeSum; while (1) { // カットされてないPlantの集合がなくなったら、調整してから終了 if (!group_n) { int sg = 1; while (sg) { sg = 0; // 該当カット単独でのPlant分割がなかったら、無駄なので削除 F0(i,SZ(solution)) if (!BreaksSolution(solution[i].second)) { ApplyMaskToSeparated(solution[i].second, -1); savedEdgeSum += ApplyLine(solution[i].first, -1, true);; // Lineを削除 solution.erase(solution.begin() + i); sg = 1; break; } } if (bestSaved < savedEdgeSum) { bestSaved = savedEdgeSum; bestSolution = solution; } return; } double t = Elapsed(); bestRatioFound = 1e10; int it = 0; aliven = 0; for (int i = m; i < n; i++) if (!dead[i]) { alive[aliven++] = i; aliveLength[i] = cutRatio[i].empty() ? edgeLength[i] : *cutRatio[i].begin(); } // ある程度の時間、繰り返してベストなカット（＋マスク）を得る int needs = 0; F0(i,group_n) needs += group_cnt[i] - 1; while (1) { it++; FindBestStraightCut(); // まあまあ良いCutを探し出して足す // ランダムな始点終点を選び、その後xかy方向に１ビットずつスライドさせて // ベストを選んだもの c_o[8]++; double portion = (Elapsed() - t) / (LTL - t); if (pow(portion, 1) * needs >= 1 || t >= LTL) break; // なぜこの条件が良く分からない・・・ } solution.push_back(bestCutFound); savedEdgeSum += ApplyLine(bestCutFound.first); // Lineを足す ApplyMaskToSeparated(bestCutFound.second); // separated[][], group_n, // group_vis[], group[][], group_cnt[] を更新 } }
すべてのPlantが切り離されるようCutを作成。
FindBestStraightCut()だけである程度良いCutになっているはずだが、さらにしつこく時間でループしてベストな候補を選んでいる。
BreakSolution()の実装はこれ。該当カットがソロで分割してるPlantがあればTrueを返している。
bool BreaksSolution(const Mask& mask) { vector<int> leftSide, rightSide; F0(i, m) if (mask.setAt(i)) leftSide.push_back(i); else rightSide.push_back(i); for (int ls : leftSide) for (int rs : rightSide) if (separated[ls][rs] == 1) return true; return false; }
パート2
void SecondPhase() { phase = 2; for (int i = m; i < n; i++) aliveLength[i] = edgeLength[i]; // このzの使いかたがよく分からない int z = min(n, 2000); z = max(z, n / 10); while (Elapsed() < GTL) { int sg = 1; // 無駄Cutを削除 while (sg) { sg = 0; for (int i = SZ(solution) - 1; i >= 0; i--) if (!BreaksSolution(solution[i].second)) { ApplyMaskToSeparated(solution[i].second, -1); bool needDelete = true; F0(j,SZ(bestSolution)) if (bestSolution[j].first == solution[i].first) { needDelete = false; break; } savedEdgeSum += ApplyLine(solution[i].first, -1, needDelete); solution.erase(solution.begin() + i); sg = 1; break; } } // カットされてないPlantがあるのはいいが、スコア悪化は嫌う if (savedEdgeSum < bestSaved + eps && group_n) { RevertSolution(); } if (!group_n) { // 全Plantがカット済で、かつベストスコア更新 if (savedEdgeSum > bestSaved + eps) { UpdateBestSolution(); // 全Plantはカット済だが、スコア悪化 } else if (savedEdgeSum < bestSaved - eps) { RevertSolution(); } // 適当に1~4本、Cutを削除 if (SZ(solution) > 0) { int k = my.nextInt(SZ(solution)); auto v = solution[k]; savedEdgeSum += ApplyLine(v.first, -1); ApplyMaskToSeparated(v.second, -1); Mask mask = v.second; solution.erase(solution.begin() + k); int sg = my.nextInt(15); if (sg == 14) sg = 3; else if (sg >= 12) sg = 2; else if (sg >= 8) sg = 1; else sg = 0; if (sg) { F0(k,SZ(solution)) { int cnt = 0; F0(i,m) if (mask.setAt(i) != solution[k].second.setAt(i)) cnt++; if (cnt <= sg || cnt >= m - sg) { auto v = solution[k]; savedEdgeSum += ApplyLine(v.first, -1); ApplyMaskToSeparated(v.second, -1); solution.erase(solution.begin() + k); break; } } } } } bestRatioFound = 1e10; int it = 0; aliven = 0; for (int i = m; i < z; i++) if (!dead[i] && cutRatio[i].empty()) { alive[aliven++] = i; } // パート１と同じようにCutを足していく int z = 8 + my.nextInt(16); while (1) { it++; FindBestStraightCut(); c_o[7]++; if ((it >= z) || Elapsed() > GTL) break; } if (bestRatioFound > 1e9) { RevertSolution(); continue; } solution.push_back(bestCutFound); savedEdgeSum += ApplyLine(bestCutFound.first); ApplyMaskToSeparated(bestCutFound.second); } }
うまくパート1とコードを共用している。
パート3は影響が小さいので省略。
FindBestStraightCut()とApplyLine()が重要なところだが、難しくて理解できなかった・・・。
Topcoder Open 2016 Marathon Match(Round 2)勉強メモ
前回の続き。上位者のコードで勉強したメモ。
- Psyhoさんのコード
http://pastebin.com/GQV4yrDj
UFOモードではモンテカルロシミュレーション、TSPモードではGreedyに経路を決めたあとに焼きなまししているようだ。TSP部分だけ読んでみる。→Greedy部分は（実行はしてるけど）使ってない。ローカル用か？
情報の持ち方（TSP関連のみ）
int PNO; // Starの数 PII PP[MAX_STARS]; // Star double PD[MAX_STARS][MAX_STARS+4]; // Star i と j の距離。UFOが通るところは0にする int PN[MAX_STARS][MAX_STARS]; // Star i から j 番目に近い星 int PO[MAX_STARS][MAX_STARS]; // Star i からみて j が 何番目に近いか double OPD[MAX_STARS][MAX_STARS+4]; // PDと同じだがUFO経路は無視 int PC[MAX_STARS][MAX_NEIGHBOURS]; // Star i から近い順の星、未到着のもののみ PII PPOS[MAX_STARS]; // 各星について、[船ID、航路Idx]のペア int SNO; // Shipの数 int UNO; // UFOの数 int vs[MAX_STARS]; // すでに訪れた星のフラグ int vscopy[MAX_STARS]; int TPATH[MAX_STARS+10]; // ワーク int PATH[MAX_SHIPS][MAX_STARS+10]; // 船ごとのPath int PATHLEN[MAX_SHIPS]; // 船ごとのPathの長さ int BPATH[MAX_SHIPS][MAX_STARS+10]; // PATHと同じ。焼きなましのベストのやつ int BPATHLEN[MAX_SHIPS]; // PATHLENと同じ。焼きなましのベスト
StarやUFOのクラスを作ったりせず、単純に配列の組み合わせで保存している。また、距離情報＋近い星の情報は初期化時にすべて作ってしまっているようだ。
Greedyの部分
// pos: 船の位置 // planets: 未到着の星、シャッフル済 // 返り値は距離の合計 double greedy(VI pos, VI planets) { double rv = 0; REP(s, SNO) { PATHLEN[s] = 1; PATH[s][0] = pos[0]; } while (planets.S) { double bv = 1e30; // ベストな増加距離 int bs = -1; // 更新する船 int bp = -1; // 挿入するPathの位置 int bi = -1; // 挿入する星 REP(s, SNO) FOR(p, 1, PATHLEN[s]+1) REP(i, planets.S) { double av = 0; av += PD[PATH[s][p-1]][planets[i]]; if (p < PATHLEN[s]) av += PD[PATH[s][p]][planets[i]]; if (av < bv) { bv = av; bs = s; bp = p; bi = i; } } PATHLEN[bs]++; for (int i = PATHLEN[bs]; i > bp; i--) PATH[bs][i] = PATH[bs][i-1]; PATH[bs][bp] = planets[bi]; rv += bv; planets[bi] = planets.back(); planets.pop_back(); } return rv; }
距離増加が最小になるように、星を船の航路に挿入している。
焼きなましの部分
while (true) { if ((steps & 1023) == 0) { if (notVisited.S == 1) break; timePassed = (getTime() - startTime) / (TIME_LIMIT - totalTime); temp = (1.0 - pow(timePassed, 0.15)) * 160; if (timePassed >= 1.0) break; } steps++; // s0： ランダムに選んだ船、p0: s0のPathのIdx（ランダム） int s0 = rng.next(SNO); if (PATHLEN[s0] == 1) continue; int p0 = rng.next(1, PATHLEN[s0]); // s1： 船、p1: s1のPathのIdx int p1, s1; int mode = rng.rand() & 1; if (mode == 0) { // 半分の確率でs0/p0の近くの星から選ぶ PII p = PPOS[PC[PATH[s0][p0]][rng.next(NEIGHBOURS)]]; s1 = p.X; p1 = p.Y; } else { p1 = 0; // 半分の確率で適当な船を選ぶ。p1はあとで s1 = rng.next(SNO); } int p0b, p1b; int type; //ちなみにp0、p1はかならず1以上。Path[0]は現在地なので無視。->Path操作がラクになる double diff = 0; if (s0 == s1) { if (p1 == 0) p1 = rng.next(1, PATHLEN[s0]); type = rng.next(2) == 0; if (type == 0) { // p0とp1を交換 if (p0 == p1) continue; if (p0 > p1) swap(p0, p1); diff -= pathDist(s0, p0-1, PATH[s0][p0]); diff -= pathDist(s0, p1+1, PATH[s0][p1]); diff += pathDist(s0, p0-1, PATH[s0][p1]); diff += pathDist(s0, p1+1, PATH[s0][p0]); } else { // p0をp1の前に挿入 if (abs(p0-p1)<=2) continue; diff -= pathDist(s0, p0-1, PATH[s0][p0]); diff -= pathDist(s0, p0+1, PATH[s0][p0]); diff += pathDist(s0, p0+1, PATH[s0][p0-1]); diff -= pathDist(s0, p1, PATH[s0][p1-1]); diff += pathDist(s0, p1-1, PATH[s0][p0]); diff += pathDist(s0, p1, PATH[s0][p0]); } } else { type = rng.next(2) == 0; if (type == 0) { // 半分の確率で(p0b, p0) と (p1b, p1) を入れ替える // { p0b -> a -> b -> p0 }, { p1b -> x -> y -> p1 } これを // { p0b -> x -> y -> p0 }, { p1b -> a -> b -> p1 } こうする if (PATHLEN[s1] == 1) continue; if (p1 == 0) p1 = rng.next(1, PATHLEN[s1]); p0b = rng.next(1, PATHLEN[s0]); p1b = rng.next(1, PATHLEN[s1]); if (p0 > p0b) swap(p0, p0b); if (p1 > p1b) swap(p1, p1b); diff -= pathDist(s0, p0-1, PATH[s0][p0]); diff -= pathDist(s0, p0b+1, PATH[s0][p0b]); diff += pathDist(s0, p0-1, PATH[s1][p1]); diff += pathDist(s0, p0b+1, PATH[s1][p1b]); diff -= pathDist(s1, p1-1, PATH[s1][p1]); diff -= pathDist(s1, p1b+1, PATH[s1][p1b]); diff += pathDist(s1, p1-1, PATH[s0][p0]); diff += pathDist(s1, p1b+1, PATH[s0][p0b]); } else { // 半分の確率で、２つの航路を途中で切り替えている p1 = p1 == 0 ? rng.next(1, PATHLEN[s1]+1) : p1 + 1; if (rng.next(2)) { // ここはよくわからない・・・未使用の星ができてしまうような・・・ p0b = rng.next(1, PATHLEN[s0]); if (p0 > p0b) swap(p0, p0b); } else { // { a -> b -> p0 -> c -> d }, { p -> q -> p1 -> r -> s } これを // { a -> b -> p0 -> r -> s }, { p -> q -> p1 -> c -> d } こうする p0b = p0; } p1b = p1-1; diff -= pathDist(s0, p0-1, PATH[s0][p0]); diff -= pathDist(s0, p0b+1, PATH[s0][p0b]); diff += pathDist(s0, p0b+1, PATH[s0][p0-1]); diff -= pathDist(s1, p1, PATH[s1][p1-1]); diff += pathDist(s1, p1-1, PATH[s0][p0]); diff += pathDist(s1, p1, PATH[s0][p0b]); } } if (diff <= rng.nextDouble() * temp) { if (s0 == s1) { if (type == 0) { // p0とp1を交換ということは、[p0, p1]を反転させるということ reverse(PATH[s0]+p0, PATH[s0]+p1+1); updatePPOS(s0, p0, p1); } else { int tmp = PATH[s0][p0]; if (p0 < p1) { FOR(i, p0, p1-1) PATH[s0][i] = PATH[s0][i+1]; PATH[s0][p1-1] = tmp; } else { for (int i = p0; i > p1; i--) PATH[s0][i] = PATH[s0][i-1]; PATH[s0][p1] = tmp; } updatePPOS(s0, p0, p1); } } else { if (p0b-p0>p1b-p1) { swap(s0, s1); swap(p0, p1); swap(p0b, p1b); } int move = (p1b-p1)-(p0b-p0); assert(move >= 0); FOR(i, p0, p0b+1) TPATH[i] = PATH[s0][i]; PATHLEN[s0] += move; PATHLEN[s1] -= move; assert(PATHLEN[s0] <= turnsLeft+1); assert(PATHLEN[s1] <= turnsLeft+1); for (int i = PATHLEN[s0]-1; i >= p0b+1+move; i--) PATH[s0][i] = PATH[s0][i-move]; //TODO: fix FOR(i, p1, p1b+1) PATH[s0][i-p1+p0] = PATH[s1][i]; FOR(i, p0, p0b+1) PATH[s1][i-p0+p1] = TPATH[i]; FOR(i, p1b+1-move, PATHLEN[s1]) PATH[s1][i] = PATH[s1][i+move]; updatePPOS(s0, p0, PATHLEN[s0]-1); updatePPOS(s1, 1, PATHLEN[s1]-1); } PATH[s0][PATHLEN[s0]] = PNO; PATH[s1][PATHLEN[s1]] = PNO; bv += diff; acc++; // ベスト経路を取っておく if (bv < xv) { xv = bv; bestacc++; REP(s, SNO) { BPATHLEN[s] = PATHLEN[s]; REP(i, PATHLEN[s]) BPATH[s][i] = PATH[s][i]; } } } }
コスト差分は予め計算しておいた距離を使ってやっている。経路は静的配列で持ち、ループで更新している。
Seed=2（船が１槽でUFOなし）で挙動を計測してみた。
温度と更新頻度のプロット。後半はほとんど更新されなくなっている。
およびスコアのプロット。前半に一気に改善して、だんだんなだらかになっている。スコアが悪化する場合もあるはずだが、プロット数をかなり減らしているので見えていない（データを取ってるのが0xFFF回に一回だけなので）。
航路変更によるスコア（距離）差分が、平均190（最小-130、最大1100、標準偏差180）くらい。
if (diff <= rng.nextDouble() * temp) {
遷移条件がこれ。コスト差分量によって遷移確率が異なる。
ループ総数3800万回のうち、遷移したのが130万回ほど。悪化したのに遷移したのは70万回ほどだった。
Topcoder Open 2016 Marathon Match(Round 2)の参加日記
62位/183人の定位置だった。そろそろ一皮剥けたいものだ。
問題概要
- 二次元平面（1024x1024）に星が100~2000個ある
- 星の場所に、ランダムに船が1~10隻ある
- 星の場所に、ランダムにUFOが0~(星の数/100)個ある
- 1ターンごとに船を動かすことができる
- 1つのターンでいくつの船を、どの星に動かしても良い（同じ星もOK）
- 1つの星に何度でも到着してよい
- 星は、どの船でも1回以上訪れていれば、到着済みになる
- ただし、最初のターンに船がいる星は未到着扱い
- UFOも1ターンごとにランダムに動く
- 1ターンごと、UFOの現在地・次の星・次の次の星が与えられる
- ターン数の上限は星の数x4
- ターン上限までにすべての星が到着済になるよう、ターンごとに船に指示を与えるのが目的
- ただし、船の移動コスト合計はなるべく小さくしたい
- 移動コストは基本的に移動距離と同じ
- ただし、もし船の航路とUFOの航路が同じなら、移動コストは距離x（1/1000＾同航路のUFOの数）になる
- 星の位置は完全にランダムではない。いくつか(1~16)の銀河が存在し、星は各銀河の中心から正規分布している
- またUFOごとに飛び方に特徴がある。UFOは星を全体からN個ランダムに選んで、その中の最も近いものに飛ぶが、Nの値はUFO固有(10~10+星の数/10)
https://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=16703&pm=14268
方針
- UFOが近く(距離100くらい)にくるのを待ってから乗る。なかなか来なかったら最も近いものに乗ってしまう
- 残りターンが少なくなるまで乗り続ける。同じ星に良さそうな別UFOがいたら乗り換える
- UFO未到着の星で巡回セールスマン（Nearest Neighborのあと、貪欲的に改善)
巡回セールスマンは焼きなましで組んでみたが、どうもうまく動かず断念した。
上位との比較
- 全体的な方針は一緒
- TS部分で大きな差がついていそう
- TSは焼きなましの人と、NNのあと2.5optなどTSP特有のアルゴリズムがいる
- 最上位の方たちは、UFOランデブーもかなり注意深いロジックを組んでいる。UFOの挙動から特徴を推定・シミュレーションして、gain/costを判断してたり
Psyhoさん(暫定1位)のコード http://pastebin.com/GQV4yrDj
（UFOランデブーではモンテカルロシミュレーション、TSでは焼きなましを使ってるらしい）
気づかなかったこと＋実装できなかったこと
- TSパートでもUFOが使えるのに気づかなかった（特に最初に１手）
- UFOから降りるとき、未到着の星の近くで降りのも良い考えだった
- 別UFOと重なったときの判断に、UFOごとの統計情報が使えた
- 最初の1手で船を動かさない場合、その星は到着済扱いだった
反省点
焼きなましを練習しよう。
