올해 킥스타트 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();
}
}
