Codeforces Round #553 (Div. 2) B. Dima and a Bad XOR
rating : 1600
tags : bitmasks, brute force, constructive algorithms, dp
문제 요약
n행 m열인 행렬 a가 주어집니다. (1<=n,m,<=500, 0≤a[i][j]≤1023 )
a의 모든 행에서 숫자 1개씩을 뽑아서 xor 연산을 합니다. xor 값이 0이 아니게 되는 각 행의 열들을 찾는 것이 문제입니다. 없으면 없다고 출력합니다.
접근
a의 각 원소가 음수가 아닌데 a[1][c1]⊕a[2][c2]⊕…⊕a[n][cn]>0을 만족한다는 건 0만 아니면 된다는 것을 파악했습니다.
이는 최종 xor값에서 각 비트의 parity가 모두 짝수만 아니면 된다는 의미입니다.
하지만 이를 구현하기는 어려워보였습니다. 그래서 다른 방법을 생각합니다.
dp 또는 애드혹스러운 풀이 둘 중에 하나라는 느낌이 들었습니다.
애드혹스러운 풀이는 떠오르지 않아서 dp로 먼저 설계했습니다.
행렬의 원소값이 0~1023이라서 "[행][값] = 존재? "로 dp설계를 하면
0이 아닌 xor값의 존재 여부는 쉽게 얻을 수 있는데, 값과 인덱스의 헷갈림이 저의 한계를 초과해서 그러한 원소들을 추적하는 것을 해결하지 못했습니다.
어려움
bitmask
문제에 bitmask가 있어서 익숙하지 않아서 어려워 보였습니다.
하지만 이 문제는 bitmask를 가장한 브루트포스,애드혹 또는 dp문제였습니다. 수를 비트로 표현해서 접근할 필요는 없었습니다.
구현 헷갈림, dp 설계
dp 설계를 하고 구현을 했는데, 문제를 다시 보니 구하는 값은 각 행의 원소의 값이 아니라 열의 인덱스였습니다. 값의 추적을 할 수 있게 코드를 짰어서 망했다는 생각이 들었습니다.
인덱스 <-> 값을 헷갈리게 만드는 트릭은 자주 나오는데..
해결
dp 풀이
"dp[row][현재까지 xor값] = 존재여부" 가 아니라 컬럼을 기록하도록 아래와 같이 설계하면 해결됩니다.
정의 :dp[row][값] = if exist column else -1
dp 테이블 채우는 방식은 아래처럼 합니다.
dp[row][이전 행에 존재할 수 있는 xor값⊕현재 행에 존재하는 행렬값] = 컬럼
이렇게 dp테이블에 xor값에 해당하는 컬럼이 존재하면 역추적해서 답을 구할 수 있습니다.
int a[510][510];
int dp[510][1050]; //[row][xored_num] = col or none(-1)
int main() {
ios_base::sync_with_stdio(false); cin.tie(nullptr);
int n,m; cin>>n>>m;
for(int i=0;i<n;i++) for(int j=0;j<m;j++) {
cin>>a[i][j];
}
memset(dp,-1,sizeof(dp));
dp[0][0]=0;
for(int i=1;i<=n;i++){
for(int j=0;j<m;j++){
for(int num=0;num<1050;num++){
if(dp[i-1][num]==-1) continue;
int here=a[i-1][j];
dp[i][num^here]=j;
}
}
}
int num=-1;
for(int i=1;i<=1024;i++){
if(dp[n][i]>=0){
num=i;
break;
}
}
if(num!=-1){
vector<int> trace;
// cout<<num<<"\n";
for(int i=n;i>=1;i--){
trace.push_back(dp[i][num]+1);
num^=a[i-1][dp[i][num]];
}
reverse(all(trace));
cout<<"TAK\n";
for(int x:trace) cout<<x<<" "; cout<<"\n";
}else cout<<"NIE\n";
return 0;
}constructive, adhoc적인 풀이
각 행의 첫번째 수들로만 xor값을 구해봅니다.
- 이 값이 0이 아니면 이것이 답입니다.
- 이 값이 0이면 서로 다른 원소의 갯수가 2개인 행을 찾아서 첫번째가 아닌 다른 값으로 xor하면 0이 아닌 xor값이 됩니다.
단, 구현할 때 set을 사용한다면 정렬되는 속성에 주의해야 하고 인덱스를 구하는 것을 고려해서 설계해야 합니다.
잘못 구현할 시에 걸릴 수 있는 코너 케이스입니다.
[implementation corner case]
:caused by just counting different kind in each rows..
3 2
0 1
1 0
0 0
int main() {
ios_base::sync_with_stdio(false); cin.tie(nullptr);
int n,m; cin>>n>>m;
//vector<vector<int> > a(n);
set<pair<int,int> > a[n];
set<int> b[n];
for(int i=0;i<n;i++){
set<pair<int,int> > t;
set<int> t2;
for(int i=0;i<m ;i++) {
int num; cin>>num;
t.insert({num,i+1});
t2.insert(num);
}
a[i]=t;
b[i]=t2;
}
int totxor=0;
for(int i=0;i<n;i++){
totxor^=(*a[i].begin()).first;
// cout<<totxor<<'\n';
// cout<<(*a[i].begin()).second<<" ";
}//cout<<'\n';
if(totxor!=0){
cout<<"TAK\n";
for(int i=0;i<n;i++) cout<<(*a[i].begin()).second<<" "; cout<<'\n';
}else{
bool found=false;
for(int i=0;i<n;i++){
if(b[i].size()>=2){
cout<<"TAK\n";
for(int j=0;j<i;j++) cout<<(*a[j].begin()).second<<" ";
// cout<<(*(--a[i].end())).second<<" ";
totxor^=((*a[i].begin()).first);
for(auto x:a[i]){
if((totxor^x.first)!=0) {
// cout<<"\nhere: "<<totxor<<" "<<x.first<<" "<<(totxor^x.first)<<"\n";
cout<<x.second<<" ";
break;
}
}
for(int j=i+1;j<n;j++) cout<<(*a[j].begin()).second<<" "; cout<<'\n';
found=true;
break;
}
}
if(not found) cout<<"NIE\n";
}
return 0;
}
피드백
-
설계 측면
편법이긴 하지만 div2 b번이라는 건 간단한 풀이가 존재한다는 말과 동치입니다. 제한이 널널한 경우가 많기 때문입니다. 이 문제도 애드혹스러운 간단한 풀이가 존재했습니다. xor의 특성을 생각해봤으면 쉽게 떠올릴 법도 했지만 저는 유도해내지 못했습니다. -
구현 측면
에디토리얼을 보고 애드혹 풀이로 구현했는데 37번 테스트 케이스에서 틀렸습니다. 참가한 대회였다면 풀이를 떠올렸어도 프리테스트를 통과해서 기뻐했다가 시스텟에서 걸려서 뼈아팠을 것입니다. 구현을 할 때, 비약이 있으면 불안한 느낌이 드는데 이번에도 제출할 때 불안한 감이 있었습니다. set의 정렬되는 속성을 잠시 망각해서 구현에서 실수가 발생했었습니다.앞서 언급했던 테스트 케이스
3 2
0 1
1 0
0 0그리고 구하는 값을 명확히 했어야 했는데, 구현부터 빠르게 하다가 설계가 꼬여서 수정을 하기도 했습니다.
