개요
이번 라운드는 전형적인 C번까지는 쉽고, D번에서 갑자기 어려워지는 라운드였다.
C번까지 느리게 풀거나 패널티를 좀 받으면 1400등 정도가 되고, 거기서 D, E, F 중 한 개를 풀면 200등권으로 들어올 수 있었다.
A번
A번 문제: 구현
단순한 구현 문제다.
$n$개의 원소를 가진 배열이 주어지며, 각 원소는 -1 혹은 1이다.
또한 입력으로 $k$가 주어지며, 여기서 적절한 $b$를 선택해 $b+i \cdot k$에 해당되는 원소들을 모두 지웠을 때 남은 1과 -1의 개수의 차이가 가장 크게 만드는 경우를 찾아야 한다.
이 때 $i$는 정수이다 (음수, 양수, 0 가능)
풀이 보기
문제 조건을 잘 봐야 하는데, $i$는 음, 양, 0 모두가 가능한 정수이다.
즉, b가 아무리 크더라도 b를 포함한 그 이전, 이후 모두가 지워져야 한다는 것이다.
이것만 조심하면 문제에서 설명 된 그대로 시뮬레이팅 하며 답을 찾으면 된다.
소스코드 보기
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL_BOOKNU
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif
// ........................macro.......................... //
#define FOR(i, f, n) for(int (i) = (f); (i) < (int)(n); ++(i))
#define RFOR(i, f, n) for(int (i) = (f); (i) >= (int)(n); --(i))
#define pb push_back
#define emb emplace_back
#define fi first
#define se second
#define ENDL '\n'
#define sz(A) (int)(A).size()
#define ALL(A) A.begin(), A.end()
#define UNIQUE(c) (c).resize(unique(ALL(c)) - (c).begin())
#define next next9876
#define prev prev1234
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ii> vii;
typedef vector<vii> vvii;
typedef long long i64;
typedef unsigned long long ui64;
// inline i64 GCD(i64 a, i64 b) { if(b == 0) return a; return GCD(b, a % b); }
inline int getidx(const vi& ar, int x) { return lower_bound(ALL(ar), x) - ar.begin(); } // 좌표 압축에 사용: 정렬된 ar에서 x의 idx를 찾음
inline i64 GCD(i64 a, i64 b) { i64 n; if(a < b) swap(a, b); while(b != 0) { n = a % b; a = b; b = n; } return a; }
inline i64 LCM(i64 a, i64 b) { if(a == 0 || b == 0) return GCD(a, b); return a / GCD(a, b) * b; }
inline i64 CEIL(i64 n, i64 d) { return n / d + (i64)(n % d != 0); } // 음수일 때 이상하게 작동할 수 있음.
inline i64 ROUND(i64 n, i64 d) { return n / d + (i64)((n % d) * 2 >= d); }
inline i64 POW(i64 a, i64 n) {
assert(0 <= n);
i64 ret;
for(ret = 1; n; a = a*a, n /= 2) { if(n%2) ret *= a; }
return ret;
}
template <class T>
ostream& operator<<(ostream& os, vector<T> v) {
os << "[";
int cnt = 0;
for(auto vv : v) { os << vv; if(++cnt < v.size()) os << ","; }
return os << "]";
}
template <class T>
ostream& operator<<(ostream& os, set<T> v) {
os << "[";
int cnt = 0;
for(auto vv : v) { os << vv; if(++cnt < v.size()) os << ","; }
return os << "]";
}
template <class L, class R>
ostream& operator<<(ostream& os, pair<L, R> p) { return os << "(" << p.fi << "," << p.se << ")"; }
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) { cerr << " " << H, debug_out(T...); }
// ....................................................... //
const int MAXN = 1e2;
int n, k, a, b, ar[MAXN];
void input() {
cin >> n >> k;
FOR(i, 0, n) {
cin >> ar[i];
if(ar[i] == 1) ++a;
else ++b;
}
}
int solve() {
int ans = 0;
FOR(i, 0, k) {
int ca = a, cb = b;
for(int j = i; j < n; j += k) {
if(ar[j] == 1) --ca;
else --cb;
}
ans = max(ans, abs(ca-cb));
}
cout << ans << ENDL;
return 0;
}
// ................. main .................. //
void execute() {
input(), solve();
}
int main(void) {
#ifdef LOCAL_BOOKNU
freopen("input.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
#endif
cin.tie(0), ios_base::sync_with_stdio(false);
execute();
return 0;
}
// ......................................... //
B번
B번 문제: 구현
$m$개의 $[1..n]$들로 이루어진 배열이 주어진다.
$[1..n]$원소들을 하나의 그룹으로 묶을 수 있을 때 총 몇 개의 그룹이 나오는지 구해야 한다.
풀이 보기
그냥 크기 $n$짜리 배열을 0으로 초기화 한 후 각 수가 몇 번씩 등장하는 지를 센 다음 $min(cnt[1..n])$을 구하면 된다.
그런데 나는 처음에 문제를 잘못 보고 잘못된 코드를 바탕으로 코드를 짰기 때문에 이상하게 구현이 됐다.
소스코드 보기
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL_BOOKNU
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif
// ........................macro.......................... //
#define FOR(i, f, n) for(int (i) = (f); (i) < (int)(n); ++(i))
#define RFOR(i, f, n) for(int (i) = (f); (i) >= (int)(n); --(i))
#define pb push_back
#define emb emplace_back
#define fi first
#define se second
#define ENDL '\n'
#define sz(A) (int)(A).size()
#define ALL(A) A.begin(), A.end()
#define UNIQUE(c) (c).resize(unique(ALL(c)) - (c).begin())
#define next next9876
#define prev prev1234
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ii> vii;
typedef vector<vii> vvii;
typedef long long i64;
typedef unsigned long long ui64;
// inline i64 GCD(i64 a, i64 b) { if(b == 0) return a; return GCD(b, a % b); }
inline int getidx(const vi& ar, int x) { return lower_bound(ALL(ar), x) - ar.begin(); } // 좌표 압축에 사용: 정렬된 ar에서 x의 idx를 찾음
inline i64 GCD(i64 a, i64 b) { i64 n; if(a < b) swap(a, b); while(b != 0) { n = a % b; a = b; b = n; } return a; }
inline i64 LCM(i64 a, i64 b) { if(a == 0 || b == 0) return GCD(a, b); return a / GCD(a, b) * b; }
inline i64 CEIL(i64 n, i64 d) { return n / d + (i64)(n % d != 0); } // 음수일 때 이상하게 작동할 수 있음.
inline i64 ROUND(i64 n, i64 d) { return n / d + (i64)((n % d) * 2 >= d); }
inline i64 POW(i64 a, i64 n) {
assert(0 <= n);
i64 ret;
for(ret = 1; n; a = a*a, n /= 2) { if(n%2) ret *= a; }
return ret;
}
template <class T>
ostream& operator<<(ostream& os, vector<T> v) {
os << "[";
int cnt = 0;
for(auto vv : v) { os << vv; if(++cnt < v.size()) os << ","; }
return os << "]";
}
template <class T>
ostream& operator<<(ostream& os, set<T> v) {
os << "[";
int cnt = 0;
for(auto vv : v) { os << vv; if(++cnt < v.size()) os << ","; }
return os << "]";
}
template <class L, class R>
ostream& operator<<(ostream& os, pair<L, R> p) { return os << "(" << p.fi << "," << p.se << ")"; }
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) { cerr << " " << H, debug_out(T...); }
// ....................................................... //
const int MAXN = 1e5+10;
int n, m, ar[MAXN], vis[MAXN], cc[MAXN];
void input() {
cin >> n >> m;
FOR(i, 0, m) cin >> ar[i];
}
int solve() {
int sta = 0;
string ans;
FOR(i, 0, m) {
++cc[++vis[ar[i]]];
if(cc[sta+1] == n) {
++sta;
ans.pb('1');
} else ans.pb('0');
}
cout << ans << ENDL;
return 0;
}
// ................. main .................. //
void execute() {
input(), solve();
}
int main(void) {
#ifdef LOCAL_BOOKNU
freopen("input.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
#endif
cin.tie(0), ios_base::sync_with_stdio(false);
execute();
return 0;
}
// ......................................... //
C번
C번 문제: 기하
다음과 같이 $n$개의 반지름이 같은 원들로 둘러쌓인 안쪽에 원이 하나 더 있는 형태의 그림이 있다.
이 때 안쪽의 원의 반지름 $r$이 주어졌을 때 바깥쪽의 원의 반지름을 구해야한다.
풀이 보기
위 그림을 보면 바깥쪽 원의 중심을 이으면 정$n$각형이 나온다는 것을 알 수 있다.
또한 정$n$각형은 $n$개의 안쪽 이등변삼각형으로 이루어진다는 것을 이용하면 삼각함수를 이용해 안쪽 원의 반지름을 구할 수 있다.
위 그림에서 반으로 쪼개진 직각삼각형 쪽을 보면 파란색 변은 우리가 구해야 할 $x$, 연두색 변은 $x+r$이다.
따라서 $(x+r)\cos\theta = x$이고, 식을 전개하면 $x = \frac{r\cdot\cos\theta}{1-\cos\theta}$가 된다.
$\theta$는 정다각형의 한 내각의 반이므로 문제 없이 구할 수 있다.
소스코드 보기
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL_BOOKNU
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif
// ........................macro.......................... //
#define FOR(i, f, n) for(int (i) = (f); (i) < (int)(n); ++(i))
#define RFOR(i, f, n) for(int (i) = (f); (i) >= (int)(n); --(i))
#define pb push_back
#define emb emplace_back
#define fi first
#define se second
#define ENDL '\n'
#define sz(A) (int)(A).size()
#define ALL(A) A.begin(), A.end()
#define UNIQUE(c) (c).resize(unique(ALL(c)) - (c).begin())
#define next next9876
#define prev prev1234
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ii> vii;
typedef vector<vii> vvii;
typedef long long i64;
typedef unsigned long long ui64;
// inline i64 GCD(i64 a, i64 b) { if(b == 0) return a; return GCD(b, a % b); }
inline int getidx(const vi& ar, int x) { return lower_bound(ALL(ar), x) - ar.begin(); } // 좌표 압축에 사용: 정렬된 ar에서 x의 idx를 찾음
inline i64 GCD(i64 a, i64 b) { i64 n; if(a < b) swap(a, b); while(b != 0) { n = a % b; a = b; b = n; } return a; }
inline i64 LCM(i64 a, i64 b) { if(a == 0 || b == 0) return GCD(a, b); return a / GCD(a, b) * b; }
inline i64 CEIL(i64 n, i64 d) { return n / d + (i64)(n % d != 0); } // 음수일 때 이상하게 작동할 수 있음.
inline i64 ROUND(i64 n, i64 d) { return n / d + (i64)((n % d) * 2 >= d); }
inline i64 POW(i64 a, i64 n) {
assert(0 <= n);
i64 ret;
for(ret = 1; n; a = a*a, n /= 2) { if(n%2) ret *= a; }
return ret;
}
template <class T>
ostream& operator<<(ostream& os, vector<T> v) {
os << "[";
int cnt = 0;
for(auto vv : v) { os << vv; if(++cnt < v.size()) os << ","; }
return os << "]";
}
template <class T>
ostream& operator<<(ostream& os, set<T> v) {
os << "[";
int cnt = 0;
for(auto vv : v) { os << vv; if(++cnt < v.size()) os << ","; }
return os << "]";
}
template <class L, class R>
ostream& operator<<(ostream& os, pair<L, R> p) { return os << "(" << p.fi << "," << p.se << ")"; }
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) { cerr << " " << H, debug_out(T...); }
// ....................................................... //
double n, r;
void input() {
cin >> n >> r;
}
int solve() {
double st = 1.0*(n-2)/n/2.0;
double coss = cos(M_PI * st);
cout.precision(10);
cout << r*coss / (1-coss) << ENDL;
return 0;
}
// ................. main .................. //
void execute() {
input(), solve();
}
int main(void) {
#ifdef LOCAL_BOOKNU
freopen("input.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
#endif
cin.tie(0), ios_base::sync_with_stdio(false);
execute();
return 0;
}
// ......................................... //
후기
처음에 주어진 반지름 $r$이 바깥 원의 반지름인줄 알고 구현을 했다가 예제가 이상하게 나와서 당황했다.
또한 $\cos(x)$에 $x$를 라디안 형태($x\pi$)로 줘야 했지만, 실수로 $\pi$를 곱하지 않은 각도를 줘버려서 이상한 결과가 나와서 시간을 많이 버렸다.
D번
D번 문제: Interactive 그리디
문제가 장황하게 길지만, 살펴보면 별거 없다.
$999\times999$ 크기의 판이 주어지고, $1$개의 킹, $666$개의 룩의 현재 위치가 주어진다.
킹과 룩은 기존 체스와는 약간 다르게 움직인다.
킹의 경우는 플레이어가 움직이며, 플레이어가 게임이 시작하면 선을 잡는다.
- 룩이 있는 곳으로 가지 못한다.
- 움직일 수 있는 범위는 일반 킹의 경우와 같다. (상하좌우 대각선 범위 1 이내)
- 룩과 같은 행, 열로 갈 수 있다. (이런 경우가 우리의 최종 목적(체크 당하기)이다.)
- 킹이 룩에 의해 체크를 당한 경우 플레이어가 이긴 것으로 판단한다.
즉, 다른점이라고 한다면 룩을 먹지 못하고, 스스로 체크 당하러 갈 수 있다는 것이다.
룩을 살펴보면
룩의 경우는 시스템이 움직이며, 항상 킹이 움직인 뒤에 움직인다.
- 현재 룩의 좌표가 어떻든, 킹과 룩이 없는 아무 빈 곳으로나 움직일 수 있다. (아예 안 움직일 수도 있다.)
- 킹과 같은 행, 열로 가지 못한다. (즉, 킹이 체크당하면 플레이어가 이기는데, 스스로 체크를 하러 가지 못한다.)
이 때, $2000$턴 이내에 킹이 체크당하도록 움직이는 것이 우리의 목표이다.
인터랙티브 방식은 우리가 킹을 다음 좌표 $(x, y)$로 움직이면, 시스템이 $k$번째 룩을 $(x, y)$로 움직였다는 정보를 준다.
풀이 보기
룩의 2번 조건 때문에 킹이 스스로 룩의 범위로 들어가지 않는 한 운 좋게 룩이 와줘서 이기는 경우는 없다.
또한 룩의 공격범위에 들어간다고 생각하지 말고, 룩은 아무 기능도 안 하고 움직이기만 하는데 킹이 룩의 공격범위를 갖고 룩을 잡으러 다닌다고 생각해보자.
시스템이 영리하게 플레이한다고 가정했을 때 룩에게 점점 다가갈 때 도망을 갈 수단이 없어야 이길 수 있다.
이것을 위해 룩은 아무 좌표로나 이동할 수 있다는 사기성을 지니고 있지만, 한 턴에 한 개의 룩 밖에 움직이지 못한다는 약점을 이용해야 한다.
그러려면 킹이 점점 룩들을 몰아넣어 놓고 조여가는 것이 가장 이상적일 것이다.
그 중에서도 가장 좋은 방법은 킹이 맵의 정중앙$(500, 500)$에서 시작하는 것이고, 아래와 같이 한 쪽 대각선으로 움직이며 조여가게 하는 것이다.
일단 한 쪽 대각선으로 쭉 움직이는 것은 알겠는데, 네 대각선 방향 중 어느 곳으로 움직여야 할까?
해당 대각선으로 움직이고 있다고 가정할 경우, 최악의 경우는 시스템이 조여지는 범위 내의 룩들을 모두 대각선의 반대방향으로 이동시켜버리는 것이다.
즉, 그림에서 파란색 부분을 대각선 반대 방향의 흰색으로 움직이는 경우이다.
이런 최악의 경우를 생각하면, 플레이어는 킹을 최대한 조여지는 대상 룩이 많은 대각선 방향으로 움직여야 한다.
즉, 파란색 부분에 룩들이 가장 많이 포함되는 방향으로 이동해야 한다는 것이다.
이런 방법으로 반드시 킹은 체크 당할 기회가 있다는 것은 아래와 같이 쉽게 증명할 수 있다.
[ 증명 ]
룩은 총 $666$개인데, 킹을 정중앙으로 놓았을 때 정말 운이 좋지 않은 경우는 4방향 모두 고르게 룩이 분포되는 것일 것이다.
그렇게 되면 어떤 방향으로 조이든 총 룩의 $\frac{3}{4}$밖에 조이는 대상이 되지 않지만, $666 \cdot \frac{3}{4} = 499.5$이므로 킹이 대각선 끝까지 갈 동안 499번의 움직임을 소모한다는 것을 감안하면 무조건 킹은 체크 당할 기회가 있는 것이다.
이동할 대각선을 구하는 것에 대한 구현은 약간 트릭을 사용해서 구현했는데 봐두면 좋을 것 같다.
소스코드 보기
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL_BOOKNU
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif
// ........................macro.......................... //
#define FOR(i, f, n) for(int (i) = (f); (i) < (int)(n); ++(i))
#define RFOR(i, f, n) for(int (i) = (f); (i) >= (int)(n); --(i))
#define pb push_back
#define emb emplace_back
#define fi first
#define se second
#define ENDL '\n'
#define sz(A) (int)(A).size()
#define ALL(A) A.begin(), A.end()
#define UNIQUE(c) (c).resize(unique(ALL(c)) - (c).begin())
#define next next9876
#define prev prev1234
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ii> vii;
typedef vector<vii> vvii;
typedef long long i64;
typedef unsigned long long ui64;
// inline i64 GCD(i64 a, i64 b) { if(b == 0) return a; return GCD(b, a % b); }
inline int getidx(const vi& ar, int x) { return lower_bound(ALL(ar), x) - ar.begin(); } // 좌표 압축에 사용: 정렬된 ar에서 x의 idx를 찾음
inline i64 GCD(i64 a, i64 b) { i64 n; if(a < b) swap(a, b); while(b != 0) { n = a % b; a = b; b = n; } return a; }
inline i64 LCM(i64 a, i64 b) { if(a == 0 || b == 0) return GCD(a, b); return a / GCD(a, b) * b; }
inline i64 CEIL(i64 n, i64 d) { return n / d + (i64)(n % d != 0); } // 음수일 때 이상하게 작동할 수 있음.
inline i64 ROUND(i64 n, i64 d) { return n / d + (i64)((n % d) * 2 >= d); }
inline i64 POW(i64 a, i64 n) {
assert(0 <= n);
i64 ret;
for(ret = 1; n; a = a*a, n /= 2) { if(n%2) ret *= a; }
return ret;
}
template <class T>
ostream& operator<<(ostream& os, vector<T> v) {
os << "[";
int cnt = 0;
for(auto vv : v) { os << vv; if(++cnt < v.size()) os << ","; }
return os << "]";
}
template <class T>
ostream& operator<<(ostream& os, set<T> v) {
os << "[";
int cnt = 0;
for(auto vv : v) { os << vv; if(++cnt < v.size()) os << ","; }
return os << "]";
}
template <class L, class R>
ostream& operator<<(ostream& os, pair<L, R> p) { return os << "(" << p.fi << "," << p.se << ")"; }
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) { cerr << " " << H, debug_out(T...); }
// ....................................................... //
const int MAXN = 1e3;
const int dy[4] = { 1, 1, -1, -1 }, dx[4] = { 1, -1, 1, -1 };
int ky, kx, cc[4], ry[MAXN], rx[MAXN], m[MAXN][MAXN];
void input() {
cin >> kx >> ky;
m[ky][kx] = -1;
FOR(i, 1, 667) cin >> rx[i] >> ry[i], m[ry[i]][rx[i]] = i;
}
bool moverock() {
int k, y, x; cin >> k >> x >> y;
if(k == -1 && y == -1 && x == -1) return true;
m[ry[k]][rx[k]] = 0;
m[y][x] = k;
ry[k] = y, rx[k] = x;
return false;
}
bool moveking(int y, int x) {
if(m[y][x] != 0) return false;
m[ky][kx] = 0;
m[y][x] = -1;
ky = y, kx = x;
cout << kx << ' ' << ky << ENDL;
return true;
}
int solve() {
// 일단 king 중앙으로 옮기기
while(ky != 500 || kx != 500) {
int ny = ky == 500 ? ky : ky + (500-ky)/abs(500-ky), nx = kx == 500 ? kx : kx + (500-kx)/abs(500-kx);
if(!moveking(ny, nx)) assert(moveking(ky, nx));
if(moverock()) return 0;
}
// 반대방향 구하기
FOR(i, 0, 1000) FOR(j, 0, 1000) if(m[i][j] > 0) ++cc[(i < 500 ? 0 : 2) + (j < 500 ? 0 : 1)];
int md = min_element(cc, cc+4) - cc;
// 대각선으로 이동
while(1) {
int ny = ky + dy[md], nx = kx + dx[md];
if(!moveking(ny, nx)) assert(moveking(ky, nx));
if(moverock()) return 0;
}
return 0;
}
// ................. main .................. //
void execute() {
input(), solve();
}
int main(void) {
#ifdef LOCAL_BOOKNU
freopen("input.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
#endif
execute();
return 0;
}
// ......................................... //
후기
처음에는 아래와 같이 실수로 $1,000$을 $100$으로 적는 바람에 런타임 에러가 발생해서 첫 번째로 멘탈이 깨졌고,
FOR(i, 501, 100)
...
두 번째 제출 때는 dy, dx를 잘못 적어서 엉뚱한 대각선으로 이동하는 바람에 WA가 발생해서 두 번째로 멘탈이 깨졌다.
const int dy[4] = { 1, -1, 1, -1 }, dx[4] = { 1, 1, -1, -1 };
다행히 라운드가 끝나기 12분 전에 실수를 찾아 고쳐서 AC를 받았지만, 딱히 테스트 할 방법이 없는 인터랙티브 문제에서 AC가 안 뜨면 너무 답답한 것 같다.
후기
B 잘못 읽어서 삽질하고, C 잘못 읽고 삼각함수에 익숙하지 않아 삽질하는 바람에 C까지 풀었을 때 등수가 $1200$등이어서 상당히 멘탈이 깨졌었다.
D를 풀면서 보니 C까지 푼 사람들은 많았지만, D, E, F를 푼 사람은 두 자리수 단위였다.
따라서 D를 풀면 $200$등, 못 풀면 $1400$등이라는 끔찍한 갭이 생기는데, 하필이면 D가 인터랙티브 문제고 문제도 뭔가 복잡해보여서 절망했었다.
하지만 차근차근 생각하다보니 결국은 풀었고 끝까지 포기하지 말고 푸는게 중요하다는 것을 다시 한 번 느꼈다.
코드포스 결과
