BOJ 33806 Sheriruth
sorohue가 PS하는 블로그
문제 링크입니다.
방어자로서
$m$이 클수록 방어자에게 유리한 게임이 되므로, 방어가 가능한 $m$의 최솟값이 존재합니다. 우선 이를 구해봅시다.
항상 방어가 가능하려면, 내가 어떤 원소의 어떤 위치에 $0$을 부여했을 때 다른 두 원소 중 해당 위치에 $2$가 부여된 것이 반드시 존재해야 합니다. 이때 나머지 한 원소는 공격자의 조건에 따라 그 위치에 $1$이 존재해야 하므로, 결국 우리가 $0$을 넣기로 정한 원소와 함께 선택할 수 있는 모든 원소의 해당 위치에는 $1$ 아니면 $2$가 부여되어야만 합니다.
공격자가 원소를 정할 때 걸리는 제약 조건은 오로지 원소의 $1$의 위치뿐입니다. 그러니 우리는 $1$의 위치를 기반으로 각 원소에 $0$을 넣을 위치를 정해줘야 합니다. 모든 위치에 $1$이 부여된 원소는 공격자의 조건 상 고를 수 없으므로 무시하면, 모든 원소에는 적어도 하나의 $1$과 적어도 하나의 $0$이 있습니다. 이를 활용해 전략을 구상해 보겠습니다.
각 위치마다 자기 자신을 제외한 어떤 위치를 일대일대응시키는 화살표들이 있다고 생각합시다. 예를 들어 그냥 다음 위치로 잇는 화살표를 생각할 수 있습니다. (마지막 위치는 첫 위치로 향하는 화살표를 그려줍시다.) 이제, 화살표의 출발점에 $1$이 있고 도착점에는 $0$이 있는 위치 중 아무거나 하나를 골라 $0$으로 놔두고, 나머지 $0$들은 모두 $2$로 바꿔줍시다. 그러면 어떤 원소를 골랐을 때, 그 원소에서 $0$의 위치를 결정한 $1$이 있을 겁니다. 이때 공격자가 이 원소와 함께 고를 수 있는 다른 모든 원소들은 그 $1$과 같은 위치에 $1$을 가질 수 없기 때문에, 이 원소에서 $0$으로 결정된 위치에 똑같이 $0$을 가질 수가 없습니다. 따라서 이 전략을 사용하는 방어자는 항상 승리할 수 있으며, 3개의 $0$을 제외한 나머지는 모두 $2$가 되므로 이 전략을 쓰기 위해 필요한 $m$의 최솟값은 $2n-3$이 됩니다.
공격자로서
$m$이 $2n-3$ 미만일 때 방어가 항상 불가능한지 생각해 봅시다. $m=2n-4$일 때 $1$을 하나만 갖고 있는 $n$개의 원소 중 둘을 고르는 방법들을 고려해보겠습니다. 이를 편의상 공격 원소라고 부르겠습니다. $n < 20$이므로 공격 원소의 방어자의 변환 후 결과는 질문을 통해 모두 얻어낼 수 있습니다.
두 공격 원소를 고르면 공격자의 제약 조건에 의해 나머지 한 원소는 $1$을 $n-2$개 갖고 있는 어떤 비트열로 자동 결정됩니다. 이를 편의 상 받이 원소로 부르겠습니다.
이제 공격 원소들 중 $0$이 둘 이상 포함된 원소가 $i$개라고 합시다. 그러면 나머지 $n-i$개의 공격 원소들은 모두 하나 이하의 $0$을 가지고 있어야 합니다. 거기에 더해 $n$개의 원소가 가진 $0$의 위치는 모두 서로 중복되어서는 안 됩니다. 특히, $n-i \ge 2$일 때 해당 원소들 중 둘을 골랐을 때 방어 가능하려면 모두 정확히 한 개의 $0$을 가지고 있어야 합니다. 이를 바탕으로 케이스를 둘로 나눠 생각합시다.
- $n-i$개의 원소가 모두 하나의 $0$을 가질 때, 골라야 하는 $0$의 위치의 총 개수는 최소 $2i + n-i = n+i$이고, $i > 0$일 때 비둘기집 원리에 의해 중복되는 위치에 $0$을 갖는 두 공격 원소가 반드시 존재하게 됩니다.
- $n-i = 1$이고 그 하나의 원소가 $0$을 가지고 있지 않을 때 골라야 하는 $0$의 위치의 총 개수는 최소 $2(n-1) = 2n-2$개이고, 문제 조건 상 $n \ge 3$이므로 $2n-2 > n$입니다. 따라서 1번 케이스와 동일하게 비둘기집 원리에 의해 중복되는 위치에 $0$을 갖는 두 공격 원소가 반드시 존재합니다.
따라서 공격 원소들이 서로 중복되지 않는 위치에 $0$을 가지려면 $i = 0$일 수밖에 없고, 모든 공격 원소가 정확히 하나의 $0$을 가지고 있음을 알 수 있습니다.
이 상황에서 $m = 2n-4$로 공격을 성공시키려면 모든 받이 원소가 2개의 $0$을 가지고 있어야 합니다. 그런데 이는, 두 개의 $0$이 공격 원소의 $1$의 위치에 있어야 함으로부터, 한 공격 원소의 $1$ 위치에 $0$이 있는 다른 공격 원소를 골라 공격을 시도하면 반드시 공격이 성공함을 알 수 있습니다.
따라서 $m=2n-4$ 이하일 때 공격자는 $n$개의 공격 원소 중 어떤 둘을 포함시켰을 때 반드시 공격을 성공시킬 수 있습니다.
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
int main(){
cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);
int n, m; cin >> n >> m;
if(m >= 2*n-3){
cout << "0" << endl;
for(int i = 1; i < (1<<n); i++){
int zero = 0;
int t = i+((i&1)<<n);
for(int bit = n-1; bit >= 0; bit--){
if((t&(1<<bit+1)) > 0 && (t&(1<<bit)) == 0) zero = bit;
}
for(int bit = n-1; bit >= 0; bit--){
if(i&(1<<bit)) cout << 1;
else if(bit == zero) cout << 0;
else cout << 2;
}
cout << endl;
}
return 0;
}
else{
cout << "1" << endl;
vector<string> one(n);
for(int bit = 0; bit < n; bit++){
cout << "? ";
for(int b = n-1; b >= 0; b--){
if(b == bit) cout << 1;
else cout << 0;
}
cout << endl;
cin >> one[bit];
}
for(int i = 0; i < n; i++) for(int j = i+1; j < n; j++){
int cnt = 0;
for(int bit = 0; bit < n; bit++){
if(one[i][bit] == '2') cnt++;
if(one[j][bit] == '2') cnt++;
if(one[i][bit] == '0' && one[j][bit] == '0'){
cout << "! ";
for(int b = 0; b < n; b++){
if(one[i][b] == '1') cout << 1;
else cout << 0;
} cout << ' ';
for(int b = 0; b < n; b++){
if(one[j][b] == '1') cout << 1;
else cout << 0;
} cout << ' ';
for(int b = 0; b < n; b++){
if(one[i][b] != '1' && one[j][b] != '1') cout << 1;
else cout << 0;
}
cout << endl;
return 0;
}
if(one[i][bit] != '2' && one[j][bit] != '2') cnt++;
}
if(cnt > m){
cout << "! ";
for(int b = 0; b < n; b++){
if(one[i][b] == '1') cout << 1;
else cout << 0;
} cout << ' ';
for(int b = 0; b < n; b++){
if(one[j][b] == '1') cout << 1;
else cout << 0;
} cout << ' ';
for(int b = 0; b < n; b++){
if(one[i][b] != '1' && one[j][b] != '1') cout << 1;
else cout << 0;
}
cout << endl;
return 0;
}
}
}
}