MC Digital プログラミングコンテスト2022（AtCoder Heuristic Contest 008）
暫定27位/827でした。黄パフォえらい。
[Q] https://atcoder.jp/contests/ahc008/tasks/ahc008_a
1. 固定盤面を作っちゃう。
円型にしたのは、
・外壁を使った穴数を多くしたかった
・導線をスムーズにしたかった
から。
直線よりも、斜めに置くほうがちょっと効率よさそうでした。
見取り図と、導線をべた書き。
void saku33() {
// 012345678901234567890123456789
saku[+0] = "#..#..#..#..#..#..#..#..#..#..";
saku[+1] = ".#..#..#..#..#.#.#..#..#..#..#";
saku[+2] = "..#..#..#..#.......#..#..#..#.";
saku[+3] = "#..#..#..#...........#..#..#..";
saku[+4] = ".#..#..#.......###.....#..#..#";
saku[+5] = "..#..#.......#....#......#..#.";
saku[+6] = "#..#.......#..#..#..#...#..#..";
saku[+7] = ".#..#....#..#..##..#......#..#";
saku[+8] = "..#....#..#..#.#..#..#...#..#.";
saku[+9] = "#..#....#..#..#..#..#......#..";
saku[10] = ".#....#..#..#..##..#..#...#..#";
saku[11] = "..#....#..#..#.#..#..#......#.";
saku[12] = "#....#..#..#..#..#..#..#...#..";
saku[13] = ".#....#..#..#..##..#..#......#";
saku[14] = "....#..#..#..#..#.##.#..#...#.";
saku[15] = "..#..#.##.##.##..#..#..##.....";
saku[16] = ".#....#..#..#..#..#..##..#..#.";
saku[17] = "#..#....#..#..#.#..#..#..#...#";
saku[18] = "..#....#..#..#..##..#..#...#..";
saku[19] = ".#..#....#..#..#..#..#......#.";
saku[20] = "#..#....#..#..#.#..#..#...#..#";
saku[21] = "..#..#....#..#..##..#......#..";
saku[22] = ".#..#.......#..#..#..#...#..#.";
saku[23] = "#..#..#.......#.#..#......#..#";
saku[24] = "..#..#..#........#......#..#..";
saku[25] = ".#..#..#..#....##.....#..#..#.";
saku[26] = "#..#..#..#..#.......#..#..#..#";
saku[27] = "..#..#..#..#..#...#..#..#..#..";
saku[28] = ".#..#..#..#..#..#..#..#..#..#.";
saku[29] = "#..#..#..#..#....#..#..#..#..#";
}
void root33() {
// 012345678901234567890123456789
root[+0] = "#RRD..#..#..#..#..#..#..#..#..";
root[+1] = ".U.RRRRRRRRRD#.DLLLLLLLLLLLLL#";
root[+2] = ".U#..#..#..#D..D...#..#..#..U.";
root[+3] = "#U.#DLLLLLLLL..RRRRRRRRRRD.#U.";
root[+4] = ".U..D..#.......###.....#.D#.U#";
root[+5] = ".U#.D#......RRRRRD#......D..U.";
root[+6] = "#U.#D......#U.#..D..#...#RD#U.";
root[+7] = ".U..D...D#..ULL##D.#......D.U#";
root[+8] = ".U#.D..#D.x..#U#.RRRD#...#D.U.";
root[+9] = "#U.#!...D..x..U..#..D.....!#U.";
root[10] = ".U...!#.D#.Lx.ULLL.#RD#...#.U#";
root[11] = ".U#..U.#D.x..x.#.U#..D......U.";
root[12] = "#U...U..D..x..x..U..#RRRD..#U.";
root[13] = ".U...U#.D#..x..x#U.#..#.D...U#";
root[14] = "....#UL#D.#..x..xLLLLLL.D...U.";
root[15] = ".D#..#U#RRRRD#x..x..#.U#D.....";
root[16] = ".D....U..#..D..x..x..#U.D#..#.";
root[17] = "#D.#..ULLL.#D.#.x..x..U.!#..D#";
root[18] = ".D#!...#.U#.RRRD#x.Dx.U#...#D.";
root[19] = ".D.U#....U..#..D..xRRRU.....D.";
root[20] = "#D.U....#ULLLL#D#..x..#...#.D#";
root[21] = ".D#U.#....#..U.D##..x.....!#D.";
root[22] = ".D.ULLLL....#U.RRRRRD#...#U.D.";
root[23] = "#D.#..#U.....U#.#..#D.....U.D#";
root[24] = ".D#.RRRU#....ULLLLLLL...#RU#D.";
root[25] = ".D..U..#..#....##.....#..U..D.";
root[26] = "#D.#ULLLLLLLLL...RRRRRRRRU#.D#";
root[27] = ".D#..#..#..#.U#..U#..#..#..#D.";
root[28] = ".D.RRRRRRRRRRU..#ULLLLLLLLL.D.";
root[29] = "#RRU..#..#..#....#..#..#..ULL#";
}
2. プレイヤーの行動パターン
1) 捕まえられるなら、捕まえちゃう(深さ2までのバックトラック)
2) 最小コストで、ペットと人を1対1に繋ぎ、粘着させる。
です。
3. 犬どうする？
A. seed80
最初に、画面中央に筒を作り、両端に集まります。
捕まえられるタイミングを待ち、捕え次第固定盤面に移ります。
画面の中央を見てて。
「今です！」
運が悪いと80ターン近く待機させられ大事故。
Q. 全部捕まえられた？
A.
77/100でパーフェクトゲームでした。
20/100で1-2匹のこり。猫が逃げます。
3/100で大事故。これは犬待ちが長すぎるなど。
seed/M/N/dog/cat/score
45 19 7 4 2:1791667
29 17 5 1 1:1850694
61 15 5 3 1:7638889
84 17 5 5 2:15000000
17 13 5 4 2:15916667
71 10 5 2 3:16027778
50 18 5 1 6:21777778
91 20 7 5 2:23222222
70 20 5 0 5:27111111
34 20 5 4 4:27500000
85 19 7 3 5:28000000
15 20 10 1 6:28055556
86 19 8 0 5:28333333
48 20 8 5 2:29000000
57 15 6 4 1:29500000
60 18 10 4 2:29555556
72 20 6 5 4:29777778
25 14 10 2 4:29888889
56 16 5 3 5:30055556
44 13 5 3 2:30277778
81 16 8 5 2:30277778
6 15 6 5 1:30500000
9 17 5 5 5:30500000
58 15 10 5 2:30555556
32 13 5 3 4:30722222
69 14 5 5 3:30944444
62 16 6 2 5:33777778
53 12 6 2 0:50000000
51 19 5 2 6:53666667
2 19 7 3 5:53777778
39 20 10 2 6:54000000
1 20 6 4 4:54222222
18 16 9 2 3:55555556
92 19 7 2 6:55888889
46 19 9 3 6:56111111
59 19 6 5 6:56222222
75 20 10 6 4:56444444
40 16 7 2 2:56555556
5 17 10 2 1:57000000
14 20 10 4 3:57000000
7 16 8 2 4:57222222
99 19 8 6 3:57777778
28 18 9 4 5:57888889
97 15 10 1 4:58000000
30 18 7 5 4:58111111
65 17 8 3 4:58222222
23 17 5 3 1:58333333
77 12 9 0 3:58444444
79 13 9 1 3:58444444
64 17 7 4 3:58444444
36 12 8 0 2:58555556
83 19 8 6 4:58555556
54 13 8 3 0:58666667
12 18 8 6 2:58888889
19 14 8 1 2:59000000
90 15 6 2 5:59000000
22 15 7 3 1:59111111
20 12 6 0 2:59333333
24 16 6 4 3:59333333
47 13 6 0 3:59444444
88 12 8 1 2:59555556
95 14 7 4 3:59555556
66 15 8 1 8:59555556
8 15 10 1 4:59555556
42 13 7 1 2:59666667
11 18 9 5 4:59666667
13 16 10 4 4:59888889
3 13 5 3 1:60000000
76 13 7 2 3:60000000
80 16 7 6 3:60000000
43 14 5 4 1:60444444
38 14 8 4 3:60666667
52 12 8 3 2:60777778
10 11 10 2 2:61000000
68 11 7 2 2:61111111
63 17 9 5 2:61111111
35 11 7 0 3:61222222
78 11 7 1 3:61222222
94 12 7 3 3:61222222
31 10 9 2 2:61555556
87 11 9 2 5:61777778
98 10 6 2 2:61888889
96 10 7 1 4:61888889
0 10 5 0 0:62000000
26 15 10 5 4:62111111
67 10 7 2 2:62222222
73 11 10 1 3:62222222
4 10 7 3 2:62555556
49 11 8 4 1:62555556
33 10 9 2 1:62666667
21 11 5 2 1:62777778
37 12 8 2 5:62777778
93 12 8 5 1:62777778
55 13 6 5 3:62777778
27 12 6 5 2:63333333
16 10 10 3 1:63777778
41 13 10 6 0:63888889
89 12 5 4 1:64000000
74 11 8 4 2:64444444
82 10 10 5 1:64555556
5019559033