March 15, 2019

第3回 RCO日本橋ハーフマラソン予選 B ファーマーXの収穫計画

Approach 無効な状態を許容する焼きなまし法です。

近傍 : １つマスを選んで、そのマスの数字を元の数字にもどす、または隣のセルの数字と同じ数字にする
- １つマスを選んで数字を±1する近傍で、探索空間が連結になるので、これでいいかなと思っていたら、上のの方が良かった。
ペナルティー : max(0,操作数 - M) の２乗
数字が１のマスを収穫しない。

March 10, 2019

第3回 RCO日本橋ハーフマラソン本戦 A めくってそろえる

Approach 解説とほとんど同じです。

今いる場所が不明箇所なら開ける
最も近いペアを作る、または最も近い不明箇所を開ける
- (最も近い不明箇所の距離 * 3.1 < 最も近いペアの距離 ? 不明箇所 : ペア) を選ぶ
- 同じ距離なら中心に近い方を選ぶ
バタフライ効果が見られる。テストケース 50 個は少ない。

March 10, 2019

第3回 RCO日本橋ハーフマラソン本戦 B まわしてそろえる

Approach ビームサーチです。

各点の重み : (1 << 3 * 中心からのチェビシェフ距離)
この後、対角線上の点なら 4 倍、その隣なら 2 倍する。
評価関数 : 各点ごとに、合ってたら 1 ,違ってたら -1 を重みに掛けて和をとる。
この評価関数は、外側からそろえる。
次の深さのノードの作り方 : バウンディングボックスに完全に含まれるまわし方で、バウンディングボックスの端またはその一つ内側を含むものに限定
重複除去に Zobrist hashing
- 現在の深さのノード群を評価が良い順に見ていくときに除去する方法と、次の深さのノードを作るときに除去する方法が有ると思いますが、今回は前者を使いました。ハッシュセットを使わずに、評価とハッシュで並べ替えて、直前のノードと同じハッシュなら除去した。
ビーム幅 : 残り時間を275等分して、各深さごとできるだけ多くノードを見る。最初の方は１とか２で、最後の方は３桁くらい。
たまに完全解にならない

うまくいった時 208手(input_1.txt)

1 0 19
10 10 10
3 1 17
9 0 11
0 1 8
9 6 11
16 17 3
11 9 9
11 9 9
0 9 7
2 10 10
18 1 2
1 1 18
4 16 4
0 18 2
9 0 2
6 0 3
1 6 13
0 10 2
0 13 3
6 17 3
3 2 16
14 0 3
17 11 3
3 1 13
18 13 2
7 0 3
2 0 2
1 8 8
0 11 3
1 1 8
3 1 15
6 1 8
12 0 2
13 10 6
14 18 2
14 18 2
14 18 2
6 8 11
12 1 4
7 8 11
2 2 15
1 13 6
1 10 6
1 4 4
16 1 4
16 1 4
16 1 4
6 16 3
9 17 2
14 1 4
14 1 3
2 3 14
1 5 4
12 3 7
4 1 3
14 8 5
14 8 5
3 16 3
11 1 3
7 2 11
16 6 3
15 17 2
17 12 2
5 6 12
13 17 2
4 2 13
6 1 3
2 10 8
5 4 13
7 3 11
14 1 4
13 3 5
13 3 5
9 12 6
9 12 6
10 16 3
6 2 6
8 17 2
8 17 2
2 5 6
2 5 6
3 3 14
3 3 13
16 2 2
2 15 2
2 11 4
3 4 13
15 13 3
12 14 4
3 10 8
3 10 8
8 2 2
10 2 2
6 2 2
7 15 3
5 3 12
16 11 2
13 8 4
11 3 6
5 13 4
5 15 3
4 3 3
4 2 3
13 3 3
3 4 11
2 11 5
12 14 3
12 14 3
14 13 3
7 15 2
8 8 8
13 5 4
13 7 4
13 15 2
3 14 3
3 4 2
4 4 6
6 3 3
5 5 11
7 15 2
15 8 2
3 4 3
3 10 6
3 13 2
3 11 2
4 9 6
7 6 9
6 4 10
5 4 8
9 3 3
9 3 3
11 3 5
12 4 4
11 10 5
10 11 5
5 10 6
4 11 4
6 13 3
4 8 5
5 5 9
4 4 2
11 6 5
8 4 5
4 11 2
11 14 2
13 12 3
6 7 8
11 5 5
10 4 2
5 5 9
8 4 2
6 4 2
6 6 9
14 8 2
5 6 5
9 5 4
6 5 4
5 13 2
6 6 8
4 10 4
4 10 4
4 10 4
11 7 4
13 13 2
13 12 2
7 7 7
5 10 3
9 11 4
10 5 2
6 7 7
10 12 3
13 12 2
8 7 6
12 7 3
7 13 2
7 13 2
6 9 5
7 7 6
7 6 5
8 5 2
8 12 2
7 6 5
6 9 4
7 9 4
10 12 2
11 6 2
8 6 3
8 7 4
8 7 3
8 9 4
8 6 2
9 8 4
9 8 4
7 9 3
8 7 2
11 9 2
8 8 3
8 8 2
11 10 2
8 9 3
7 8 2
8 8 3
9 9 3
9 9 3
9 9 2
9 10 2
9 10 2

時間制限10倍うまくいった時 193手(input_1.txt)

1 0 19
10 10 10
3 1 17
9 0 11
0 1 8
9 6 11
16 17 3
11 9 9
11 9 9
3 13 7
0 9 7
0 10 6
18 1 2
0 16 4
0 17 2
1 1 18
9 0 2
6 0 3
4 16 4
16 10 4
1 1 17
14 0 2
7 17 3
2 0 2
12 0 2
0 13 2
7 0 2
3 1 15
7 5 12
17 12 3
18 4 2
1 2 16
5 1 6
1 13 6
3 4 15
13 18 2
3 5 14
15 8 4
1 15 3
2 1 5
2 2 16
4 1 4
1 11 7
5 2 13
12 2 7
2 2 9
1 2 6
2 16 3
14 1 2
11 17 2
17 16 2
6 2 11
16 3 3
12 1 4
2 5 11
1 12 3
8 9 9
10 16 3
1 13 5
14 16 3
2 2 13
13 1 2
2 8 9
2 17 2
2 13 5
6 17 2
6 1 4
2 2 5
6 1 3
12 4 6
16 7 3
11 2 5
3 5 13
3 3 14
5 4 13
11 9 7
12 15 3
2 12 3
3 14 4
3 4 13
7 2 3
3 16 2
4 4 13
15 6 3
7 16 2
4 7 10
11 10 7
16 13 2
6 3 6
16 11 2
3 3 4
2 4 2
11 2 4
11 2 4
11 10 6
3 7 8
2 10 2
2 10 2
3 7 8
5 7 10
9 3 5
10 16 2
10 16 2
5 3 7
9 8 8
9 8 8
4 4 10
3 4 7
3 12 3
10 12 5
4 5 11
4 3 4
4 3 4
3 4 4
12 15 2
5 5 11
15 5 2
6 4 10
14 6 3
4 4 5
3 8 2
4 14 3
4 6 10
6 5 10
4 8 7
6 12 4
5 5 10
13 5 3
6 4 9
4 14 2
4 12 3
6 4 5
5 6 6
7 4 3
10 13 3
4 10 2
4 5 2
5 6 9
13 12 3
10 14 2
6 14 2
6 9 6
5 6 7
10 5 4
6 6 8
4 6 3
5 7 6
7 5 6
9 13 2
10 11 4
12 10 3
7 6 6
7 5 3
7 11 4
8 12 3
6 7 5
5 10 3
10 9 4
5 6 2
6 6 6
9 6 2
6 7 5
10 11 3
8 7 5
12 6 3
12 6 3
12 6 3
8 8 4
10 11 3
8 12 2
9 7 4
10 6 3
9 7 3
9 8 5
9 8 5
7 11 2
7 11 2
9 8 4
9 9 4
7 7 2
11 11 2
8 8 4
8 10 3
8 8 3
10 11 2
10 11 2
9 9 3
8 10 2
8 8 2
8 7 2
8 7 2
8 8 3
9 9 2

時間制限100倍うまくいった時 174手(input_1.txt)

1 0 19
10 10 10
3 1 17
11 0 9
6 3 14
0 1 8
10 6 10
16 17 3
1 1 18
0 17 3
4 15 5
11 0 5
0 9 9
0 9 9
18 9 2
18 9 2
6 0 3
3 18 2
0 13 3
16 12 4
7 0 2
3 1 10
1 5 14
2 0 2
0 13 2
3 18 2
0 10 2
3 6 13
13 18 2
9 1 9
14 0 3
14 0 2
14 10 5
18 13 2
18 13 2
1 1 16
1 3 15
8 9 10
1 2 9
3 1 11
1 8 9
4 1 7
13 3 6
14 3 5
2 2 16
1 13 3
14 13 5
6 1 3
9 9 9
10 16 3
14 5 5
2 3 15
11 2 7
2 2 11
6 1 3
17 6 2
13 1 2
3 4 14
16 10 3
1 5 3
4 17 2
4 4 14
17 15 2
2 10 6
8 6 10
1 13 3
10 11 7
4 4 13
14 4 4
13 2 5
2 4 3
12 15 3
2 11 4
9 2 2
4 3 13
3 3 13
13 9 5
3 8 9
3 14 4
8 6 9
14 4 4
15 2 3
14 12 4
2 5 2
3 4 12
2 10 3
3 3 6
5 7 10
13 15 3
4 3 10
2 7 2
3 3 6
5 4 11
13 8 4
9 11 6
5 3 4
3 5 6
4 4 8
8 3 4
14 6 3
5 13 4
15 13 2
11 3 2
3 12 4
3 12 2
4 4 11
12 14 3
4 6 9
4 4 7
4 8 3
6 5 10
6 14 3
9 11 4
11 11 5
11 11 5
4 14 2
12 6 4
8 5 7
7 4 5
10 8 5
12 11 4
12 12 4
7 4 2
6 14 2
5 5 9
5 7 8
11 5 5
4 12 2
5 7 8
6 4 4
4 5 3
13 4 2
8 5 7
10 6 5
10 11 4
11 8 4
6 6 8
6 6 8
13 9 2
8 7 6
8 5 2
7 5 3
6 6 6
5 10 2
6 7 6
8 6 5
7 8 5
10 11 3
10 8 4
7 6 4
7 6 4
8 11 3
7 7 5
8 11 2
7 8 4
8 7 3
9 8 4
8 10 3
8 8 4
10 7 2
11 8 2
8 8 4
10 7 2
7 9 3
7 9 3
9 8 3
9 9 2
8 9 3
8 9 3
9 10 2
8 9 2
9 8 2
9 9 2
10 9 2