第3回RCO日本橋ハーフマラソン（予選）に参加した話
今更ながら第３回日本橋ハーフマラソン予選に参加してA問題を解いた話です。初めてのハーフマラソンで、よくわからないまま中途半端な時間に参加してとりあえずコードを提出した感じでした。その後に参加者が招待されるリクルート全体の社員LT大会なるものがあり、競技プログラミングを始めてから、初めて参加者に会える機会で嬉しいという感じでそちらもエントリーしました。そのLT大会で「ところでどうやって解いた？」って聞かれるとやばい、と思ったので、A問題だけですが、LT大会前にちょっとでもと思い精度をあげて行きました。
ハーフマラソンに参加したときのアルゴリズムは本当にポンコツ（Nearest Neighbor法を利用しました）で、スコアがほぼ最低点の2507だったのですが、巡回セールスマン問題の単純な精度改善アルゴリズムである2-optという方法を参考にして、精度を改善した結果、28万くらいまで上がりました。（全体の順位としてはこれで半分くらいだと思います。）
※※※注意 これは高い精度の人のブログではないです こういう解き方でこれくらいの結果になるんだなと指標になれば嬉しいです。 Javaで書いたコードも載せています。
「こうやったらいいよ〜」とか、「ここはどうしてこうなの？」とかあれば、ご指摘とか質問とか大歓迎です:) どうぞよろしくお願いします。
問題概要
200個の都市を1日１都市ずつ、1日の移動距離がなるべく同じになるような都市の巡り方を探索するコードを提出します。つまり、各移動距離が全体の移動距離の平均からあまり離れないようなルートを選択すると良いということです。
方針
- まず、適当に選んだ初期位置から、Nearest Neighbor法で貪欲に平均との差が一番小さいノードを採用していくことを全ノードに対して繰り返していき、最初の順番とします。（このまま出すとスコア2507です）
- 精度を上げるためにランダムに二つのノードを選びswapします。2-optではノードではなくエッジを選択しますが、実装を簡単にするためにノードでやってみました。
- swap前とswap後で評価値が低い（低い方が良い）ものを採用して、採用した順番に対して操作2を行います。
- 時間の許す限り2,3を繰り返し、良い評価値のものを採用していきます。
コード
import java.util.*;
class Main {
static HashSet<Integer> set = new HashSet<Integer>();
static double[][] d;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int[] x = new int[N];
int[] y = new int[N];
d = new double[N][N];
double[][] offset = new double[N][N];
for(int i = 0; i<N; i++) {
x[i] = sc.nextInt();
y[i] = sc.nextInt();
set.add(i);
}
//ノード間距離の平均値を抽出
double ave = 0;
for(int i = 0; i<N; i++) {
for(int j = 0; j<N; j++) {
d[i][j] = Math.sqrt(Math.pow(x[i] -x[j],2) + Math.pow(y[i] -y[j],2));
ave += d[i][j];
}
}
ave = ave/N;
// ノード間の平均との差を計算する
for(int i = 0; i <N; i++) {
for(int j = 0; j<N; j++) {
offset[i][j] = Math.abs(d[i][j] -ave);
}
}
// nearest neightborで順番を決定
int[] a = new int[N];
a[0] = 0;
set.remove(0);
for(int i = 1; i<N; i++) {
a[i] = searchNextI(a[i-1], offset);
}
Random rnd = new Random(1000);
// 時間の許す限りできるだけ多くswapする
int[] ans = a;
int cnt = 0;
while(cnt<600000) {
int x1 = rnd.nextInt(N);
int x2 = rnd.nextInt(N);
int[] b = makeNewArray(ans,x1,x2);
ans = (calcEval(ans)<calcEval(b))?ans:b;
cnt++;
}
for(int i = 0; i<N; i++) {
System.out.println(ans[i]);
}
}
// arrayを複製してx1,x2番目のノードをswapしたものを返す
public static int[] makeNewArray(int[] a,int x1,int x2) {
int[] b = new int[a.length];
for(int i = 0; i < a.length; i++) {
b[i] = a[i];
}
b[x1] = a[x2];
b[x2] = a[x1];
return b;
}
// arrayの順番でのスコアを計算して返す。
public static double calcEval(int[] a) {
double val = 0;
double ave = 0;
// aveの計算
for(int i = 0; i<a.length; i++) {
if(i==a.length-1) {
ave += d[a[i]][a[0]];
} else {
ave += d[a[i]][a[i+1]];
}
}
ave = ave/a.length;
// 評価値の計算
for(int i = 0; i<a.length; i++) {
if(i==a.length-1) {
val += Math.abs(d[a[i]][a[0]]-ave);
} else {
val += Math.abs(d[a[i]][a[i+1]]-ave);
}
}
return val;
}
// 現在の位置から最も平均的な距離で到達できるノードのインデックスを返す関数
public static int searchNextI(int curI, double[][] offset) {
if(set.size() == 0) return -1;
double min = Integer.MAX_VALUE;
int minI = 0;
for(int i = 0; i<offset.length; i++) {
if(curI != i && set.contains(i)) {
if(min > offset[curI][i]) {
min = offset[curI][i];
minI = i;
}
}
}
set.remove(minI);
return minI;
}
}
感想
今回は移動距離の分散が小さくなるようにという制約だったのでよくわかりませんが、2-optのようにエッジをswapするのではなく、私が採用したノード二つをswapするやり方だと、交差が増えるもしくは減らないことが多いので移動距離の総和が評価値の時には使えないなと思いました。
TLEのときの申し訳なさは半端ないです。途中で止めれるような機能があったらいいと思います。
問題２についてはLT大会前に確認しましたが、これはもしやDFS..!と思ってそっ閉じしました。土日とかで時間があるときにやってみる予定です。
LT大会に関して
私が参考にしたことがあるサイトの著者さんとtwitterを交換できました。競技プログラミングの話はあまり多くの人とできていないので、とても楽しかったです。リクルート全体で開かれたLTの内容は就活生向けで会社紹介や環境紹介のものが多かった印象でした。（就活生に声がかかったようですね）私はもう少し技術的な話の割合が多くてもよかったかなとも思ったけど、仕事の成果物のデモとか見せてもらえたのが面白かったです。あと個別で社員さんとずっと興味のあった技術の話が聞けて面白かったです!
