tony9402
Qualification Round 2020 본문
구글 코드잼을 해보았다! (풀이 공개는 대회 끝나고 했습니다.)
A ~ E 총 5문제고 30점 이상이면 통과할 수 있다.
30점은 A,B를 다 맞고 C 7점을 긁으면 할 수 있다.
E도 풀어보려고 했지만 히든 테케 맞추기 힘들꺼 같기도 하고 그렇다고 긁는것도 귀찮아서 안했다.
A. Vestigium
행렬에서 대각선(왼쪽 위부터 오른쪽 아래)의 합을 구하고 행, 열을 보고 한 줄에 중복되는 수가 있으면 개수를 세면 된다.
#include<bits/stdc++.h>
#define mp make_pair
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef pair<int, int> pii;
int Map[111][111];
bool visit[111][111], check[111];
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int t; cin >> t;
for(int TestCase = 1; TestCase <= t; TestCase++){
int n;cin >> n;
memset(visit, false, sizeof(visit));
int r=0, c=0,ans = 0;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cin >> Map[i][j];
if(i == j)ans += Map[i][j];
}
}
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(check[Map[i][j]]){
r++;
break;
}
check[Map[i][j]] = true;
}
memset(check, false, sizeof(check));
}
for(int j=0;j<n;j++){
for(int i=0;i<n;i++){
if(check[Map[i][j]]){
c++;
break;
}
check[Map[i][j]] = true;
}
memset(check, false, sizeof(check));
}
cout << "Case #" << TestCase << ": " << ans << ' ' << r << ' ' << c << '\n';
}
}
B. Nesting Depth
111000 => (111)000
23200 => ((2(3)2))00
이런식으로 숫자에 맞춰서 올바른 괄호 안에 있도록 괄호를 추가해주면 된다.
#include<bits/stdc++.h>
#define mp make_pair
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef pair<int, int> pii;
const int dy[] = {-1,1,0,0};
const int dx[] = {0,0,-1,1};
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int t; cin >> t;
for(int TestCase = 1; TestCase <= t; TestCase++){
string str, ans; cin >> str;
int top = 0;
for(int i=0;i<str.size();i++){
int cnt = str[i] - 48;
while(top < cnt){ans.push_back('(');top++;}
while(top > cnt){ans.push_back(')');top--;}
ans.push_back(str[i]);
}
while(top > 0){ans.push_back(')');top--;}
cout << "Case #" << TestCase << ": " << ans << '\n';
}
}
C. Parenting Partnering Returns
문제를 안읽고 예제보고 푼거라 풀이만 말하겠다.
난 예제를 보는 순간 회의실 배정 + 두 사람이 일을 잘 나누어 다 할 수 있나를 보는 문제인거 같았다.
이런 문제는 스위핑으로 풀면 쉽게 풀린다.
#include<bits/stdc++.h>
#define mp make_pair
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef pair<int, int> pii;
struct Node{
int v, t, idx;
Node() {}
Node(int v, int t, int idx):v(v),t(t),idx(idx) { }
bool operator<(const Node &o) const{
if(v != o.v)return v < o.v;
return t < o.t;
}
};
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int t; cin >> t;
for(int TestCase = 1; TestCase <= t; TestCase++){
int n; cin >> n;
vector<Node> vc;
for(int i=0;i<n;i++){
int a, b;cin >> a >> b;
vc.emplace_back(a, 1, i);
vc.emplace_back(b, -1, i);
}
sort(all(vc));
int J = -1, C = -1;
string ans; ans.resize(n);
for(auto i: vc){
if(i.t == -1){
if(J == i.idx){
J = -1;
}
else{
C = -1;
}
}
else{
if(J == -1){
ans[i.idx] = 'C';
J = i.idx;
}
else if(C == -1){
ans[i.idx] = 'J';
C = i.idx;
}
else{
ans = "IMPOSSIBLE";
break;
}
}
}
cout << "Case #" << TestCase << ": " << ans << '\n';
}
}
D. ESAb ATAd
처음 해보는 Interactive 문제이다! 이런 문제를 처음 접해봐서 처음에 바로 생각한 풀이가 맞는지 한참 고민했는데 그 풀이가 맞았다...
문제 요약부터 해보자.
- 길이가 B이고 0과 1로 이루어진 비트(B)가 있다. 이는 뭔지 알 수 없다.
- 알고 싶은 위치를 쿼리를 날리면 0인지 1인지 알려준다.
- 쿼리를 10n + 1 번째 쿼리를 날리면 B가 50% 확률로 reverse가 될 수 있고 50% 확률로 not 연산이 일어난다.
- 위 두가지가 독립사건으로 둘다 안일어날 수 있고 한 가지만 일어날 수 있고 둘다 일어날 수 있다.
- 최대 150개의 쿼리를 날려서 쿼리를 그만 날린 시점에서의 현재 B를 맞추면 되는 문제이다.
B의 최대 길이가 100이다. 10번마다 B가 변경되므로 10번의 쿼리를 1 set으로 묶어서 생각해보자.
10번마다 B가 변경 되므로 쿼리를 날릴때 B가 변경 됬는지 안됬는지에 대한 정보 검색과 새로운 B의 정보를 알아야한다.
변경된 정보 검색 횟수를 X, 새로운 정보 검색 횟수를 Y로 했을 때 X + Y = 10이 된다.
최대 15set까지 있으므로 15Y >= B(=100) 를 만족하는 Y번의 횟수를 나열해보자.
가능한 Y는 7, 8, 9가 된다. X와 쌍을 이루어 적어놓자. (X, Y) => (1, 9), (2, 8), (3, 7)
위 세개 중에서 가능한 것은 (2, 8)이다. (reverse가 일어나는지 판단하려면 대칭되는 두 비트를 알아야 하므로 짝수번만 가능하다.)
이제 B가 변경 된 점을 어떻게 판단할지 생각을 해보자. B에서 하나의 index를 잡고 그거에 대칭 되는 곳을 잡자.
(101001 이 있다면 1번째 1을 잡으면 맨 뒤 1를 같이 잡는다)
| index | B - index + 1 | reverse | not | all(rev + not) | |
| 1 | 0 | 0 | 0 0 | 1 1 | 1 1 |
| 2 | 0 | 1 | 1 0 | 1 0 | 0 1 |
| 3 | 1 | 0 | 0 1 | 0 1 | 1 0 |
| 4 | 1 | 1 | 1 1 | 0 0 | 0 0 |
원래 비트가 변경 됬을 경우 T, 아닐 경우를 F로 하고 다시 정리해보면 아래와 같다.
| index | B - index + 1 | reverse | not | all(rev + not) | |
| 1 | 0 | 0 | F F | T T | T T |
| 2 | 0 | 1 | T T | T T | F F |
| 3 | 1 | 0 | T T | T T | F F |
| 4 | 1 | 1 | F F | T T | T T |
이 표를 잘 보면 경우의 수를 조금 더 줄일 수 있다.
바로 index의 비트와 B - index + 1의 비트가 동일 한 경우와 다른 경우로 나눌 수 있다.
| 두 비트의 관계 | reverse | not | all(rev + not) | |
| 1 | 같은 경우 | F F | T T | T T |
| 2 | 다른 경우 | T T | T T | F F |
이렇게 보면 두 비트가 같은 경우 하나와 다른 경우 하나를 가지고 reverse, not, 또는 all(reverse + not)이 발생했는지를 항상 판단할 수 있다. 따라서 대칭되는 두 비트가 같은 경우와 다른 경우를 찾고 그 곳에서 변경 여부를 확인할 때 쿼리를 날려주면 된다. (Y를 1 set당 2회 사용가능)
이제 코딩을 하면 되는데 맨 처음 1 set 돌땐 아는 정보가 없으므로 10회를 다 새로운 정보를 물어보는 쿼리로 쓰면 되고 그 다음부터는 Y = 2번, X = 8번 사용하면서 판단하게 만들면 된다.
#include<bits/stdc++.h>
#define mp make_pair
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef pair<char, char> pcc;
int B;
void reverse(string &bits){
reverse(all(bits));
}
void complement(string &bits){
for(auto &i: bits)
i = 97 - i;
}
pcc query(int idx){
char _first, _second;
cout << idx << endl; cin >> _first;
cout << B - idx + 1 << endl; cin >> _second;
return mp(_first, _second);
}
void check_update(string &ret, int &c1, int &c2){
if(c1 < 0)cout << 1 << endl;
else cout << c1 << endl;
char a1, a2; cin >> a1;
if(c2 < 0)cout << 1 << endl;
else cout << c2 << endl;
cin >> a2;
bool ch1 = (a1 == ret[c1-1]);
bool ch2 = (a2 == ret[c2-1]);
if(ch1 && !ch2){
reverse(ret);
}
if(!ch1 && !ch2){
complement(ret);
}
if(!ch1 && ch2){
reverse(ret);
complement(ret);
}
}
int main(){
int t; cin >> t; cin >> B;
for(int TestCase = 1; TestCase <= t; TestCase++){
string target; target.resize(B);
int idx = 1;
int check_idx1 = -1, check_idx2 = -1;
for(int QQ=0;QQ<5;QQ++){
pcc q_ans = query(idx);
target[idx - 1] = q_ans.first;
target[B - idx] = q_ans.second;
if(check_idx1 == -1)
if(q_ans.first == q_ans.second)
check_idx1 = idx;
if(check_idx2 == -1)
if(q_ans.first != q_ans.second)
check_idx2 = idx;
idx++;
}
if(idx > B)idx = 1;
for(int Q=0;Q<14;Q++){
check_update(target, check_idx1, check_idx2);
for(int QQ=0;QQ<4;QQ++){
pcc q_ans = query(idx);
target[idx - 1] = q_ans.first;
target[B - idx] = q_ans.second;
if(check_idx1 == -1)
if(q_ans.first == q_ans.second)
check_idx1 = idx;
if(check_idx2 == -1)
if(q_ans.first != q_ans.second)
check_idx2 = idx;
idx++;
if(idx > B)idx = 1;
}
}
cout << target << endl;
char temp; cin >> temp;
}
return 0;
}