2019 KOI 2차 대회 후기

작성일 | In

전략

대회에서는 실력만큼 전략이나 컨디션, 멘탈 관리가 중요하다는 것을 1차 대회가 끝나고 나서 깨달았습니다.
대회 전날부터 몇 가지 규칙을 정해놓고 대회에 참가했습니다.

  • 1번 풀이가 10분 이내로 안 떠오르면 넘어감
  • 1번 구현 방법 30분 이내로 정리가 안 되면 넘어감
  • 2번 풀이가 30분 이내로 안 떠오르면 서브테스크 긁음
  • 3, 4번은 서브테스크만 긁어도 성공

등등 몇 가지 규칙을 세웠습니다.

1번 문제

대회는 1시에 시작이 되었습니다.
서버가 느려져서 1시 3분쯤에 문제를 열었고, 1시 5분에 서버 지연을 이유로 1대회가 중단되었습니다.
1번 문제를 읽고 나서 대회가 중단되었기 때문에 1시 25분에 대회가 다시 재개될 때까지 약 20분간 구현 절차를 정리했습니다. 마침 풀이는 쉽고 구현량만 많은 문제라 개인적으로 좋았습니다.
1시 45분에 WA를 받고, 반례를 찾아서 고친 다음에 1시 55분에 AC가 떴습니다.

2번 문제

문제 보자마자 dp 느낌이 와서 dp로 최소 길이를 구하고, 역추적하면서 괄호열을 구성하는 방식으로 풀었습니다.
dp[N]을 f(x) = N이 되는 최소 길이라고 할 때, dp[N]가 최소가 되게 하는 바로 전 상태가 여러 가지라는 것을 생각하지 못해서 48점이 나왔습니다.
가능한 이전 상태를 모두 배열에 저장해도 각 숫자마다 최대 10개만 들어가고, 괄호열은 최대 18글자이기 때문에 마음 편하게 재귀 돌면서 탐색했습니다.
정확한 시간은 기억나지 않지만 2시 50분~3시 20분쯤에 AC가 떴습니다.

여담으로, {}보다 []가 아스키코드가 작다는 것을 너무 늦게 깨달았습니다.

3번 문제

뭔가 트리dp인데, 감이 안 잡혀서 비트마스크로 완전 탐색 돌면서 전처리해줘서 9점 긁었습니다.

풀이를 들어보니, 검은 돌의 개수를 고정시키고 정점 개수의 상한/하한을 구하는 방식으로 트리dp를 돌리면 된다고 하네요.

4번 문제

기하 문제는 역겹습니다.
1번 서브테스크의 반례가 끝나기 1분 전에 떠올라서 못 긁었습니다.

아무말

1번 문제는 3번 정도 틀리고, 2번 문제도 5번 정도 틀려서 멘탈이 터질뻔했지만, 다행히 계속해서 아이디어가 떠오르길래 멘탈을 잘 잡고 있었습니다.
저는 한 번 말리면 끝까지 멘탈 복구 못 하는 타입이기 때문에 조심해야 합니다:(

2번 문제 100점 나오자마자 긴장감이 풀리면서 느긋하게 서브테스크 구경하는 저를 관찰할 수 있었습니다.

결과

총점 209점
예상했던 점수입니다. 내년에는 더 잘해야겠네요.
점수 공유해보니까 동상 최상위권 ~ 은상 최하위권정도 나올 것 같습니다.

목요일에 결과가 나온다고 하는데, 딱히 긴장되지는 않네요.

추가) 소스코드

대회 당시에 작성했던 코드와 최대한 비슷하게 다시 코드를 짰습니다.
몇 가지 구현을 빼먹었을 수 있지만, 예제와 대회 당시에 발견했던 반례는 모두 통과합니다.

1번

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#include <bits/stdc++.h>
using namespace std;

int n, k;
int arr[55][55];
int tmp[55][55];
int dist[55][55];
int ans = 1e9+7;

int di[6][2] = { //세로 방향 이동
	1, 0,
	1, 0,
	-1, 0,
	-1, 0,
	1, -1,
	0, 0
};

int dj[6][2] = { //가로 방향 이동
	0, 1,
	0, -1,
	0, 1,
	0, -1,
	0, 0,
	-1, 1
};

int chk(){
	for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) dist[i][j] = 1e9+7;
	int now, i, j, cnt;

	//start(시작 지점에 못 들어가는 경우)
	now = arr[1][1];
	if(now != 1 && now != 3 && now != 5) return dist[n][n];
	//end(끝 지점으로 못 빠져나가는 경우)
	now = arr[n][n];
	if(now != 0 && now != 2 && now != 5) return dist[n][n];

	i = 1, j = 1, cnt = 1;
	while(1){
		dist[i][j] = cnt++;
		if(i == n && j == n) break;
		now = arr[i][j];
		int ddi, ddj, ii, jj, flag, nxt;

		ddi = di[now][0], ddj = dj[now][0];
		ii = i + ddi, jj = j + ddj;
		nxt = arr[ii][jj]; flag = 1;

		if(dist[ii][jj] < 1e5) flag = 0; //이미 방문한 칸
		if(ddi == -1 && ddj == 0){
			if(nxt != 0 && nxt != 1 && nxt != 4) flag = 0;
		}
		if(ddi == 1 && ddj == 0){
			if(nxt != 2 && nxt != 3 && nxt != 4) flag = 0;
		}
		if(ddi == 0 && ddj == -1){
			if(nxt != 0 && nxt != 2 && nxt != 5) flag = 0;
		}
		if(ddi == 0 && ddj == 1){
			if(nxt != 1 && nxt != 3 && nxt != 5) flag = 0;
		}
		if(flag){
			i = ii, j = jj; continue;
		}

		ddi = di[now][1], ddj = dj[now][1];
		ii = i + ddi, jj = j + ddj;
		nxt = arr[ii][jj]; flag = 1;

		if(dist[ii][jj] < 1e5) flag = 0;
		if(ddi == -1 && ddj == 0){
			if(nxt != 0 && nxt != 1 && nxt != 4) flag = 0;
		}
		if(ddi == 1 && ddj == 0){
			if(nxt != 2 && nxt != 3 && nxt != 4) flag = 0;
		}
		if(ddi == 0 && ddj == -1){
			if(nxt != 0 && nxt != 2 && nxt != 5) flag = 0;
		}
		if(ddi == 0 && ddj == 1){
			if(nxt != 1 && nxt != 3 && nxt != 5) flag = 0;
		}
		if(flag){
			i = ii, j = jj; continue;
		}
		break;
	}
	return dist[n][n];
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n >> k;
	for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) cin >> arr[i][j];

	if(k == 0){ //k가 0인 경우 : 입력 데이터에서 탐색
		ans = min(ans, chk());
		if(ans > 1e9) cout << -1;
		else cout << ans;
		return 0;
	}

	memcpy(tmp, arr, sizeof tmp);
    //k가 1인 경우 : 하나씩 바꿔보면서 탐색
	for(int i=1; i<=n; i++){
		for(int j=1; j<=n; j++){
			for(int k=0; k<6; k++){
				if(tmp[i][j] == k) continue;
				arr[i][j] = k;
				ans = min(ans, chk());
				arr[i][j] = tmp[i][j];
			}
		}
	}

	if(ans > 1e9) cout << -1;
	else cout << ans;
	return 0;
}

2번

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;

typedef pair<int, int> p;
typedef pair<int, p> pp; // {op, {a, b}}

int dp[1010]; //괄호열의 최소 길이, 최대 약 18
vector<pp> track[1010]; //track[N] = dp[N]이 최소가 되는 이전 상태
/*
** a+b = N인 경우 : op = 0
** a*b = N인 경우 : op = 1
** dp[N]이 최소가 되는 이전 상태는 약 10개까지 존재함
*/
string ans[1010]; //괄호열

void init(){
	memset(dp, -1, sizeof dp);
	dp[1] = dp[2] = dp[3] = 2;

	track[1].push_back({-1, {-1, -1}});
	track[2].push_back({-1, {-1, -1}});
	track[3].push_back({-1, {-1, -1}});

	ans[1] = "()";
	ans[2] = "{}";
	ans[3] = "[]";
}

int f(int x){
	int &res = dp[x];
	if(res != -1) return res;

	res = 1e9+7;
	if(x%2 == 0){ //(...)
		int now = f(x/2) + 2;
		if(now < res){
			res = now;
			track[x].clear();
			track[x].push_back({1, {2, x/2}});
		}else if(now == res){
			track[x].push_back({1, {2, x/2}});
		}
	}
	if(x%3 == 0){ //{...}
		int now = f(x/3) + 2;
		if(now < res){
			res = now;
			track[x].clear();
			track[x].push_back({1, {3, x/3}});
		}else if(now == res){
			track[x].push_back({1, {3, x/3}});
		}
	}
	if(x%5 == 0){ //[...]
		int now = f(x/5) + 2;
		if(now < res){
			res = now;
			track[x].clear();
			track[x].push_back({1, {5, x/5}});
		}else if(now == res){
			track[x].push_back({1, {5, x/5}});
		}
	}

	for(int i=1; i<x; i++){
		if(i > x-i) break;
		int now = f(i) + f(x-i); //ans[i]과 ans[x-i]를 붙임
		if(now < res){
			res = now;
			track[x].clear();
			track[x].push_back({0, {i, x-i}});
		}else if(now == res){
			track[x].push_back({0, {i, x-i}});
		}
	}
	return res;
}

bool cmp(string &a, string &b){ //{}보다 []가 아스키코드가 작더라...
	int len = min(a.size(), b.size());
	for(int i=0; i<len; i++){
		int x, y;
		if(a[i] == '(') x = 1;
		else if(a[i] == ')') x = 2;
		else if(a[i] == '{') x = 3;
		else if(a[i] == '}') x = 4;
		else if(a[i] == '[') x = 5;
		else x = 6;

		if(b[i] == '(') y = 1;
		else if(b[i] == ')') y = 2;
		else if(b[i] == '{') y = 3;
		else if(b[i] == '}') y = 4;
		else if(b[i] == '[') y = 5;
		else y = 6;

		if(x != y) return x < y;
	}
	return a.size() < b.size();
}

void make(int x){
	if(!ans[x].empty()) return;

	string res = "]]]]]]]]]]]]]]]]]]]";
	for(auto i : track[x]){ //dp[N]이 최소가 되는 모든 이전 상태를 순회
		int op = i.x, a = i.y.x, b = i.y.y;
		vector<string> now;

		if(op == 0) make(a); ////덧셈인 경우에만 a에 대해 재귀 호출, 곱셈인 경우는 2/3/5 중 하나이므로 탐색할 필요 없음
		make(b);
		if(op == 0) now.push_back(ans[a]);
		now.push_back(ans[b]);

		sort(now.begin(), now.end(), cmp);

		string sum;
		for(auto j : now) sum += j;
		if(op == 1){ //곱셈인 경우 처리
			if(a == 2) sum = "(" + sum + ")";
			if(a == 3) sum = "{" + sum + "}";
			if(a == 5) sum = "[" + sum + "]";
		}
		if(cmp(sum, res)) res = sum;
	}
	ans[x] = res;
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	init();

	int t; cin >> t;
	while(t--){
		int n; cin >> n;
		f(n); make(n);
		cout << ans[n] << "\n";
	}
}