첫 세 문제를 풀어내는 데 좀 많은 시간을 써서, 대회 시간 내에 풀지는 못했지만, 만약 저에게 2시간만 더 있었다면 이 문제를 풀어낼 수 있었을 겁니다...
1. 생각의 시작
일단 간단한 재귀를 생각해보는 것으로 출발했습니다. 대략 두 칸 넘어갈 때마다 횟수가 3배 정도 되는 방법들이 나왔는데, 가장 마지막에 생각했던 간단한 재귀는 다음과 같습니다.
1234567 - - → 127 - 3456 → 1 27 3456 → 13456 27 - → 1 234567 - → - 234567 1 → ...
한편 여기서 중요한 성질들을 조금 잡아냈습니다.
1. 반드시 "1 234567 -"이 되어야만 "- 234567 1"로 넘어가면서 진행할 수 있다.
2. 모든 이동은 가역적이기 때문에, "- - 1234567 → - 234567 1"의 과정은 앞에서 만든 것을 활용할 수 있으므로, 이 과정을 정확히 반대로 수행하면 "- 234567 1 → - - 1234567"을 만들 수 있다.
특히 2번 성질은 구현량을 효과적으로 줄여주기 때문에 매우 중요했습니다.
2. 좌절
위에 나와 있는 재귀의 식을 구해보면
f(n) = 2(g(n) + 2 + h(n)) + 1
g(n) = g(n-2) + 2 + h(n-2)
h(n) = h(n-2) + 1 + f(n-5) + 1 + h(n-2) + 1 + h(n-2)
정도의 식이 나왔습니다. 만점의 희망을 갖고 dp를 계산한 결과는..!
N=23 → 941745, N=24 → 1743913. 140점 정도짜리 풀이가 나왔습니다. 하지만 저는 부분 점수 따위에 만족하고 싶지 않았습니다. 그리고, 사실 "간단한 재귀"라고 했지만 구현이 생각보다 귀찮기 때문에, 완전한 풀이를 만들자고 결심했습니다. 뭐 결과적으로는 이게 실수였던 것 같습니다만... 저는 괜찮습니다. 이미 본선을 네 번이나 나갔기에 미련 없습니다.
3. 규칙 찾기
N=26일 때 만점을 받을 수 있는 길이와의 차이가 6배 이상 되었기 때문에, 방향을 선회해서 N이 작을 때의 최적해를 구해보고, 규칙을 찾아서 답을 만들어낼 수 있는 알고리즘을 구현해보기로 했습니다. BFS 코드에서 checker 코드를 만드는 것도 약간의 수정이면 가능해서, 만드는 김에 checker까지 만들었습니다.
from queue import Queue
N = 11
sd = [(0,1),(0,2),(1,0),(1,2),(2,0),(2,1)]
inv_sd = [2,4,0,5,1,3]
chkd = {}
def f(state, x):
towers = [[],[],[]]
for i in range(N):
towers[state%3].append(i)
state //= 3
src, des = sd[x]
nn, mm = len(towers[src]), len(towers[des])
if nn == 0:
return -1
ppap = towers[src][nn//2]
if (mm < 1 or towers[des][(mm-1)//2] < ppap) and (mm < 2 or ppap < towers[des][(mm-1)//2+1]):
towers[src].remove(ppap)
towers[des].insert((mm+1)//2, ppap)
else:
return -1
nstate = 0
for i in range(3):
for j in towers[i]:
nstate += i*(3**j)
return nstate
def ppp(state):
towers = [[],[],[]]
for i in range(N):
towers[state%3].append(i+1)
state //= 3
print(towers)
if __name__ == '__main__':
start = 0
end = (3**N-1)
bfsq = Queue()
bfsq.put(start)
chkd[start] = (0, -1)
while not bfsq.empty():
tmp = bfsq.get()
# print(tmp, chkd[tmp])
if tmp == end:
break
prv = chkd[tmp][0]
for i in range(6):
ttmp = f(tmp, i)
if ttmp != -1 and ttmp not in chkd:
chkd[ttmp] = (prv+1, i)
bfsq.put(ttmp)
y = end
ans = []
aans = []
while y!=start:
tmp = chkd[y]
ans.append(tmp[1])
aans.append(y)
y = f(y, inv_sd[tmp[1]])
print(ans[::-1])
print(''.join([chr(ord('A')+i) for i in ans[::-1]]))
print(len(ans))
idx = 0
for z in aans[::-1]:
idx += 1
print(idx, end=' ')
ppp(z)
# checker
# if __name__ == '__main__':
# cur = 0
# N = int(input())
# with open("output.txt", "r") as ff:
# ans = ff.readline().strip()
# # ans = input()
# cnt = 0
# for c in ans:
# xx = ord(c) - ord('A')
# cur = f(cur, xx)
# cnt += 1
# # print(cnt, end=' ')
# # ppp(cur)
# if cur == -1:
# print("boom")
# exit(0)
# print(cnt, end=' ')
# ppp(cur)이렇게 답을 뽑아놓고, 100개 정도 되는 타워들의 패턴을 보면서, 큰 덩어리가 움직이는 형태가 나오는지를 관찰했습니다. 특히, 예를 들면 N=7인 경우 1과 7이 항상 타워에 들어 있는 상황이라면, 1과 7이 없더라도 똑같은 이동 결과가 나오게 됩니다. 1234567 - - → 127 - 3456를 23456 - - → 2 - 3456과 똑같이 생각할 수 있다는 것이죠. 이것이 "간단한 재귀"에서 재귀 함수를 호출하게 되는 부분입니다. 심지어 이동도 똑같기 때문에 정답 string도 어느 기둥에서 어느 기둥으로 옮기는지만 잘 바꿔주면 됩니다.
1 [[1, 2, 3, 5, 6, 7], [4], []]
2 [[1, 2, 3, 6, 7], [4, 5], []]
3 [[1, 2, 6, 7], [4, 5], [3]]
4 [[1, 2, 7], [4, 5], [3, 6]]
5 [[1, 2, 5, 7], [4], [3, 6]]
6 [[1, 2, 5, 7], [], [3, 4, 6]]
7 [[1, 2, 7], [], [3, 4, 5, 6]]
8 [[1, 7], [2], [3, 4, 5, 6]]
9 [[1], [2, 7], [3, 4, 5, 6]]
10 [[1, 5], [2, 7], [3, 4, 6]]
11 [[1, 5], [2, 4, 7], [3, 6]]
12 [[1], [2, 4, 5, 7], [3, 6]]
13 [[1, 6], [2, 4, 5, 7], [3]]
14 [[1, 3, 6], [2, 4, 5, 7], []]
15 [[1, 3, 5, 6], [2, 4, 7], []]
16 [[1, 3, 5, 6], [2, 7], [4]]
17 [[1, 3, 6], [2, 7], [4, 5]]
18 [[1, 6], [2, 3, 7], [4, 5]]
19 [[1], [2, 3, 6, 7], [4, 5]]
20 [[1, 5], [2, 3, 6, 7], [4]]
21 [[1, 5], [2, 3, 4, 6, 7], []]
22 [[1], [2, 3, 4, 5, 6, 7], []]
23 [[], [2, 3, 4, 5, 6, 7], [1]]
24 [[], [2, 3, 4, 6, 7], [1, 5]]
25 [[4], [2, 3, 6, 7], [1, 5]]
26 [[4, 6], [2, 3, 7], [1, 5]]
27 [[4, 6], [2, 7], [1, 3, 5]]
28 [[4], [2, 6, 7], [1, 3, 5]]
29 [[], [2, 6, 7], [1, 3, 4, 5]]
30 [[6], [2, 7], [1, 3, 4, 5]]
31 [[6], [2, 4, 7], [1, 3, 5]]
32 [[], [2, 4, 6, 7], [1, 3, 5]]
33 [[3], [2, 4, 6, 7], [1, 5]]
34 [[3, 6], [2, 4, 7], [1, 5]]
35 [[3, 4, 6], [2, 7], [1, 5]]
36 [[3, 4, 5, 6], [2, 7], [1]]
37 [[3, 4, 5, 6], [2], [1, 7]]
38 [[3, 4, 5, 6], [], [1, 2, 7]]
39 [[3, 4, 6], [], [1, 2, 5, 7]]
40 [[3, 6], [4], [1, 2, 5, 7]]
41 [[3, 6], [4, 5], [1, 2, 7]]
42 [[3], [4, 5], [1, 2, 6, 7]]
43 [[], [4, 5], [1, 2, 3, 6, 7]]
44 [[], [4], [1, 2, 3, 5, 6, 7]]
45 [[], [], [1, 2, 3, 4, 5, 6, 7]]N=7일 때를 간단히 보자면, 1234567 - - → 127 - 3456을 23456 - - → 2 - 3456로 환원할 수 있습니다. 또한, 이후 1 27 3456 → 1 234567 - 역시 1 - 3456 → 1 3456 -로 환원할 수 있습니다. 이렇게 하면 1234567 - - → 1 234567 -가 끝났고, 위에서 언급했듯이 전체 답도 만들어낼 수 있습니다.
많은 시행착오 끝에 다음과 같은 5가지 점화식으로 모든 것을 나타낼 수 있었습니다.
f(9,^,0,0) = f(7,^,0,0) + 2 + f(6,v,^,0) + 1 + f(6,^,v,0)
f(9,0,0,^) = f(8,v,^,0) + 1 + f(8,^,v,0)
f(9,^,v,0) = f(7,^,v,0) + 1 + f(6,0,0,^) + 2 + f(7,^,^,0)
f(9,^,^,0) = f(6,0,0,^) + 2 + f(5,^,^,0) + 1 + f(6,^^,0,^) + f(6,0,^^,^) + f(5,^,^,0) + 2 + f(6,0,0,^)
f(9,^^,0,^) = f(7,0,0,^) + 2 + f(6,^,^,0) + 1 + f(5,0,0,^) + 2 + f(4,^,^,0) + 1 + f(5,^^,0,^)
f(9,^,0,0): 123456789A - - => 1 23456789A -
f(9,0,0,^): 23456789A - 1 => - 23456789A 1
f(9,^,v,0): 123456789A B - => 1 23456789AB -
f(9,^,^,0): 13456789AB 2 - => 1 23456789AB -
f(9,^^,0,^): 13456789ABC - 2 => 13 456789ABC 2실제 구현과는 조금 다른데, 세 번째 케이스가 바닥이 목표 기둥이 아닌 곳에 있어야 더 빠를 때가 있어서 해당 부분을 flag로 넣어 최적화를 했습니다.
저 점화식을 쓸 때 기둥 위치까지 같이 썼다면 좀 더 구현이 빨랐을 수도 있겠네요.
4. 구현, 그리고 대회 종료
구현을 하다가 결국 완성된 코드를 만들지 못하고 대회가 종료되었습니다. 이후 열심히 코딩을 했지만 2시간이 더 걸렸습니다. 아이디어 완성 이후부터만 따지더라도 전체 코딩 시간이 4시간은 넘는 것 같습니다.
처음에 N이 작은 경우에 대한 하드코딩을 좀 덜 했더니 1007835라는 조금 아쉬운 길이가 나왔습니다. 작은 경우에 대한 예외처리를 열심히 추가했더니 976371짜리 만점 답안이 나왔습니다. 출제자가 확인한 972051보다는 큰데, 더 줄이기 위해서는 아마 세 번째 케이스에 대한 완벽한 최적화가 필요할 것 같습니다.
아래는 답을 만드는 코드입니다.
#include <bits/stdc++.h>
using namespace std;
pair<int,int> i2p[6] = {{0,1},{0,2},{1,0},{1,2},{2,0},{2,1}};
map<pair<int,int>, int> p2i;
int ggr[6] = {2,4,0,5,1,3};
void init(){
for(int i=0;i<6;i++) p2i[i2p[i]] = i;
}
string cv(string s, int a, int b, int c){
string res = "";
int k = s.size();
int xxx[3] = {a, b, c};
for(int i=0;i<k;i++){
pair<int,int> tmp = i2p[s[i] - 'A'];
res += (char)('A'+p2i[{xxx[tmp.first], xxx[tmp.second]}]);
}
return res;
}
string geoguro(string s){
string res = "";
int k = s.size();
for(int i=k-1;i>=0;i--) res += (char)('A'+ggr[s[i]-'A']);
return res;
}
string f1(int n, int a, int b, int c);
string f2(int n, int a, int b, int c);
string f3(int n, int a, int b, int c, bool flag);
string f4(int n, int a, int b, int c);
string f5(int n, int a, int b, int c);
int main(){
// freopen("output.txt", "w", stdout);
init();
int N = 26;
cout << "Case #1\n";
cout << N << "\n";
string ans;
ans += f1(N-1, 0, 1, 2);
ans += "B";
ans += geoguro(f1(N-1, 2, 1, 0));
cout << ans << "\n";
cout << ans.size();
}
string f1(int n, int a, int b, int c){
if(n==0) return "";
if(n==1) return cv("A", a, b, c);
if(n==2) return cv("AA", a, b, c);
if(n==3) return cv("BAAF", a, b, c);
if(n==4) return cv("BBAAEFA", a, b, c);
string res = "";
res += f1(n-2, a, c, b);
res += (char)('A'+p2i[{a,b}]);
res += (char)('A'+p2i[{a,b}]);
res += geoguro(f3(n-3, a, c, b, true));
res += f3(n-3, a, b, c, false);
// cout << "f1 " << n << " " << a << " " << b << " " << c << ": " << res << "\n";
return res;
}
string f2(int n, int a, int b, int c){
if(n==0) return "";
if(n==1) return cv("A", a, b, c);
if(n==2) return cv("BAF", a, b, c);
if(n==3) return cv("ABBCFFA", a, b, c);
string res = "";
res += geoguro(f3(n-1, c, a, b, false));
res += f3(n-1, c, b, a, true);
return res;
}
string f3(int n, int a, int b, int c, bool flag){
if(n==0) return flag?"":cv("F", a, b, c);
if(n==1) return flag?cv("DAF", a, b, c):cv("AF", a, b, c);
if(n==2) return flag?cv("DAFA", a, b, c):cv("AFA", a, b, c);
string res = "";
if(flag){
res += f3(n-2, a, c, b, false);
}
else{
res += f3(n-2, a, c, b, true);
}
res += (char)('A'+p2i[{a,b}]);
res += f2(n-3, c, a, b);
res += (char)('A'+p2i[{c,b}]);
res += (char)('A'+p2i[{c,b}]);
res += f4(n-2, a, b, c);
return res;
}
string f4(int n, int a, int b, int c){
if(n==0) return "";
if(n==1) return cv("A", a, b, c);
if(n==2) return cv("BAF", a, b, c);
if(n==3) return cv("ABBCFFA", a, b, c);
if(n==4) return cv("BAABCDAECFAAF", a, b, c);
if(n==5) return cv("ABDAAFBDCDAECEFBAAEFA", a, b, c);
string res = "";
res += f2(n-3, a, c, b);
res += (char)('A'+p2i[{a,b}]);
res += (char)('A'+p2i[{a,b}]);
res += f4(n-4, c, b, a);
res += (char)('A'+p2i[{a,c}]);
res += f5(n-3, b, c, a);
res += (char)('A'+p2i[{b,a}]);
res += geoguro(f5(n-3, a, c, b));
res += (char)('A'+p2i[{c,b}]);
res += f4(n-4, a, c, b);
res += (char)('A'+p2i[{a,b}]);
res += (char)('A'+p2i[{a,b}]);
res += f2(n-3, c, b, a);
return res;
}
string f5(int n, int a, int b, int c){
if(n==0) return "";
if(n==1) return cv("BAE", a, b, c);
if(n==2) return cv("ABAE", a, b, c);
if(n==3) return cv("ABBAEF", a, b, c);
if(n==4) return cv("BAFBBDAFEF", a, b, c);
string res = "";
res += f2(n-2, a, b, c);
res += (char)('A'+p2i[{a,c}]);
res += (char)('A'+p2i[{a,c}]);
res += f4(n-3, b, c, a);
res += (char)('A'+p2i[{a,b}]);
res += f2(n-4, c, b, a);
res += (char)('A'+p2i[{c,a}]);
res += (char)('A'+p2i[{c,a}]);
res += f4(n-5, b, a, c);
res += (char)('A'+p2i[{c,b}]);
res += f5(n-4, a, b, c);
return res;
}끝으로 마지막 디버깅 단계에서 썼던, 실제 이동 과정이 들어있는 메모를 첨부합니다.
# f5
13456...WXYZ - 2
13YZ 456..WX 2
1Z 456..WX 23Y
1Z 4 2356..WXY
1 4Z 2356..WXY
1 456..WZ 23XY
13X 456..WZ 2Y
136..WX 45Z 2Y
136..WX 45YZ 2
13456..WXYZ - 2
# f1
123..XYZ - -
12Z - 3..XY
1 2Z 3..XY
13..X 2Z Y
13..X 2YZ -
1 23..XYZ -
# f3
1234..XY Z -
1234..XY - Z
12Y - 34..XZ
1Y 2 34...XZ
14..XY 2 3Z
14..XY 23Z -
1 234..XYZ -
# f2
2..YZ - 1
Z - 12..Y
- Z 12..Y
- 2..YZ 1
# f4
1345..XYZ 2 -
13YZ 2 45..X
1Z 23Y 45..X
1Z 235..XY 4
1 235..XY 4Z
1 23 45..XYZ
13 2 45..XYZ
135..XY 2 4Z
135..XY 2Z 4
13Y 2Z 45..X
1 23YZ 45..X'PS' 카테고리의 다른 글
| UCPC 2023 예선 후기 (팀명: 관리상의이유로정규식을통과하는팀명만을허용하게되었습니다) (0) | 2023.07.03 |
|---|---|
| Google Hash Code 2020 대회 (간단한) 후기! (0) | 2020.02.21 |