작년에 이어서 올해에도 구글 코드잼에 참가했는데, 작년에는 2라운드 진출까지만 하고, 2라운드에서는 그냥 던져버렸었다. 올해에는 좀 더 나아진 모습을 보여주고자 했는데 결국 라운드 1C까지 왔다.
구글 코드잼은 Qualification Round이후 Round 1로 넘어가는데, 1라운드의 경우 A,B,C로 총 3번의 기회가 있다. 각각의 라운드에서 1500등 안에 들면 다음 라운드인 Round 2로 진출하게 되고, A라운드에서 1500등 안에 들어서 다음 라운드로 진출하게 되면 다음 B, C라운드는 참여할 수 없다.
즉 각각 A,B,C 라운드 별 1500명이 다음 라운드로 진출하게 되어 결과적으로는 4500명이 Round 2로 진출하게 된다. 그런데 올해 구글 코드잼의 등록자는 역대급이라고 하며(근데 매년 등록자의 수가 늘어난다고는 한다) 라운드 1A, 1B에서 처참하게 발려버려서 자신감이 꽤나 떨어져있는 상태였다.
대충 처참한 나의 이전 라운드 성적이다.
하지만 이번 라운드에선 아슬아슬하긴 하지만 어째 저째 다음 라운드로 진출하게 될 것 같다.
In review 상태인데, 뭐 부정행위를 한 것도 아니고 1389등을 했으니 Round 2를 체험해볼 수 는 있을 것 같다. 다만 좀 걱정이 되는 것은 Round 2가 DEFCON CTF Qualification Round와 일정이 겹친다는 것... 뭐 코로나 때문에 일정이 더 밀릴수도 있긴 하겠지만 애매한 것은 사실이긴 하다.
어쨋든 기적적으로 라운드 2로 진출하게 되었으니 당분간은, 어차피 이 글을 쓰는 시기로 부터는 열흘밖에 시간이 없긴 하지만 PS 공부를 좀 더 해봐야 겠다.
1. Overexcited Fan
1번 문제인데, 생각보다 너무 쉽게 나왔어서 오히려 걱정이 되었다. 빨리 풀기 대결이 되지 않을까 하는 그러한 우려이다. 어차피 상대평가라 난이도가 너무 쉬우면 오히려 불리하게 작용할 때도 있었다.
움직이는 녀석을 가장 빨리 만날 수 있는 시간대를 찾는 문제인데, 이동 거리를 L1 Distance(맨하탄 거리)로 바로 알아낼 수 있고, 이동하거나 멈추거나 둘 다 가능하므로, 이동경로별로 원점에서의 맨하탄 거리보다 현재 시간이 더 긴 순간이 만나는 순간이 되겠다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define endl '\n'
const int dx[] = { +1, -1, 0, 0 };
const int dy[] = { 0, 0, +1, -1 };
int val(char c) {
if (c == 'S') return 3;
if (c == 'N') return 2;
if (c == 'W') return 1;
return 0;
}
void solve() {
int x, y;
string steps;
cin >> x >> y;
cin >> steps;
int ans = -1;
for (size_t i = 0; i < steps.size(); i++) {
int k = val(steps[i]);
x += dx[k];
y += dy[k];
int dist = abs(x) + abs(y);
if (dist <= i + 1) {
ans = i + 1;
break;
}
}
if (ans == -1) {
cout << "IMPOSSIBLE\n";
}
else {
cout << ans << endl;
}
}
int main() {
int tc; cin >> tc;
for (int t = 1; t <= tc; t++) {
printf("Case #%d: ", t);
solve();
}
}
2. Overrandomized
꽤나 신박한 내용의 문제였다. TC가 3가지로 나뉘는데, 마지막 TC의 경우 //(Q=-1//)로 고정이라는 것이 어떻게 보면 힌트가 좀 되었다.
문제 조건을 보면, N, R, D가 각각 chosen independently and uniformly at random from~ 과 같은 제약사항이 있다.
따라서 랜덤의 upper-bound역시 랜덤이므로, 이 값들은 순서는 중구난방이겠지만, 결국은 계단과 같은 모양으로 나타나게 될 것이다. //(10^4//)개의 쿼리 값들을 알려주니 대충 아래와 같은 형식으로의 값들이 나타난다고 볼 수 있겠다.
rand() % 10
rand() % 20
rand() % 30
rand() % 40
...
rand() % 100
이렇게 되면 아무래도 맨 앞자리의 수가 1로 시작하는 수의 값이 맨 앞자리의 수가 2로 시작하는 녀석보다는 많을 것이고, 2로 시작하는 녀석은 3으로 시작하는 녀석보다 많을 것이고.. 와 같은 통계적 상관관계가 나타날 것이다.
이러한 점을 이용해서 가장 앞자리에 나타나는 알파뱃의 출연 빈도를 체크해서 내림차순으로 정렬하면 이 알파뱃들이 1부터 9의 숫자를 나타낼 것이다.
또한 0의 경우는 첫번째 자리에서만 나타날 수 없는 수이므로, 전체 나타난 알파뱃 중 맨 앞자리에 나타나는 알파뱃들을 빼면 나오게 될 것이다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define endl '\n'
#define NUMTC 10000
typedef pair<ll, string> pis;
typedef pair<ll, char> pic;
ll cnt[30];
void solve() {
set<char> occurs;
set<char> nonzero;
occurs.clear();
nonzero.clear();
memset(cnt, 0, sizeof(cnt));
int U;
pis arr[NUMTC + 5];
vector<pic> ans;
ans.clear();
char output[11];
cin >> U;
for (int i = 0; i < NUMTC; i++) {
cin >> arr[i].first >> arr[i].second;
}
for (int i = 0; i < NUMTC; i++) {
auto& s = arr[i].second;
nonzero.insert(s[0]);
//첫번째만 셈
cnt[s[0] - 'A']++;
for (char c : s) {
occurs.insert(c);
}
}
for (int i = 0; i < 30; i++) {
if (cnt[i]) {
ans.push_back(make_pair(cnt[i], i + 'A'));
}
}
for (auto c : nonzero) {
occurs.erase(c);
}
char zero = *occurs.begin();
sort(ans.begin(), ans.end(), greater<pic>());
for (int i = 0; i < 9; i++) {
output[i+1] = ans[i].second;
}
output[0] = zero;
output[10] = 0;
printf("%s\n", output);
return;
}
int main() {
int tc; cin >> tc;
for (int t = 1; t <= tc; t++) {
printf("Case #%d: ", t);
solve();
}
}
3. Oversized Pancake Choppers
이 문제는 고생을 꽤 했다. 마지막 문제 답게 난이도도 꽤 어려웠던 것 같은 느낌이다.
근데 사실 아이디어는 어느정도 생각을 해서 Middle TC는 맞출 수 있을 것 같았는데 한가지 조건을 빼 먹어서 업솔빙하면서도 많이 틀려먹었다.
결국 wwiiiii님의 코드를 참고한 뒤 힌트를 얻었다.
analysis를 보고 미들 TC를 맞추는 풀이까지만 적용해서 풀어보았다.
조각의 크기를 //(Ai//)중 하나로만 가능하다고 생각한 고정관념에 따라 틀려버렸는데, 조각의 크기는 //(Ai / k//)가 가능하고, 이때 //(k//)는 1과 //(D//)사이의 수가 된다.
analysis에서 Time Complexity가 //(O(D*N^2)//)라고 했을때, D가 왜 들어가나 이해를 못했는데 이것 때문이었다.
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
#define MAXN 305
ll A[MAXN];
void solve() {
ll N, D;
cin >> N >> D;
ll ans = D - 1;
for (int i = 0; i < N; i++) {
cin >> A[i];
}
sort(A, A + N);
// K를 perfect-cut 개수라고 하면 D - K가 정답이 된다.
for (int i = 0; i < N; i++) {
for (ll k = 1; k <= D; k++) {
ll unit = A[i];// 조각의 크기는 unit / k이다.
ll pieces = 0; //조각의 개수
for (int j = 0; j < N; j++) {
ll chunk = A[j];
pieces += chunk * k / unit;
}
if (pieces < D) continue; //다 잘라도 이 조각 개수가 안나오는 경우 skip
pieces = 0;
int K = 0; // 모두 다 떨어지는 조각 개수
for (int j = 0; j < N; j++) {
ll chunk = A[j];
ll add = chunk * k / unit;
if ((chunk * k) % unit == 0 && pieces + add <= D) {
pieces += add;
K++;
}
}
ans = min(ans, D - K);
}
}
cout << ans << endl;
}
int main() {
int tc; cin >> tc;
for (int t = 1; t <= tc; t++) {
printf("Case #%d: ", t);
solve();
}
}
TC 3에 대한 솔루션 코드 업솔빙은 나중에 시간나면 해보도록 하겠다..... 나중에 스코어 보드를 보니, 한국인 참가자 중에서는 TC3를 맞춘 사람이 1명도 없었다. 코드를 보니 아이디어는 대충 비슷하게 구현은 한 것 같은데 다들 TLE가 나서 그런듯 하다.
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define MAXN 100005
string arr[MAXN];
map<string, int> mm;
int main() {
int n, m;
cin >> n >> m;
ios::sync_with_stdio(false);
cin.tie(NULL);
for(int i=1 ;i <= n; i++) {
string s;
cin >> s;
arr[i] = s;
mm[s] = i;
}
for (int i=0; i < m; i++) {
string v;
cin >> v;
if (v[0] >= 'A') {
cout << mm[v] << endl;
} else {
int idx = atoi(v.c_str());
cout << arr[idx] << endl;
}
}
}
하 C++로 하면 이렇게 간단하게 코드를 짤 수 있는데... 근데 보니깐 sync_with_stdio(false)를 넣지 않으면 TLE가 나는걸로 봐서는 아마 러스트 코드에서 TLE가 나는것은 Scanner가 느리거나, 인풋 받는데 vector를 선언해서 받고 하는데 이런게 느려서 그런거지 않을까 싶다.
올해 킥스타트 B라운드는 주말 아침8시에 시작을 해서, 어째저째 술먹고 새벽에 퍼질러 자다가 비몽사몽한상태에서 용캐 일어나서 한번 풀어보았다.
코드잼 1Round에서 엄청 발렸던 기분을 Kickstart를 풀면서 조금 달래주려 했는데, 확실히 Kickstart는 Codejam에 비해서는 난이도가 낮은 듯 한 느낌을 많이 받았다.
총 4문제가 나왔고, 예전에는 Large set은 Full feedback을 안주고 Hidden verdict형식이었는데, 이번에는 다 Visible verdict로 진행이 되었다.
Bike Tour
봉우리 갯수를 새는 문제이다. for loop로 순회하면서 좌우 값을 봐서 그 보다크면 봉우리로 갯수를 카운트 하면 되는 간단한 문제이다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define endl '\n'
int arr[105];
void solve() {
int n;
int ans = 0;
cin >> n;
for (int i = 0; i < n; i++) cin >> arr[i];
for (int i = 1; i < n - 1; i++) {
if (arr[i] > arr[i - 1] && arr[i] > arr[i + 1]) ans++;
}
cout << ans << endl;
}
int main() {
int tc; cin >> tc;
for (int t = 1; t <= tc; t++) {
printf("Case #%d: ", t);
solve();
}
}
Bus Routes
버스가 오는 시간 주기를 알때, 마지막 버스를 탈 수 있는 가장 늦은 시간을 구하는 문제이다. 배수개념으로 접근하면 될 것 같은데, 파라메트릭 서치를 이용하면 간단하게 풀 수 있다. 쿼리를 바이너리 서치로 확인하는건데, 쿼리 확인시에는 floor(v/x) * x를 해서 가장 가까운 배수를 찾아내면 된다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define endl '\n'
ll a[1005];
int n;
ll d;
bool q(ll v) {
for (int i = 0; i < n; i++) {
ll x = a[i];
v = max(v, (v + x - 1) / x * x);
if (v > d)
return false;
}
return true;
}
void solve() {
ll l, r;
l = 1;
//r = (ll)1e12;
cin >> n >> d;
r = d;
for (int i = 0; i < n; i++) {
cin >> a[i];
}
while (l < r) {
ll m = (l + r + 1) / 2;
//printf("%lld %lld %lld\n", l, r, m);
if (q(m)) {
l = m;
}
else {
r = m - 1;
}
}
cout << l << endl;
}
int main() {
int tc; cin >> tc;
for (int t = 1; t <= tc; t++) {
printf("Case #%d: ", t);
solve();
}
}
Robot Path Decoding
문제 내용 자체보다는, Operation code 파싱이 더 어렵다. (를 만나면 같은 depth의 )의 인댁스를 찾아서 재귀로 짜보려다가 //(O(N^2)//)인데 TLE안나려나 궁금했다가 그냥 스택으로 짜는게 더 나을거 같아서 머리를 쥐어 짜면서 스택으로 파서를 만들어 보았다. 생각보다 파서가 간단하게 만들어 졌던 것 같다. 좌표계가 wrap-around되므로 그 부분을 처리해주는 함수를 따로 만들어서 썼다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define endl '\n'
const ll MOD = 1e9;
ll nor(ll v) {
if (v < 0)
v += MOD;
if (v >= MOD)
v %= MOD;
return v;
}
struct Data {
int op;
ll x, y;
void add(struct Data& rhs) {
x += rhs.x;
y += rhs.y;
x = nor(x);
y = nor(y);
}
void mult(int v) {
x *= v;
y *= v;
x = nor(x);
y = nor(y);
}
};
Data calc(char c) {
if (c == 'N') {
return { 0, -1, 0 };
//return make_pair(-1, 0);
}
else if (c == 'S') {
return { 0, 1, 0 };
//return make_pair(+1, 0);
}
else if (c == 'W') {
return { 0, 0, -1 };
//return make_pair(0, -1);
}
else if (c == 'E') {
return { 0, 0, 1 };
//return make_pair(0, +1);
}
else {
assert(false);
}
}
void solve() {
string s;
cin >> s;
//ll x, y;
//x = y = 0;
stack<Data> ss;
ss.push({ 0, 0, 0 });
for (int i = 0; i < s.length(); i++) {
char c = s[i];
if (c >= '0' && c <= '9') {
ss.push({ c - '0', 0, 0 });
ss.push({ 0, 0, 0 });
}
else if (c == ')') {
Data operand = ss.top(); ss.pop();
Data mult = ss.top(); ss.pop();
Data prev = ss.top(); ss.pop();
operand.mult(mult.op);
prev.add(operand);
ss.push(prev);
}
else if (c >= 'A' && c <= 'Z') {
Data cur = ss.top(); ss.pop();
Data delta = calc(c);
cur.add(delta);
ss.push(cur);
}
}
ll y = (ss.top().y + 1);
ll x = (ss.top().x + 1);
cout << y << ' ' << x << endl;
while (ss.size()) ss.pop();
//x++; y++;
//cout << y << ' ' << x << endl;
}
int main() {
int tc; cin >> tc;
for (int t = 1; t <= tc; t++) {
printf("Case #%d: ", t);
solve();
}
}
Wandering Robot
kickstart때는 못풀어서 나중에 Analysis랑 남의 코드들을 보고 업솔빙을 좀 했다. 아이디어 자체는 대충 냈었는데, 어차피 디테일부분을 못따라가서 구현법 팁을 알았어도 당시에는 못 풀었을 듯 하다.
1등한 사람의 코드도 좀 참고를 하고 이해안가는 부분을 동기형한테는 물어보고 해서 도움을 꽤 받았다.(사실 아직도 100%는 이해 안 된 것 같기도하고...)
이항계수를 구하는 부분에서 Precision Error가 많이 날 것 같았는데 결국 요구하는 정확도가 //(10^{-5}//)정도로 낮은 수준이기도 하고, log로 축소시켜서 계산한 뒤 다시 역로그(exp함수)로 되돌려서 계산하는 부분들이 신박했다.
근데 여기서 좀 쟁점이 되는 부분은 대각선이 딱 맞아떨어지지 않는 경우가 쟁점인데, 아래 그림을 보자.
참고로 아래 문단에서 구한다고 하는 것은 시작점을 //((0,0)//)라고 가정하고 도착지점 좌표를 //((x,y)//)라고 가정하면
//(\frac{1}{2}^{x+y}*\binom{x+y}{x}//)를 의미한다. 이를 //(f(x,y)//)라고 하자.
파란색들은 독립적으로 되기 때문에 각자 구해서 더하면 되는데, 파란색 위쪽에 비어있는 칸으로 가는 경우는 쟁점이 된다.
오른쪽 끝에 다다른 경우 무조건 아래로만 가기 때문에 해당 부분에 대한 내용들도 더해줘야 하는데, 이는 빨간색 박스에 도달하는 경우(실제로는 벽을 뚫을 순 없지만 뚫을 수 있다고 가정할 시)를 더해주면 된다. 어차피 벽을 뚫는경우 아래로 내려가는걸로 취급하면 되므로 그러하다.
근데 1등 코드를 확인해보면 노란색으로 가는 확률(f(노랑칸))에 1/2를 곱해서 더해버리는 식이다. 사실 노랑색 바로 아래 파란색(C) 입장에서는 바로 위 노란색(B)에서 아래로 1/2확률로 내려오는 것만 포함되어 있는데, 바로 위 노란색(B)에서 오른쪽으로 가는 경우의 확률도 더해져야 하므로 노란색으로 도달하는 확률에 1/2를 곱해서 더한다.
그리고 마찬가지로 가장 아래 노란색(B)으로 가는 확률은 바로 위 노란색(A)에서 1/2확률로 내려온경우는 포함되지만, 맨 위 노란색에서 오른쪽으로 가서 내려오는 경우확률이 빠져있으므로 이도 더해주는 식이라고 한다.(thanks for jrj) 각 부분의 정의를 명확하게 해줘야지 안햇갈린다고 한다.
설명하면서도 내가 약간 햇갈려서 첨언을 하자면, 대각선으로 구역을 나누는 경우 서로 겹치는 경우가 없으므로(독립이므로) 확률을 구해서 더해버리면 되는데, 노란색(B)의 경우와 아래 파란색(C)의 경우는 겹치는 경우가 있다. 그러므로 겹치지 않는 경우 중에 세어지지 않은 부분만 추가적으로 더해주는 것이다. 노란색(A, B)의 경우에서는 오른쪽으로 갈 확률이 0%이므로 이 부분만 따로 추가로 더해주는 것이고, 아래로 가는 확률이 100%, 오른쪽이 0%인데 이것이 50% 50%으로 더해져 있으므로, 부족한 아래로 가는 50%를 더해주는 것이다.
내가 착각을 했던 것이, A,B의 경우가 무조건 C까지 가야만 한다고 생각을 했는데, 어차피 C에는 A,B 경우의 수 중 절반은 더해져 있는 상황이고, 이 남은 절반만 더해주면 된다는 것이다. 이 남은 절반의 확률은 맨 오른쪽에서는 아래로만 내려가는 선택지만 생긴다는 특수한 상황때문에 생기는 것이기도 하다.
그리고 역으로 전체에서 중간 구멍으로 빠질 확률을 빼줘도 되는데, f(초록칸)을 죄다 구한 뒤 1/2를 곱해서 더하면 된다고 한다. 그리고 1에서 그 값을 빼줘도 될 것 같은데 아직 구현은 안해봤다.
아래 코드는 빨간칸을 구해서 다 더하는 방식의 코드이다.
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
#define MAXN 200005
double lnfact[MAXN];
double bicof(int a, int b) {
return lnfact[a] - lnfact[a - b] - lnfact[b];
}
void solve() {
int W, H, L, U, R, D;
cin >> W >> H >> L >> U >> R >> D;
int dist = L + D - 2;
double ans = 0;
if (D < H) {
for (int i = 1; L - i > 0; i++) {
int x = L - i;
int y = D + i;
double logval = bicof(dist, x - 1);
logval -= dist;
ans += pow(2, logval);
}
}
dist = R + U - 2;
if (R < W) {
for (int i = 1; U - i > 0; i++) {
int x = R + i;
int y = U - i;
double logval = bicof(dist, x - 1);
logval -= dist;
ans += pow(2, logval);
}
}
cout << fixed << setprecision(8);
cout << ans << endl;
}
int main() {
for (int i = 2; i < MAXN; i++) {
lnfact[i] = lnfact[i - 1] + log(i) / log(2);
}
int tc;
cin >> tc;
for (int t = 1; t <= tc; t++) {
cout << "Case #" << t << ": ";
solve();
}
}
끝나고 나서 맞은 상황이다. Interactive Problem이라서 디버깅 환경 구축하는 것도 꽤 귀찮고 했었다.
일단 푼 문제들 간단하게 리뷰를 해보자.
1. Vestigium (7pt)
첫번째 문제 답게 매우 쉬웠던걸로 기억한다. Latin square matrix라고 각 오와 열에 1부터 N까지의 수가 1번씩만 나타나는 녀석에서 왼쪽위부터 오른쪽아래로 되는 대각선의 값들의 합이 trace라고 하는데 임의의 matrix가 주어질 때, 이 trace를 구하고, Latin square rule을 위반하는 row와 column의 수를 출력하면 되는 그런문제이다.
하나하나 다 따라가면서 체크하면 답이 나온다. 문제 이해하는데 시간을 더 쓴 것 같다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void solve() {
int trace = 0, duprow = 0, dupcol = 0;
int matrix[105][105];
int n;
cin >> n;
int check[105];
for (int i = 0; i < n; i++) {
memset(check, 0, sizeof(check));
for (int j = 0; j < n; j++) {
int v;
cin >> v;
matrix[i][j] = v;
check[v]++;
if (i == j) trace += v;
}
int correct = 0;
for (int i = 1; i <= n; i++) {
if (check[i] == 1) correct++;
}
if (correct != n) {
duprow++;
}
}
for (int i = 0; i < n; i++) {
memset(check, 0, sizeof(check));
for (int j = 0; j < n; j++) {
int& v = matrix[j][i];
check[v]++;
}
int correct = 0;
for (int i = 1; i <= n; i++) {
if (check[i] == 1) correct++;
}
if (correct != n) {
dupcol++;
}
}
cout << trace << ' ' << duprow << ' ' << dupcol << endl;
}
int main() {
int tc; cin >> tc;
for (int t = 1; t <= tc; t++) {
printf("Case #%d: ", t);
solve();
}
}
2. Nesting Depth (5pts, 11pts)
문자열 다루는 문제 같은 문제인데, 숫자가 나오면, 각각의 숫자는 자신을 둘러싼 괄호가 자신의 숫자만큼 나와야 한다. Greedy하게 이전 숫자보다 큰 숫자가 나오면 여는 괄호를 더 열어주고, 더 작은 숫자가 나오면 닫아주고, 마지막에 다 닫아주면 된다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void solve() {
string s;
string ans = "";
cin >> s;
//int opened = 0;
int prev = 0;
for (char c : s) {
int cur = c - '0';
if (cur > prev) {
int diff = cur - prev;
//diff만큼 더 연다
for (int i = 0; i < diff; i++) {
ans += "(";
}
}
else if (cur < prev) {
int diff = prev - cur;
for (int i = 0; i < diff; i++) {
ans += ")";
}
}
prev = cur;
ans += c;
}
if (prev > 0) {
while (prev--) {
ans += ")";
}
}
cout << ans << endl;
}
int main() {
int tc; cin >> tc;
for (int t = 1; t <= tc; t++) {
printf("Case #%d: ", t);
solve();
}
}
3. Parenting Partnering Returns(7pts, 12pts)
부모 두명이서 아기 돌보는 스케쥴?을 각자 스케쥴링 하는데, 가능하게 스케쥴링 하면 되는 문제이다. 각각 task가 시작하는 시간 기준으로 정렬을 한 뒤, 그리디하게 지금 일 가능한 녀석들을 스케쥴링 해주면 된다.
소팅하기 전에 원래 Index 기준으로 답을 입력해야 하는 것을 깜빡해서 한번 WA를 받았다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
string mark[2] = { "C", "J" };
void solve() {
int fins[2];
fins[0] = fins[1] = 0;
int resp[1005];
memset(resp, -1, sizeof(resp));
int n;
vector<pair<pii, int>> tasks;
tasks.clear();
cin >> n;
for (int i = 0; i < n; i++) {
int s, e;
cin >> s >> e;
tasks.push_back(make_pair(make_pair(s, e), i));
}
sort(tasks.begin(), tasks.end());
for (auto task : tasks) {
bool alloced = false;
for (int candid = 0; candid < 2; candid++) {
if (fins[candid] <= task.first.first) {
fins[candid] = task.first.second;
//ans += mark[candid];
resp[task.second] = candid;
alloced = true;
break;
}
}
if (alloced == false) {
cout << "IMPOSSIBLE" << endl;
return;
}
}
string ans = "";
for (int i = 0; i < n; i++) {
ans += mark[resp[i]];
}
cout << ans << endl;
}
int main() {
int tc; cin >> tc;
for (int t = 1; t <= tc; t++) {
printf("Case #%d: ", t);
solve();
}
}
interactive_runner.py는 -- 기준으로 왼쪽에 있는 command와 오른쪽에 있는 command를 각각 쓰레드로 실행시킨 뒤, stdin/stdout를 각각 연결해주는 역할을 한다.
python3 judge.py 0라고 실행하면 서버가 어떻게 응답하는지를 확인해볼 수 있다. 0을 인자로 넣으면 1번째 test set(b=10)이 나오고, 1를 인자로 넣으면 2번째 test set(b=20)이 적용된다.
맨처음에 문제 내용을 이해하는데에도 꽤나 오래걸렸었다. 문제를 잘 이해못하고 테스팅 툴을 이해못해서, 파이썬 코드를 뜯어서 분석해 보기도 했었다.
문제 내용을 대충 설명해보자면, B bit의 임의의 수를 서버에서 지정한다. 이 값을 우리가 맞추면 되는데, 최대 150번의 쿼리가 가능하다. 각 쿼리를 하기 위해서 1~B에 해당하는 정수 하나를 보내면 그 쿼리 번째 bit값을 리턴해준다. 근데 10번 요청을 할 때 마다 서버에 저장된 B bit가 랜덤한 확률로 값이 바뀌게 된다. 50%확률로 Negation 연산이 일어나고(1이 0이 되고, 0이 1이 된다), 50%확률로 Reverse 연산이 일어나서 1번 비트가 B번 비트로, 2번 비트가 B-1번 비트가 되고 이런식으로 바뀌게 된다.
따라서 25%확률로 Negation만 일어나고 25%확률로 Reverse만 일어나고 25%확률로 Negation과 Reverse가 동시에 일어나고, 25%확률로 아무일도 안일어난다.
서버에 저장된 bit를 맞추는 것은 Negation, Reverse가 일어난것을 다 쳐서, 답을 맞추는 시점에 맞는 bit이기만 하면 정답처리가 된다. 그리고 정답을 제출하는 것은 Query로 안친다고 한다.
1번째 test set는 각 비트별로 값을 한번씩 다 물어본 뒤 이어서 응답을 주면 풀린다. 10번 쿼리를 했지만, 답변하는 것은 쿼리가 아니므로 비트 변조가 안일어난 상태이다.
2번째만을 위한 답 코드 말고 3번째에도 해당되는 솔루션을 생각했는데 대략 다음과 같다.
일단 bit값들을 앞에서부터 5개, 뒤에서부터 5개씩 해서 10개씩 받는다. 그러면 그 10개의 뭉치는 바뀌어도 같은 시점에 바뀌기 때문에 초기 값은 같은그룹들을 모을 수 있다.
첫번째 그룹은 [1~5]비트와 [96~100] 비트가 된다. 두번째 그룹은 [6~10]비트와 [91~95]비트가 된다.
같은 그룹끼리는 Reverse가 되어도 같은 그룹끼리 바뀌게 되므로 같이 움직인다고 볼 수 있다.
그러면 여기서 1번 비트와 해당하는 100번 비트가 둘다 같은 숫자이면 Reverse되어도 그대로이다. 그리고 1번 비트와 100번 비트가 서로 다른 숫자라면 Negation되어도 Reverse되는 것과 같은 효과가 난다.
이러한 점을 이용해서 같은 그룹내에 대칭인 bit와 아닌 bit가 둘 다 있다면, 이 2개의 비트를 확인해서 Negation이 되었는지 Reverse가 되었는지를 확인할 수 있다.
그리고 만약 한 그룹이 모두 대칭인 수로만 이루어져 있거나, 모두 비대칭인 수로만 이루어져 있다면 더욱 쉽다. 대칭인 수로만 이루어져 있으면 Neg만 확인하면 되고, 비대칭인 수로만 이루어져 있으면 Rev랑 Neg랑 동일하게 칠 수 있다.
이를 이용해서 그룹의 수를 모두 알아내고(100번의 쿼리로), 각각 그룹 별 Neg랑 Rev가 일어났는지를 체크를 한다. 각각 그룹당 2번 이하의 쿼리로 일어났는지를 확인할 수 있으므로 10번의 쿼리마다 5개의 그룹을 확인할 수 있다. 그리고 10번의 쿼리가 일어난 뒤는 Bit fliping이 어떻게 일어났는지 알기 위해서 기준이 되는 그룹을 하나 두고(이 그룹은 비대칭과 대칭이 둘다 있어야지 Rev와 Neg를 둘다 확인가능) 그녀석으로 체크를 한다.
그래서 10번의 쿼리마다 최소 4개의 그룹의 상태를 확인가능하다.
그러면 130번 쿼리 내에 모든 그룹의 상태를 확인할 수 있다.
디버깅 할때에는 query 함수를 디버깅용 서버 상태를 알려주는 녀석으로 만들어서 했다.
모두 대칭이거나 비대칭인 경우의 체크를 조금 잘못해서 3번째 set에서 틀리긴 했었는데 고쳐서 이제는 모두 정답이 나온다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define TOTAL_BIT_NUM 105
#define GROUP_NUM 12
int tc, n;
int bits[TOTAL_BIT_NUM];
int mirror[TOTAL_BIT_NUM];
int mirror_cnt[GROUP_NUM];
int neged[GROUP_NUM];
int reved[GROUP_NUM];
int g_neged, g_reved;
void solve10() {
for (int t = 1; t <= tc; t++) {
string ans = "";
for (int i = 1; i <= n; i++) {
cout << i << endl;
cout.flush();
string s;
cin >> s;
ans += s[0];
}
cout << ans << endl;
cout.flush();
string res;
cin >> res;
if (res[0] == 'N') exit(1);
}
}
pii get_canary(int gnum) {
int neg_canary, rev_canary;
neg_canary = rev_canary = -1;
for (int i = gnum * 5; i < gnum * 5 + 5; i++) {
if (mirror[i] && neg_canary == -1) {
neg_canary = i; //rev 되도 변하지 않음
}
if (!mirror[i] && rev_canary == -1) {
rev_canary = i; //rev 되면 변함
}
}
return make_pair(neg_canary + 1, rev_canary + 1);
}
//debug
/*
int samples[] = {0, 1, 0, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 1 };
int query(int pos) {
static int count = 0;
int ret = samples[pos - 1];
count++;
if (count == 10) {
cout << "---------------------------------------" << endl;
count = 0;
if (rand() % 2 == 0) {
cout << "Negation !!!" << endl;
for (int i = 0; i < 100; i++) {
samples[i] ^= 1;
}
}
if (rand() % 2 == 0) {
cout << "Reversed !!!" << endl;
for (int i = 0; i < 50; i++) {
swap(samples[i], samples[99 - i]);
}
}
cout << "---------------------------------------" << endl;
}
return ret;
}
*/
int query(int pos) {
cout << pos << endl;
cout.flush();
int ret;
cin >> ret;
return ret;
}
void solve_large() {
while (tc--) {
//입력받기
memset(bits, -1, sizeof(bits));
memset(mirror, 0, sizeof(mirror));
memset(mirror_cnt, 0, sizeof(mirror_cnt));
memset(neged, -1, sizeof(neged));
memset(reved, -1, sizeof(reved));
g_neged = g_reved = 0;
for (int i = 0; i < n / 10; i++) {
// [i*5+1, i*5+5]이랑 [n-5*i-4, n-5*i]
//10개씩 뭉텅이로 받되, 앞에서부터 5개, 뒤에서부터 5개가 하나의 셋트이다.
//앞에서부터 5개
for (int j = i * 5; j < i * 5 + 5; j++) {
bits[j] = query(j + 1);
}
//뒤에서부터 5개
for (int j = n - 5 * i - 5; j < n - 5 * i; j++) {
bits[j] = query(j + 1);
}
}
//base group를 찾는다.
//base는 palindrome한 쌍과 palindrome 아닌 것 값 하나를 알아내면 된다.
//팰린드롬은 complement 연산을 했는지를 확인하는 용도이다.
//palindrome아닌 것은 reverse연산을 했는지 확인하는 용도이다.
//base 그룹은 mirror_cnt가 1~4 사이의 값이다.
for (int i = 0; i < n / 2; i++) {
int j = n - i - 1;
if (bits[i] == bits[j]) {
mirror[i] = mirror[j] = 1;
mirror_cnt[i / 5]++; //해당 그룹에 palindrome 인 수 개수.
}
}
// mirror_cnt가 5인 그룹에는 rev 연산이 무의미함
// mirror_cnt가 0인 그룹은 rev 연산과 neg 연산이 같다.
int base_gnum = -1;
for (int i = 0; i < n / 10; i++) {
if (mirror_cnt[i] > 0 && mirror_cnt[i] < 5) {
base_gnum = i;
break;
}
}
if (base_gnum == -1) {
//모든 그룹이 palindrome이거나 그 반대인경우
//neg만 체크하면 된다.
for (int i = 0; i < n / 10; i++) {
int k = i * 5 + 1;
int res;
res = query(k);
if (bits[k - 1] != res) {
//real time negation
//앞에서부터 5개
for (int j = i * 5; j < i * 5 + 5; j++) {
bits[j] ^= 1;
}
//뒤에서부터 5개
for (int j = n - 5 * i - 5; j < n - 5 * i; j++) {
bits[j] ^= 1;
}
}
}
string s = "";
for (int i = 0; i < n; i++) {
if (bits[i]) {
s += "1";
}
else {
s += "0";
}
}
cout << s << endl;
cout.flush();
//get response
string res;
cin >> res;
if (res[0] == 'N') exit(1);
}
else {
//일반적인 섞여있는 경우
pii base_canary = get_canary(base_gnum); // {neg, reg}
int query_left = 8;
if (query(base_canary.first) != bits[base_canary.first - 1]) {
neged[base_gnum] = 1;
}
else {
neged[base_gnum] = 0;
}
if (query(base_canary.second) != (bits[base_canary.second - 1] ^ neged[base_gnum])) {
reved[base_gnum] = 1;
}
else {
reved[base_gnum] = 0;
}
(void)0;
for (int i = 0; i < n / 10; i++) {
if (i == base_gnum) continue; //base 그룹은 미리 구해놨으므로 안구해도 된다.
if (query_left < 2) {
if (query_left == 1) query(1);
query_left = 8;
if (query(base_canary.first) != (bits[base_canary.first - 1] ^ neged[base_gnum] ^ g_neged)) {
g_neged ^= 1;
}
if (query(base_canary.second) != (bits[base_canary.second - 1] ^ neged[base_gnum] ^ reved[base_gnum] ^ g_neged ^ g_reved)) {
g_reved ^= 1;
}
}
if (mirror_cnt[i] > 0 && mirror_cnt[i] < 5) {
pii canary = get_canary(i);
query_left -= 2;
if (query(canary.first) != (bits[canary.first - 1] ^ g_neged)) {
neged[i] = 1;
}
else {
neged[i] = 0;
}
if (query(canary.second) != (bits[canary.second - 1] ^ g_neged ^ g_reved ^ neged[i])) {
reved[i] = 1;
}
else {
reved[i] = 0;
}
}
else {
query_left--;
if (query(i * 5 + 1) != ((bits[i * 5] ^ g_neged) ^ (mirror_cnt[i] == 0 ? g_reved : 0))) {
neged[i] = 1;
}
else {
neged[i] = 0;
}
reved[i] = 0;
}
}
//apply answers
for (int i = 0; i < n / 10; i++) {
int cneged = (g_neged ^ neged[i]);
int creved = (g_reved ^ reved[i]);
if (cneged) {
for (int j = i * 5; j < i * 5 + 5; j++) {
bits[j] ^= 1;
}
//뒤에서부터 5개
for (int j = n - 5 * i - 5; j < n - 5 * i; j++) {
bits[j] ^= 1;
}
}
if (creved) {
for (int j = i * 5; j < i * 5 + 5; j++) {
int k = n - j - 1;
swap(bits[j], bits[k]);
}
}
}
string s = "";
for (int i = 0; i < n; i++) {
if (bits[i]) s += "1";
else s += "0";
}
cout << s << endl;
cout.flush();
string res;
cin >> res;
if (res[0] == 'N') exit(1);
}
}
return;
}
int main() {
cin >> tc >> n;
if (n == 10) {
solve10();
}
else {
solve_large();
}
}
5. Indicium(7pts, 25pts)
마지막 문제인데, Small tc만 풀이법을 알겠고, large는 모르겠다.
원하는 Trace에 해당하는 Latin square matrix를 찾거나, 불가능하다고 말해줘야하는 그런 문제이다.
Backtracking으로 풀 수 있고, 특정 K값을 트레이스로 갖는지 알아야 한다.
만약 K가 주어지면, 1~N의 범위의 수 N개의 합으로 K를 만들 수 있는 조합들을 구해본다.
그리고 그 조합들의 수로 대각선으로 나열한 뒤, 남은 칸에다가 수를 채워서 Latin square matrix를 만들 수 있는지만 확인하면 된다.
이때 만약 수 조합이 1 2 2 3 4 라는 조합으로 12라는게 되는지 확인해야 할 때, 순서는 중요치 않다는 것을 알 수 있는데, 이때 하나의 성질을 활용하면 된다.
즉 1 2 2 3 4로 Latin square 매트릭스를 만들 수 있으면 1 3 4 2 2 로도 만들 수 있는데, Latin square matrix는 행 단위로 순서를 바꾸거나 열 단위로 서로 순서를 바꾸어도 Latin square matrix이다. 왜 그런지는 조금만 생각해보면 알 수 있다.
따라서 조합별로 가능한 라틴 스퀘어 매트릭스가 있는지를 다 체크해보면 Small tc는 맞출 수 있다.
Large tc는 이분매칭을 쓴다는 것 같은데, 나중에 다시 공부해봐야 겠다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define endl '\n'
int n, k;
//n개의 숫자(1~n) 합으로 k를 만드는 경우의 수를 다 만들어야한다.
int val[6];
struct Chunk {
int v[5];
};
vector<Chunk> comb[26];
void dfs(int offset) {
if (offset <= n) {
for (int i = val[offset - 1]; i <= n; i++) {
val[offset] = i;
dfs(offset + 1);
}
}
else {
Chunk chunk;
int sum = 0;
for (int i = 1; i <= n; i++) {
sum += val[i];
chunk.v[i - 1] = val[i];
}
comb[sum].push_back(chunk);
}
}
int row[5], col[5];
int field[5][5];
bool backtrack(int i, int j) {
if (i >= n) {
//모두 성공한 경우
cout << "POSSIBLE\n";
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cout << field[i][j] << ' ';
}
cout << endl;
}
return true;
}
if (j >= n) {
//다음줄로 이동
return backtrack(i + 1, 0);
}
if (field[i][j] != -1) {
//이미 지정된 경우(diagonal)
return backtrack(i, j + 1);
}
for (int v = 1; v <= n; v++) {
if (((row[i] & (1 << v)) == 0 && (col[j] & (1 << v)) == 0)) {
//set
field[i][j] = v;
row[i] |= (1 << v);
col[j] |= (1 << v);
//search
if (backtrack(i, j + 1)) {
return true;
}
//unset
row[i] &= (~(1 << v));
col[j] &= (~(1 << v));
field[i][j] = -1;
}
}
return false;
}
void solve() {
cin >> n >> k;
for (int i = n; i <= n * n; i++) {
comb[i].clear();
}
//n에 대한 가능한 모든 숫자 조합들을 만들어냄
dfs(1);
for (int i = 0; i < comb[k].size(); i++) {
memset(row, 0, sizeof(row));
memset(col, 0, sizeof(col));
memset(field, -1, sizeof(field));
for (int j = 0; j < n; j++) {
int v = comb[k][i].v[j];
field[j][j] = v;
row[j] |= (1 << v);
col[j] |= (1 << v);
}
if (backtrack(0, 0)) return;
}
cout << "IMPOSSIBLE\n";
return;
}
int main() {
val[0] = 1;
int tc; cin >> tc;
for (int t = 1; t <= tc; t++) {
printf("Case #%d: ", t);
solve();
}
}
사실 지금 글을 쓰는 이 시점에는 Rust를 공식적으로 지원하는 IDE나 그런 녀석들은 잘 없는데, 그래도 제일 많이 쓰이는 조합이 Visual Studio Code + Rust plugin인 것 같다. 해당 조합은 VS코드에서 Syntax highlighting을 지원합니다.
그리고 RLS라는 Rust Language Server라는 녀석이 있는데 이 녀석은 백그라운드로 실행되면서 코드 에디터나 다른 툴에게 Rust에 대한 정보를 넘겨주는 그런 녀석입니다. syntax상 에러 같은거를 알려주고, 선언부로 이동하기 라던지 IDE에서 제공하는 기능들을 모듈화 된 프로그램이라고 보면 됩니다.
근데 아직 RLS도 Stable 버전이 나온 상태는 아니라서 다른 언어에 비해좀 느리거나 중간에 동작하지 않거나 하는 경우가 좀 있다고 합니다. 그래도 쓸만하다고 하네요.
제가 구축할 환경은 Windows 10 + Sublime Text3 + Rust plugin 이 되겠습니다.
Rustup 설치
Rustup은 rust 툴체인 인스톨러라고 합니다. Rustup을 쓰지 않더라도 러스트를 설치할 수 있지만, rustup을 이용하면 다른 컴포넌트들을 쉽게 설치할 수 있어서 추천한다고 합니다.
문제는 간단하다. N개의 집이 있고, 각각의 집의 가격은 Ai원이다. 그리고 총 B달러가 있을때 가장 많은 집을 사고 싶다고 한다. 몇개를 살 수 있는가?
그냥 Ai를 오름차순으로 소팅한 뒤 예산을 넘지 않는 만큼만 진행하면 된다. //(O(NlgN)//)로 풀리며, N이 //(10^5//)이므로 쉽게 풀린다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int A[100005];
void solve() {
int N, B;
cin >> N >> B;
for (int i = 0; i < N; i++) {
cin >> A[i];
}
sort(A, A + N);
int ans = 0;
for (int i = 0; i < N; i++) {
if (B >= A[i]) {
B -= A[i];
ans++;
}
else {
break;
}
}
printf("%d\n", ans);
}
int main() {
int tc; cin >> tc;
for (int t = 1; t <= tc; t++) {
printf("Case #%d: ", t);
solve();
}
}
2. Plates
접시를 골라서 그 값들을 최대로 해야하는데, 접시는 위에서부터 연속된 것들만 고를 수 있다. 접시를 고르는 총 개수도 정해져있다.
dp문제인데, 맨처음에 dp인 것 같다가 시간복잡도가 안될 것 같았다는 생각이 좀 들어서 약간 긴가민가 했었다. 근데 문제를 부분문제로 나눌 수 있고 독립되게 풀린다는 것이 보여서 dp가 맞는 듯 했다.
2차원 dp로 풀 수 있는데 각 항의 정의는 다음과 같다.
//(dp[i][j]//)는 i번째 줄까지 쭉 진행했을 때, j개의 접시를 골라서 낼 수 있는 최대 점수
이러면 //(dp[i][j]//)를 이용해서 다음 줄에서 k개의 접시를 구하는 경우//(dp[i+1][j+k]//)를 쉽게 구할 수 있다.
for-loop를 돌리는 식으로 구현해보았다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[55][33];
int dp[55][1505]; //dp[i][j]는 i번째 라인까지 j개의 plate를 골라서 얻을 수 있는 최대 점수.
void solve() {
int N, K, P;
cin >> N >> K >> P;
memset(dp, 0, sizeof(dp));
memset(a, 0, sizeof(a));
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= K; j++) {
cin >> a[i][j];
a[i][j] += a[i][j - 1];
}
}
for (int i = 1; i <= K; i++) {
dp[1][i] = a[1][i];
}
for (int i = 1; i <= N; i++) {
for (int j = 0; j <= i * K; j++) {
for (int k = 0; k <= K; k++) {
dp[i + 1][j + k] = max(dp[i + 1][j + k], dp[i][j] + a[i + 1][k]);
}
}
}
printf("%d\n", dp[N][P]);
return;
}
int main() {
int tc; cin >> tc;
for (int t = 1; t <= tc; t++) {
printf("Case #%d: ", t);
solve();
}
}
3. Workout
이거는 증가하는 수열에서 인접한 수열 사이의 차이를 일정 값 이하로 만들고 싶은 상황이다. 이 때 수열 사이 사이에 임의의 값을 갖는 녀석을 끼워넣을 수 있다. 이 때 인접한 수열 사이의 차이값의 최소값을 구하는 그런 문제이다.
최소값 구하는 문제, 최대값 구하는 문제 중 이러한 류의 문제들, 차이값의 최소 와 같은 좀 복잡한 값의 최소/최대문제는 보통 결정문제로 변경해서 푸는 파라메트릭 서치 문제이다.
인접한 값의 차이를 d 이하로 만들 수 있는가? 의 결정 문제로 바꾼 뒤 이녀석을 통해서 binary search를 돌리면 풀린다.
그리고 이 결정 문제는 보통 그리디나 선형 시간복잡도로 풀리게 된다.
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
int M[100005];
int N, K;
bool ok(int v) {
int k = K;
for (int i = 1; i < N; i++) {
int diff = M[i] - M[i - 1];
k -= (diff + v - 1) / v - 1;
}
return k >= 0;
}
int solve() {
cin >> N >> K;
for (int i = 0; i < N; i++) {
cin >> M[i];
}
int l = 1;
int r = 1e9;
while (l < r) {
int m = (l + r) / 2;
if (ok(m)) {
r = m;
}
else {
l = m + 1;
}
}
return r;
}
int main() {
int tc;
cin >> tc;
for (int t = 1; t <= tc; t++) {
cout << "Case #" << t << ": " << solve() << endl;
}
}
4. Bundling
문자열들을 같은 크기의 Group들로 균일하게 나눈 뒤, 그 그룹들의 Longest prefix의 길이만큼 점수를 얻는데 이 점수를 최대화하는 그런 문제이다. 그룹을 어떻게 나눌 것인가까지는 알 필요 없이 점수만을 계산할 수 있다고 한다. 맨처음 이 문제를 보고 문자열 그냥 소팅한 뒤 K개씩 그룹핑 하면 되지 않을까 했는데 조금 생각해보니 바로 반례가 나왔다..
K가 만약 3이라고 하면 문자열이 다음과 같이 나왔을때 그리디하게 하면 최적화되지 않은 그룹핑이 된다.
A A A B C C C D E E E F
이런 경우 하나씩만 있는 B, D, F는 어차피 점수를 낼 수 없으므로 자기내들끼리 묶여서 남에게 피해를 주지 않아야 하는데 greedy하게 묶으면 망한다.
솔루션을 보니, Trie를 구축한 뒤, Trie Node별로 나타난 횟수를 체크해놓고, 나타난 횟수를 A라고 할때 각 노드별 floor(A/K)를 더하면 된다고 한다.
A % K에 해당하는 K개가 되지 못한 그룹녀석들은 어차피 어디에 끼여도 점수를 낼 수 없으므로 버리게 된다.
조금 생각해보니 correct한 알고리즘인 것이 이해가 되었다.
Trie는 malloc으로 구현하는 것이 귀찮아서 배열을 두고 정적할당과 같은 테크닉으로 구현을 해 보았다.
그리고 dfs로 모든 노드를 순회하면서 점수를 계산했다.
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
#define MAXN 2000006
class Node {
public:
char c;
int num;
int next[28];
Node() {
clear();
}
void clear() {
memset(next, 0, sizeof(next));
num = 0;
c = 0;
}
};
Node nodes[MAXN];
int cnt;
int dfs(int v, int k) {
auto& cnode = nodes[v];
int ret = cnode.num / k;
for (char c = 'A'; c <= 'Z'; c++) {
if (cnode.next[c - 'A'])
ret += dfs(cnode.next[c - 'A'], k);
}
return ret;
}
int solve() {
int n, k;
cin >> n >> k;
//clear prev data
for (int i = 0; i <= cnt; i++) {
nodes[i].clear();
}
cnt = 0;
for (int i = 0; i < n; i++) {
string s;
cin >> s;
int ptr = 0;
for (char c : s) {
auto& next = nodes[ptr].next[c - 'A'];
if (!next) {
next = ++cnt;
nodes[next].c = c;
}
ptr = next;
nodes[ptr].num++;
}
}
return dfs(0, k);
}
int main() {
int tc;
cin >> tc;
for (int t = 1; t <= tc; t++) {
cout << "Case #" << t << ": " << solve() << endl;
}
}
Original Data: count=10&lat=37.351&user_id=1&long=-119.827&waffle=eggo
Original Signature: 6d5f807e23db210bc254a28be2d6759a0f5f5d99
여기에 공격자는 마지막에 파라메터를 추가하고자 한다.
Desired New Data: count=10&lat=37.351&user_id=1&long=-119.827&waffle=eggo&waffle=liege
그러면 공격이 이루어진 데이터는 다음과 같은 형태를 띄게 된다.
New Data: count=10&lat=37.351&user_id=1&long=-119.827&waffle=eggo\x80\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x02\x28&waffle=liege
New Signature: 0e41270260895979317fff3898ab85668953aaa2
사이에 Null byte들이 많이 들어가게 되는데, 저 Null byte로 해시함수를 계산할때 내부 구조를 적절히 바꾸어서 하는 방식이라고 한다.
방어법
이 취약점은 Merkle–Damgård construction를 갖는 해쉬함수를 MAC에 오용해서 나타나는 취약점이라고 한다. 이 구조의 해시함수는 충돌이 잘 일어나지 않는 것그러므로 해당 구조에 해당하지 않는 해쉬함수(SHA-3)를 사용하면 된다.
공격용 툴들
이 Hash length extension attack을 직접 구현해서 써먹기에는 어려우므로 공개된 라이브러리들을 쓰면 좋다. HashPump는 커맨드라인에서 실행할 수 있는 형태의 툴이며, hlextend는 파이썬에서 사용할 수 있는 라이브러리 형태로 제공된다.
#include <stdio.h>
#include <sys/time.h>
#include <sys/types.h>
#include <unistd.h>
#include <sys/time.h>
#include <sys/resource.h>
#include <stdlib.h>
#include <fcntl.h>
#include <stdio.h>
#include <sys/socket.h>
#include <stdlib.h>
#include <netinet/in.h>
#include <string.h>
#include <vector>
#include <arpa/inet.h>
#include <algorithm>
/* globals */
fd_set *rfds;
int lastfd;
std::vector<int> listeners;
std::vector<int> admins;
int vhasele(std::vector<int> v, int ele) {
if(std::find(v.begin(), v.end(), ele) != v.end()) {
return 1; // has it
} else {
return 0; // doesn't have it
}
}
void vremove(std::vector<int> v, int ele) {
v.erase(std::remove(v.begin(), v.end(), ele), v.end());
}
void setfdlimit() {
struct rlimit fdlimit;
long limit;
limit = 65536;
fdlimit.rlim_cur = limit;
fdlimit.rlim_max = limit;
setrlimit(RLIMIT_NOFILE, &fdlimit);
FD_ZERO(rfds);
}
void nobuf() {
setvbuf(stdout, NULL, _IONBF, 0);
setvbuf(stderr, NULL, _IONBF, 0);
setvbuf(stdin, NULL, _IONBF, 0);
}
void intro() {
puts("simple hybrid infrastructure torrent");
puts("enable simple distribution of files among your fleet of machines");
puts("used by it department the world over");
}
void printmenu() {
puts("《SHITorrent 》management console");
puts("[a]dd pc to manage");
puts("[r]emove pc from fleet");
puts("[w]ork");
puts("[q]uit");
puts("[g]et flag");
}
int add_node() {
char hostname[100] = {0};
char portstr[100] = {0};
int port = 0;
puts("enter host");
read(0, hostname, 99);
if(hostname[strlen(hostname) - 1] == '\n') {
hostname[strlen(hostname) - 1] = '\x00';
}
puts("enter port");
read(0, portstr, 99);
port = atoi(portstr);
struct sockaddr_in address;
int sock = 0, valread;
struct sockaddr_in serv_addr;
char *hello = "SHITorrent HELO\n";
char buffer[1024] = {0};
if ((sock = socket(AF_INET, SOCK_STREAM, 0)) < 0) {
printf("\n Socket creation error \n");
return -1;
}
memset(&serv_addr, '0', sizeof(serv_addr));
serv_addr.sin_family = AF_INET;
serv_addr.sin_port = htons(port);
// Convert IPv4 and IPv6 addresses from text to binary form
if(inet_pton(AF_INET, hostname, &serv_addr.sin_addr)<=0) {
printf("\nInvalid address/ Address not supported \n");
return -1;
}
if (connect(sock, (struct sockaddr *)&serv_addr, sizeof(serv_addr)) < 0) {
printf("\nConnection Failed \n");
return -1;
}
send(sock , hello , strlen(hello) , 0 );
valread = read( sock , buffer, 1024);
if (strncmp("TORADMIN", buffer, strlen("TORADMIN"))) {
listeners.push_back(sock);
printf("added listener node %d\n", sock);
} else {
admins.push_back(sock);
FD_SET(sock, rfds);
printf("added sending node %d\n", sock);
}
if (sock > lastfd) {
lastfd = sock;
}
return 0;
}
void remove_node() {
char buf[256];
read(0, buf, 255);
int bufno = atoi(buf);
if (bufno > 2 && bufno <= lastfd) {
close(bufno);
}
if (vhasele(listeners, bufno)) {
vremove(listeners, bufno);
}
if (vhasele(admins, bufno)) {
vremove(admins, bufno);
if (FD_ISSET(bufno, rfds)) {
FD_CLR(bufno, rfds);
}
}
}
void dispatch_it(int fd) {
printf("dispatching from %d\n", fd);
char *buf = (char *)calloc(1, 4096);
int sz = read(fd, buf, 4096);
printf("getting %s\n", buf);
for (int i = 0; i < listeners.size(); i++) {
write(listeners[i], buf, sz);
}
free(buf);
}
void workit() {
struct timeval tv;
tv.tv_sec = 5;
tv.tv_usec = 0;
int retval = select(FD_SETSIZE, rfds, NULL, NULL, &tv);
// Don't rely on the value of tv now!
if (retval) {
puts("DEBUG: ready to send out the data");
// FD_ISSET(0, &rfds) will be true.
for (int i = 3; i < lastfd; i++) {
if (FD_ISSET(i, rfds)) {
dispatch_it(i);
return;
}
}
} else {
printf("no data within 5 seconds quitting");
exit(0);
}
}
void notmain() {
for(;;) {
char buf[2];
printmenu();
read(0, buf, 2);
switch(buf[0]) {
case 'a':
{
add_node();
}
break;
case 'r':
{
remove_node();
}
break;
case 'w':
{
workit();
}
break;
case 'q':
{
return;
}
break;
case 'g':
{
puts("lol, just kidding");
}
break;
default:
{
puts("not supported");
}
break;
}
}
}
int main(int argc, char **argv) {
fd_set fds;
rfds = &fds;
lastfd = 2;
setfdlimit();
nobuf();
intro();
notmain();
return 0;
}
C++로 작성된 서버코드이다. 클라이언트 입장에서는 ip와 port를 넘겨준 뒤, 서버에서 접속을 시도하면 적절한 값을 리턴해서 admin모드이거나 일반 user 모드로 등록이 가능하다.
미티게이션
checksec으로 확인해보면 아래와 같이 나타난다.
NX가 활성화 되어 있고, 스택 까나리가 적용되어 있다.
취약점
소스코드를 보면 잘 모르는 자료구조와, 매크로 함수가 보이는데 fd_set, FD_SET, FD_ZERO, FD_ISSET, FD_CLR 이런 녀석들이다.
여기서 FD는 File descriptor의 약자라고 한다. 이 함수들과 자료구조는 여러개의 소캣들을 열어서 connection을 맺어 놓은 상태에서 관리하기 위해 존재한다고 한다.
소캣 fd를 bitmap 자료구조로 관리하는 거라고 한다. 만약 3번 소캣을 사용중이면 FD_SET(fd_set, 3) 이런식으로 해서 3번 비트를 1로 만들고, FD_CLR(fd_set, 3)이런 식으로해서 3번 비트를 0으로 되돌리는 방식으로 소캣들의 사용 유무를 관리할 수 있다고 한다.
그래서 총 1024개의 소캣들을 관리할 수 있는데, 즉 fd_set의 자료구조는 1024bit의 크기를 갖는다.
Anfd_setis a fixed size buffer. ExecutingFD_CLR() orFD_SET() with a value offdthat is negative or is equal to or larger thanFD_SETSIZEwill result in undefined behavior. Moreover, POSIX requiresfdto be a valid file descriptor.
fd_set는 고정 크기의 버퍼이므로, FD_SETSIZE를 넘는 값으로 FD_SET, FD_CLR 등을 호출하는 것은 Undefined behaivro이다. 라고 써있다. 바로 여기서 취약점이 나타난다.
FD_SETSIZE는 일반적으로 1024이며, 주어진 바이너리에서도 1024이다.
fd_set 자료구조를 보면 main context의 지역변수로 들어가게 되고, FD_CLR, FD_SET의 함수는 소캣 연결의 제한이 별도로 있지는 않다. (2^16이 제한인 듯 하다)
이를 이용해서 buffer overflow가 나타나게 된다.
mitigation들을 체크해보면 nx도 걸려있으므로, ROP chain을 구성해서 exploit을 하면 될 듯 하다.
익스플로잇
일단 익스플로잇을 하기 위해서는 서버단에서 접속이 가능한 ip와 port로 적절한 서비스를 열고 있어야 간편하다.
If you click the 'the source' link, you can get back-end source code.
const express = require("express");
const rateLimit = require("express-rate-limit");
const app = express();
const { Pool, Client } = require("pg");
const port = process.env.PORT || 9090;
const path = require("path");
const client = new Client({
user: process.env.DBUSER,
host: process.env.DBHOST,
database: process.env.DBNAME,
password: process.env.DBPASS,
port: process.env.DBPORT
});
async function query(q) {
const ret = await client.query(`SELECT name FROM Criminals WHERE name ILIKE '${q}%';`);
return ret;
}
app.set("view engine", "ejs");
app.use(express.static("public"));
app.get("/src", (req, res) => {
res.sendFile(path.join(__dirname, "index.js"));
});
app.get("/", async (req, res) => {
if (req.query.q) {
try {
let q = req.query.q;
// no more table dropping for you
let censored = false;
for (let i = 0; i < q.length; i ++) {
if (censored || "'-\".".split``.some(v => v == q[i])) {
censored = true;
q = q.slice(0, i) + "*" + q.slice(i + 1, q.length);
}
}
q = q.substring(0, 80);
const result = await query(q);
res.render("home", {results: result.rows, err: ""});
} catch (err) {
console.log(err);
res.status(500);
res.render("home", {results: [], err: "aight wtf stop breaking things"});
}
} else {
res.render("home", {results: [], err: ""});
}
});
app.listen(port, function() {
client.connect();
console.log("App listening on port " + port);
});
Code is written in javascript, so the server platform is nodejs.
There is simple sql execution function, it filters some special chars.
It filters single-quotor, double-quotor, dash and point.
If one of bad-char appears, the all remainders will be substituted to '*' char.
I thought hard how can I bypass the filter, a solution is javascript type confusion.
The server source code assumes that 'req.query.q' data type is string, if you send url querystring like "q[]=value&q[]=another", on the server side the value is ["value", "another"] which is javascript array type.
Then q[i] is no longer single character but string, so we can bypass the filtering.
The expression ("'or 1=1-- " == "'") is evaluated as false.
Moreover, javascript array object also have method "slice" like string. The function slightly differ.
If you try to + operation between javascript array and string, the result is string. The array is treated like string.
Then after the expression `slice(0,i) + "*" + slice(i+1, q.length)`, q is now string, we can do the q.substring method below without exception.
I coded query string exploit payload builder in javascript.
function go(payload) {
var ret = '?q[]=' + encodeURIComponent(payload);
for (var i =1; i < payload.length; i++) {
ret += `&q[]`;
}
ret += `&q[]='`
return ret;
}
For the test, I wrote a query to get the current database name in pg-sql.
It works well!
I tried to get the column name with information_schema table, but q.substring(0, 80) limit our query length to 80, I did another method.
With some functions in pg-sql, we can get the data in 'Criminals' table in json serialized format.
Gotcha!, We've got the flag
actf{qu3r7_s7r1ng5_4r3_0u7_70_g37_y0u}
한글 풀이
UI는 아래와 같이 생겼다.
우측에 the source라는 것을 클릭하면 백엔드 소스도 제공을 해준다.
const express = require("express");
const rateLimit = require("express-rate-limit");
const app = express();
const { Pool, Client } = require("pg");
const port = process.env.PORT || 9090;
const path = require("path");
const client = new Client({
user: process.env.DBUSER,
host: process.env.DBHOST,
database: process.env.DBNAME,
password: process.env.DBPASS,
port: process.env.DBPORT
});
async function query(q) {
const ret = await client.query(`SELECT name FROM Criminals WHERE name ILIKE '${q}%';`);
return ret;
}
app.set("view engine", "ejs");
app.use(express.static("public"));
app.get("/src", (req, res) => {
res.sendFile(path.join(__dirname, "index.js"));
});
app.get("/", async (req, res) => {
if (req.query.q) {
try {
let q = req.query.q;
// no more table dropping for you
let censored = false;
for (let i = 0; i < q.length; i ++) {
if (censored || "'-\".".split``.some(v => v == q[i])) {
censored = true;
q = q.slice(0, i) + "*" + q.slice(i + 1, q.length);
}
}
q = q.substring(0, 80);
const result = await query(q);
res.render("home", {results: result.rows, err: ""});
} catch (err) {
console.log(err);
res.status(500);
res.render("home", {results: [], err: "aight wtf stop breaking things"});
}
} else {
res.render("home", {results: [], err: ""});
}
});
app.listen(port, function() {
client.connect();
console.log("App listening on port " + port);
});
코드를 보니 nodejs로 백엔드를 작성했다.
간단하게 sql 쿼리를 실행시킬 수 있도록 되어있고, 일부 특수문자들을 필터링하는 것을 알 수 있다.
일단 싱글쿼터를 필터링을 해서, 해당 bad character가 나타나면 나머지 모든 글자들을 *로 바꿔버리는 방식이다.
이 sql 쿼리 필터링을 어떻게 우회할까 고민을 많이 했는데, 정답은 javascript type confusion이었다.
서버코드는 req.query.q가 string일 것을 가정하고 코드가 짜져있는데, url 쿼리스트링에 q[]=value&q[]=another 와 같은 방식으로 전송하면 서버에는 ["value", "another"]과 같은 javascript array형태로 전송이 되게 된다.
그러면 some(v => v == q[i])라는 필터링에서도 ["'or 1=1-- ", "garbage"] 이런 값이 전송이 되는 경우 filtering이 제대로 되지 않게 된다. "'or 1=1-- " == "'" 는 당연 false가 나오기 때문.
게다가 Javascript array는 slice라는 함수를 동일하게 가지고 있다.
그리고 문자열과 배열간 + 연산을 하게 되면, 배열을 문자열처럼 바뀌어서 concat연산이 되고 그 결과는 문자열이 되어서 아래의 q.substring 함수도 정상적으로 실행을 하게 된다.
이러한 조건에 맞는 query string payload를 만들어주는 js 코드를 작성해서 요청을 보내보았다.
function go(payload) {
var ret = '?q[]=' + encodeURIComponent(payload);
for (var i =1; i < payload.length; i++) {
ret += `&q[]`;
}
ret += `&q[]='`
return ret;
}
일단 테스트 겸 database name을 알아내는 쿼리를 작성해보았다.
결과가 잘 나온다.
information_schema로 column 명을 알아내려고 했는데, q.substring(0, 80)의 쿼리 길이 제한때문에 잘 안되서 다른 방법을 사용해보기로 했다.
이제 Criminals 테이블의 값을 json형태로 serialize해서 다 빼오는 쿼리를 작성해서 날려보자.
