1차 예선 때 글을 바로 안 써놓아서 문제가 잘 기억나지 않아 문제가 나오고 나서 후기를 작성할까 고민하다가 나중에는 더 작성하지 않을 것 같아서 그냥 작성하게 되었다..
1차 예선
1. 증강현실 배달 안경
#bruteforce
아마 A개를 담을 수 있는 상자와 B개를 담을 수 있는 상자로 N개를 1개도 빠짐없이 모두 담으려고 할 때 상자를 최대로 사용하는 문제였던 것 같다. 가능한 모든 경우를 탐색해주기만 하면 되는 문제였다.
#include <bits/stdc++.h>
using namespace std;
int n, m, k;
void solve() {
int a, b;
cin >> n >> a >> b;
if (a > b) swap(a, b);
int cnt = 0;
while (1) {
int tmp = b * cnt;
if (tmp > n) break;
if ((n - tmp) % a == 0) {
cout << cnt + (n - tmp) / a << "\n";
return;
}
cnt++;
}
cout << -1 << "\n";
}
int main(void) {
fastio;
int test_case; cin >> test_case;
for (int tc = 1; tc <= test_case; tc++) {
cout << "Case #" << tc << "\n";
solve();
}
return 0;
}2. 딸기 수확 로봇
#parametric_search #sorting
한 번만 방향을 꺾는 것이 이득이라는 것을 증명하였다면 매개 변수 탐색을 통해 답을 찾을 수 있었다. 이 문제가 투 포인터로 O(N)에 풀린다고 들었던 것 같다.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int n, m, k;
vector<ll> v;
bool isAvailable(int x) {
int d = INF * 2;
for (int i = 0; i < n - x; i++) {
int s = v[i];
int e = v[i + x];
if (s < 0 && e > 0)
d = min(d, min(-s, e) * 2 + max(-s, e));
else d = min(d, max(abs(s), abs(e)));
if (d <= k) return 1;
}
return 0;
}
void solve() {
int ans = -1;
cin >> n >> k;
for (int i = 0; i < n; i++) {
ll x; cin >> x;
v.emplace_back(x);
}
sort(all(v));
int s = 0, e = n - 1;
while (s <= e) {
int mid = s + e >> 1;
if (isAvailable(mid)) {
ans = mid;
s = mid + 1;
}
else e = mid - 1;
}
cout << ans + 1 << "\n";
}
int main(void) {
fastio;
int test_case; cin >> test_case;
for (int tc = 1; tc <= test_case; tc++) {
cout << "Case #" << tc << "\n";
solve();
v.clear();
}
return 0;
}2번까지는 그래도 큰 어려움 없이 바로 바로 해결할 수 있었다. 하지만 3번부터가 시작이었다...
3. 장난감
#Adhoc #kmp
두 가지의 난관이 있었다. 전체 개수가 N개보다 작을 때 계속해서 돌리면 모든 위치에 많아도 1개만 있을 수 있다는 것은 쉽게 알 수 있지만 이것을 계속해서 돌린 모양이 어떤 모양인지 빠르게 구하는 것이 첫 번째 난관이었고, 두 번째는 이것을 통해 반복되는 모양이 몇 개인지 찾는 것이 두 번째 난관이었다.
두 번째 난관부터 해결할 수 있었다. 패턴의 반복을 확인하기만 하면 되었다. 이 부분을 bruteforcing으로 진행하였으나 대회가 끝난 후 그냥 kmp로 찾으면 된다는 것을...
하지만 첫 번째 난관이 떠오르지 않았다. 그래서 그냥 하나씩 다 그려보면서 진행했는데, 규칙이 조금씩 보였다. 왼쪽으로 밀 수 있는 구슬들을 모두 밀면 구하고자 하는 모양이 나오는 것이었다. 그래서 해당 부분을 구현하고 AC
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned ll
#define pii pair<int, int>
#define pip pair<int, pii>
#define pll pair<ll, ll>
#define fastio cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false);
#define all(v) v.begin(), v.end()
#define ff first
#define ss second
#define MOD 1234567891
#define INF 0x3f3f3f3f
#define LINF 0x3f3f3f3f3f3f3f3f
#define MAXN 500001
int n, m;
int arr[MAXN];
bool isPrime[MAXN];
void getPrime() {
fill(isPrime, isPrime + MAXN, 1);
isPrime[0] = isPrime[1] = 0;
for (int i = 2; i * i < MAXN; i++) {
if (!isPrime[i]) continue;
for (int j = i + i; j < MAXN; j += i)
isPrime[j] = 0;
}
}
// O(n)
void move() {
for (int k = 0; k < 2; k++) {
for (int i = n - 1; i >= 0; i--) {
if (arr[i] > 1) {
arr[(i - 1 + n) % n] += arr[i] - 1;
arr[i] = 1;
}
}
}
}
// O(nlogn)
int check() {
move();
for (int k = 2; k <= n / 2; k++) {
if (n % k != 0) continue;
bool flag = 1;
int s = k;
while (s < n) {
for (int i = 0; i < k; i++) {
if (arr[s + i] != arr[i]) {
flag = 0;
break;
}
}
if (!flag) break;
s += k;
}
if (flag) return k;
}
return n;
}
void solve() {
int ans = 0;
ll cnt = 0;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> arr[i];
cnt += arr[i];
}
if (cnt >= n || cnt == 0) ans = 1;
else ans = check();
cout << ans << endl;
}
int main(void) {
getPrime();
int test_case; cin >> test_case;
for (int tc = 1; tc <= test_case; tc++) {
cout << "Case #" << tc << endl;
solve();
}
return 0;
}4. 최적의 프로세스 수행 순서
#dp #kmp
3, 4번은 사실 자려다가 새벽에 풀이가 갑자기 생각난 문제들이다. 끝나고 보니 둘 다 kmp인 것이... kmp를 돌려준 다음 단어의 시작 위치를 역방향으로 돌려주며 찾으면 해결할 수 있는 문제였다.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned ll
#define pii pair<int, int>
#define pip pair<int, pii>
#define pll pair<ll, ll>
#define fastio cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false);
#define all(v) v.begin(), v.end()
#define ff first
#define ss second
#define MOD 1234567891
#define INF 0x3f3f3f3f
#define LINF 0x3f3f3f3f3f3f3f3f
#define MAXN 250001
/*
대표 반례
aaabaaabaaa
aabaaa
3
aaaaabbbbaaaaaaababa
aaabbbbb
-1
*/
int n, m, k;
string s1, s2;
int pi[MAXN], res[MAXN];
int len1, len2;
void get_pi() {
int k = 0;
memset(pi, 0, sizeof(pi));
for (int i = 1; i < len2; i++) {
while ((k > 0) && (s2[i] != s2[k])) k = pi[k - 1];
if (s2[i] == s2[k]) pi[i] = ++k;
}
}
int kmp(void) {
int k = 0, ret = 0, past = 0;
int idx = 0;
for (int i = 0; i < len1; i++) {
while ((k > 0) && (s1[i] != s2[k])) k = pi[k - 1];
if (s1[i] == s2[k]) {
res[idx++] = k;
if (k == (len2 - 1))
k = pi[k];
else k++;
}
}
if (idx != len1) return -1;
for (int i = idx - 1; i > 0; i--) {
while (res[i] != 0 && i) {
res[i - 1] = res[i] - 1;
i--;
}
}
for (int i = 0; i < idx; i++) ret += res[i] == 0;
return ret == 0 ? -1 : ret;
}
void solve() {
cin >> s1 >> s2;
len1 = s1.length();
len2 = s2.length();
get_pi();
cout << kmp() << "\n";
}
int main(void) {
fastio;
int test_case; cin >> test_case;
for (int tc = 1; tc <= test_case; tc++) {
cout << "Case #" << tc << endl;
solve();
}
return 0;
}5번은 문제가 "나는 CHT입니다" 하고 있어서 넘겼다... ㅎㅎ DP 최적화들을 올해 조금 공부했었는데 문제들을 많이 풀어봐야 할 것 같다.
1차 에선은 이렇게 마무리 되었다.
2차 예선
상당히 어려웠다.
1. 타이젠 윷놀이
#case_work
문제를 조금 더럽게 풀긴 했다.. 윷놀이 판을 각각 정점으로 대응 시켜서 사이클이 언제 생기는지 파악하여 개수를 세주면 되는 문제였다. 1번 문제부터 살짝 어지러움이 느껴졌다.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned ll
#define pii pair<int, int>
#define pip pair<int, pii>
#define pll pair<ll, ll>
#define fastio cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false);
#define all(v) v.begin(), v.end()
#define ff first
#define ss second
#define MOD 10000003
#define INF 0x3f3f3f3f
#define LINF 0x3f3f3f3f3f3f3f3f
#define MAXN 100001
ll n, k, cnt;
ll A[MAXN];
pii nextState(int cur, int state) {
if (state == 0) {
if (cur == 5) return { 0, 'B' };
else if (cur > 5) return { cur - 5, 1 };
else return { cur, 0 };
}
else if (state == 1) {
if (cur == 5) return { 0, 'C' };
else if (cur > 5) return { cur - 5, 6 };
else return { cur, 1 };
}
else if (state == 2) {
if (cur == 3) return { 0, 'E' };
else if (cur == 6) return { 0, 'D' };
else if (cur > 6) return { cur - 6, 7 };
else if (cur > 3) return { cur - 3, 3 };
else return { cur, 2 };
}
else if (state == 3) {
if (cur == 3) return { 0, 'D' };
else if (cur > 3) return { cur - 3, 7 };
else return { cur, 3 };
}
else if (state == 4) {
if (cur == 3) return { 0, 'E' };
else if (cur == 6) return { 0, 'A' };
else if (cur > 6) return { 0, 0 };
else if (cur > 3) return { cur - 3, 5 };
else return { cur, 4 };
}
else if (state == 5) {
if (cur == 3) return { 0, 'A' };
else if (cur > 3) return { 0, 0 };
else return { cur, 5 };
}
else if (state == 6) {
if (cur == 5) return { 0, 'D' };
else if (cur > 5) return { cur - 5, 7 };
else return { cur, 6 };
}
else if (state == 7) {
if (cur == 5) return { 0, 'A' };
else if (cur > 5) return { 0, 0 };
else return { cur, 7 };
}
else if (state == 'A') {
return { 0, 0 };
}
else if (state == 'B') {
if (cur == 3) return { 0, 'E' };
else if (cur > 3) return { cur - 3, 3 };
else return { cur, 2 };
}
else if (state == 'C') {
if (cur == 3) return { 0, 'E' };
else if (cur > 3) return { cur - 3, 5 };
else return { cur, 4 };
}
else if (state == 'D') {
if (cur == 5) return { 0, 'A' };
else if (cur > 5) return { 0, 0 };
else return { cur, 7 };
}
else if (state == 'E') {
if (cur == 3) return { 0, 'A' };
else if (cur > 3) return { 0, 0 };
else return { cur, 5 };
}
return { -1, -1 };
}
void solve() {
cin >> n >> k;
for (int i = 0; i < n; i++) {
cin >> A[i];
}
ll lastCur, lastState, cycle_cnt = 0;
ll cur = 0, state = 0, pcnt = 0; cnt = 0;
for (int c = 1; c <= k; c++) {
for (int i = 0; i < n; i++) {
tie(cur, state) = nextState(cur + A[i], state);
if (cur == 0 && state == 0)
cnt++, cycle_cnt++;
if (i == n - 1) {
if (c == 1) lastCur = cur, lastState = state, cycle_cnt = 0;
else if (cur == lastCur && state == lastState) {
int cycle = (k - c) / (c - 1);
cnt += cycle * cycle_cnt;
c += cycle * (c - 1);
continue;
}
}
}
}
cout << cnt << endl;
}
int main(void) {
fastio;
int tc; cin >> tc;
for (int _ = 1; _ <= tc; _++) {
cout << "Case #" << _ << "\n";
solve();
}
return 0;
}2. 괄호 문자열
#stack #combinatorics
괄호쌍을 찾는 문제는 유명하니 그대로 진행해주면 되고 같은 단계에 속한 괄호쌍의 조합 개수를 더해주면 된다. 해당 부분은 스택을 통해 각 단계의 괄호쌍을 저장해주었다. 실수를 할 부분이 많았던 문제였다.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned ll
#define pii pair<int, int>
#define pip pair<int, pii>
#define pll pair<ll, ll>
#define fastio cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false);
#define all(v) v.begin(), v.end()
#define ff first
#define ss second
#define MOD 10000003
#define INF 0x3f3f3f3f
#define LINF 0x3f3f3f3f3f3f3f3f
#define MAXN 100001
void solve() {
int n; cin >> n;
string S; cin >> S;
stack<char> s;
stack<ll> pcnt;
ll cnt = 0, pair_cnt = 0;
bool isPair = 0;
for (int i = 0; i < n; i++) {
if (S[i] == '(' || S[i] == '{') {
s.push(S[i]);
if (isPair) {
pcnt.push(pair_cnt);
pair_cnt = 0;
}
else isPair = 1;
}
else {
if (!s.empty()) {
if ((S[i] == ')' && s.top() == '(') ||
(S[i] == '}' && s.top() == '{')) {
if (isPair) pair_cnt++;
else {
if (pair_cnt)
cnt += pair_cnt * (pair_cnt + 1) / 2;
if (!pcnt.empty()) {
pair_cnt = pcnt.top() + 1;
pcnt.pop();
}
else pair_cnt = 1;
}
s.pop();
}
else {
s.push(S[i]);
cnt += pair_cnt * (pair_cnt + 1) / 2;
pair_cnt = 0;
}
}
else if (pair_cnt) {
cnt += pair_cnt * (pair_cnt + 1) / 2;
pair_cnt = 0;
}
isPair = 0;
}
}
if (pair_cnt) cnt += pair_cnt * (pair_cnt + 1) / 2;
while (!pcnt.empty()) {
ll t = pcnt.top();
cnt += t * (t + 1) / 2;
pcnt.pop();
}
cout << cnt << endl;
}
int main(void) {
fastio;
int tc; cin >> tc;
for (int _ = 1; _ <= tc; _++) {
cout << "Case #" << _ << endl;
solve();
}
return 0;
}3, 4, 5번은 긁기만 했다. 3번은 ${20}C{9}$의 경우만 탐색해주면 되고, 4번은 DP로 3000짜리 제한까지는 뚫리고, 5번도 완전탐색을 진행해주면 된다. (8!=40320)
아무래도 시도 횟수가 많고 3번도 첫 단계밖에 못 긁어서 진출은 어렵지 않을까 생각 중이다. 하지만 작년보다 실력이 늘은 것이 느껴져서 꽤 만족스러운 대회였다. 아래는 긁은 코드들이다.
3. 루머
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned ll
#define pii pair<int, int>
#define pip pair<int, pii>
#define pll pair<ll, ll>
#define fastio cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false);
#define all(v) v.begin(), v.end()
#define ff first
#define ss second
#define MOD 10000003
#define INF 0x3f3f3f3f
#define LINF 0x3f3f3f3f3f3f3f3f
#define MAXN 5001
int n, A[MAXN], M, t, ans;
bool vst[MAXN], flag[MAXN], before[MAXN];
int check() {
queue<pii> q;
for (int i = 0; i < n; i++) {
flag[i] = before[i] = vst[i];
if (vst[i]) q.push({ 1, i + 1 }), q.push({ 1, i - 1 });
}
int lastcnt = 1;
while (!q.empty()) {
int cnt = q.front().ff;
int idx = q.front().ss;
q.pop();
if (cnt > t) break;
if (lastcnt < cnt) {
for (int i = 0; i < n; i++)
before[i] = flag[i];
lastcnt = cnt;
}
if (idx < 0 || idx >= n || before[idx]) continue;
if ((idx == 0 && before[1]) ||
(idx == n - 1 && before[n - 2]))
flag[idx] = 1;
else if (A[idx] == 2 && before[idx - 1] && before[idx + 1])
flag[idx] = 1;
else if (A[idx] == 1 && (before[idx - 1] || before[idx + 1])) {
flag[idx] = 1;
if (!before[idx - 1]) q.push({ cnt + 1, idx - 1 });
if (!before[idx + 1]) q.push({ cnt + 1, idx + 1 });
}
}
int ret = 0;
for (int i = 0; i < n; i++)
ret += flag[i];
return ret;
}
void dfs(int x, int cnt) {
if (cnt == M) {
ans = max(ans, check());
return;
}
for (int i = x; i < n; i++) {
vst[i] = 1;
dfs(i + 1, cnt + 1);
vst[i] = 0;
}
}
void solve() {
ans = 0;
cin >> n;
for (int i = 0; i < n; i++)
cin >> A[i];
cin >> M >> t;
if (M >= n / 2) {
cout << n << endl;
return;
}
if (n > 20) {
cout << 0 << endl;
return;
}
if (n == 1) {
cout << 1 << endl;
return;
}
dfs(0, 0);
cout << ans << endl;
}
int main(void) {
fastio;
int tc; cin >> tc;
for (int _ = 1; _ <= tc; _++) {
cout << "Case #" << _ << endl;
solve();
}
return 0;
}4. 막대기 연결
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned ll
#define pii pair<int, int>
#define pip pair<int, pii>
#define pll pair<ll, ll>
#define fastio cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false);
#define all(v) v.begin(), v.end()
#define ff first
#define ss second
#define MOD 10000003
#define INF 0x3f3f3f3f
#define LINF 0x3f3f3f3f3f3f3f3f
#define MAXN 100001
ll n, k, x[MAXN], h[MAXN];
ll dp[3001][3001];
bool vst[3001][3001];
ll area(int l, int r) {
return (h[r] + h[l]) * (x[r] - x[l]);
}
ll dfs(int s, int e) {
if (s >= e) return LINF;
if (dp[s][e] != LINF) return dp[s][e];
return dp[s][e] = min({ area(s, e), dfs(s + 1, e), dfs(s, e - 1) });
}
void solve() {
cin >> n;
for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) dp[i][j] = LINF;
for (int i = 1; i <= n; i++)
cin >> x[i] >> h[i];
cin >> k;
if (n > 3000 || k > 3000) {
while (k--) cout << 0 << endl;
return;
}
dfs(1, n);
ll ans = LINF;
while (k--) {
int a, b; cin >> a >> b;
cout << dp[a][b] << endl;
}
}
int main(void) {
fastio;
int tc; cin >> tc;
for (int _ = 1; _ <= tc; _++) {
cout << "Case #" << _ << endl;
solve();
}
return 0;
}5. 아파트 건설
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned ll
#define pii pair<int, int>
#define pip pair<int, pii>
#define pll pair<ll, ll>
#define fastio cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false);
#define all(v) v.begin(), v.end()
#define ff first
#define ss second
#define MOD 10000003
#define INF 0x3f3f3f3f
#define LINF 0x3f3f3f3f3f3f3f3f
#define MAXN 100001
int n, m, k;
void solve() {
vector<pii> v;
cin >> n >> k;
cin >> m;
for (int i = 0; i < m; i++) {
int a, b; cin >> a >> b;
v.push_back({ a - 1, b - 1 });
}
if (n > 8) {
cout << 0 << endl;
return;
}
vector<int> p; for (int i = 1; i <= n; i++) p.push_back(i);
ll cnt = 0; // max is 8! = 40320, but 20! = 1e18 n is 20
do {
bool flag = 1;
for (int i = 0; i < v.size(); i++) {
if (p[v[i].ff] + p[v[i].ss] > k) {
flag = 0;
break;
}
}
if (flag) cnt++;
} while (next_permutation(all(p)));
cout << cnt << endl;
}
int main(void) {
fastio;
int tc; cin >> tc;
for (int _ = 1; _ <= tc; _++) {
cout << "Case #" << _ << endl;
solve();
}
return 0;
}