[AGC061] A - Long Shuffle
[Q] https://atcoder.jp/contests/agc061/tasks/agc061_a
173分使ってギリギリ抜きましたが腑に落ちていないので、せめて整理します。この解法は全く優れていません。
・考察
1. 問題文通りの実装を行って、N=34くらい表示する。
N: K
------
2: 2 1
3: 2 3 1
4: 2 1 4 3
5: 2 4 1 5 3
6: 2 1 3 4 6 5
7: 2 3 1 4 6 7 5
8: 2 1 4 3 6 5 8 7
9: 2 4 1 6 3 8 5 9 7
10: 2 1 3 4 5 6 7 8 10 9
11: 2 3 1 4 5 6 7 8 10 11 9
12: 2 1 4 3 5 6 7 8 10 9 12 11
13: 2 4 1 5 3 6 7 8 10 12 9 13 11
14: 2 1 3 4 6 5 7 8 10 9 11 12 14 13
15: 2 3 1 4 6 7 5 8 10 11 9 12 14 15 13
16: 2 1 4 3 6 5 8 7 10 9 12 11 14 13 16 15
17: 2 4 1 6 3 8 5 10 7 12 9 14 11 16 13 17 15
18: 2 1 3 4 5 6 7 8 9 10 11 12 13 14 15 16 18 17
19: 2 3 1 4 5 6 7 8 9 10 11 12 13 14 15 16 18 19 17
20: 2 1 4 3 5 6 7 8 9 10 11 12 13 14 15 16 18 17 20 19
21: 2 4 1 5 3 6 7 8 9 10 11 12 13 14 15 16 18 20 17 21 19
22: 2 1 3 4 6 5 7 8 9 10 11 12 13 14 15 16 18 17 19 20 22 21
23: 2 3 1 4 6 7 5 8 9 10 11 12 13 14 15 16 18 19 17 20 22 23 21
24: 2 1 4 3 6 5 8 7 9 10 11 12 13 14 15 16 18 17 20 19 22 21 24 23
...2. よく観察し、すぐに特定できる法則を見つけると、
a. 行の先頭が2,2,2,2,2,…
b. 行の末尾だけ見ると、1,1,3,3,5,5,…
c. 行の末尾から1つ前を見ると、2,3,4,5,6,…
しかし、これ以上見つけられない。
大きな特徴として、数字の移動が極めて少ないことがわかった。
3. もとの数列との差分を出して考察する。
2: 1 -1
3: 1 1 -2
4: 1 -1 1 -1
5: 1 2 -2 1 -2
6: 1 -1 0 0 1 -1
7: 1 1 -2 0 1 1 -2
8: 1 -1 1 -1 1 -1 1 -1
9: 1 2 -2 2 -2 2 -2 1 -2
10: 1 -1 0 0 0 0 0 0 1 -1
11: 1 1 -2 0 0 0 0 0 1 1 -2
12: 1 -1 1 -1 0 0 0 0 1 -1 1 -1
13: 1 2 -2 1 -2 0 0 0 1 2 -2 1 -2
14: 1 -1 0 0 1 -1 0 0 1 -1 0 0 1 -1
15: 1 1 -2 0 1 1 -2 0 1 1 -2 0 1 1 -2
16: 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1
17: 1 2 -2 2 -2 2 -2 2 -2 2 -2 2 -2 2 -2 1 -2
18: 1 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 -1
19: 1 1 -2 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 -2
20: 1 -1 1 -1 0 0 0 0 0 0 0 0 0 0 0 0 1 -1 1 -1
21: 1 2 -2 1 -2 0 0 0 0 0 0 0 0 0 0 0 1 2 -2 1 -2
22: 1 -1 0 0 1 -1 0 0 0 0 0 0 0 0 0 0 1 -1 0 0 1 -1
23: 1 1 -2 0 1 1 -2 0 0 0 0 0 0 0 0 0 1 1 -2 0 1 1 -2
24: 1 -1 1 -1 1 -1 1 -1 0 0 0 0 0 0 0 0 1 -1 1 -1 1 -1 1 -1
25: 1 2 -2 2 -2 2 -2 1 -2 0 0 0 0 0 0 0 1 2 -2 2 -2 2 -2 1 -2
26: 1 -1 0 0 0 0 0 0 1 -1 0 0 0 0 0 0 1 -1 0 0 0 0 0 0 1 -1
27: 1 1 -2 0 0 0 0 0 1 1 -2 0 0 0 0 0 1 1 -2 0 0 0 0 0 1 1 -2
28: 1 -1 1 -1 0 0 0 0 1 -1 1 -1 0 0 0 0 1 -1 1 -1 0 0 0 0 1 -1 1 -1
29: 1 2 -2 1 -2 0 0 0 1 2 -2 1 -2 0 0 0 1 2 -2 1 -2 0 0 0 1 2 -2 1 -2
30: 1 -1 0 0 1 -1 0 0 1 -1 0 0 1 -1 0 0 1 -1 0 0 1 -1 0 0 1 -1 0 0 1 -1
31: 1 1 -2 0 1 1 -2 0 1 1 -2 0 1 1 -2 0 1 1 -2 0 1 1 -2 0 1 1 -2 0 1 1 -2
32: 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1
33: 1 2 -2 2 -2 2 -2 2 -2 2 -2 2 -2 2 -2 2 -2 2 -2 2 -2 2 -2 2 -2 2 -2 2 -2 2 -2 1 -2
34: 1 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 -1 すると、-2,-1,0,1,2の5要素で構成されていることがわかる。それぞれが特定できればよい。
0だけ抽出すると、シェルピンスキーのギャスケットみたいなものが現れる。
これは頑張れば特定できる。
辺が2の三角形({(6, 3), (6, 4), (7, 4)})は、8*8周期で出現している。
辺が6の三角形は、16*16周期で出現している。
辺が14の三角形は、32*32周期で出現している。
辺が2^n - 2 の三角形は、2^(n + 1)周期で出現している。
同様に
-> 0の特定
-> -1の特定
-> 1の一部を特定
-> -2を特定
-> 2を特定
-> 残りは全部1
として進めた。
・実装
https://atcoder.jp/contests/agc061/submissions/38849309