📝 문제 정보#
문제 번역#
두 형제 Aldo와 Bondan은 COVID-19 팬데믹 상황이 악화되어 도시가 다시 봉쇄되면서 집에 갇혀 있습니다. 그들은 학기를 마치고 방학 중이지만, 집 밖으로 나갈 수 없다면 무슨 방학을 즐길 수 있을까요? 하지만 지루함은 창의성을 불러일으킵니다. 그들은 지루한 방학 동안 새로운 게임을 만들었습니다.
이 게임은 R행 C열의 보드에서 진행되며, 각 칸은 0개 또는 1개의 토큰을 포함합니다. 각 토큰은 ‘a’부터 ‘z’까지의 문자로 표현되는 26가지 색상 중 하나로 칠해져 있습니다. 보드에는 최소 하나의 토큰이 있습니다.
두 명의 대전 플레이어가 번갈아가며 플레이합니다. 자신의 턴에 플레이어는 하나의 토큰을 선택하여 인접한 칸(북쪽, 남쪽, 서쪽 또는 동쪽 방향)으로 이동시킵니다(비어있지 않은 칸으로도 이동 가능).
**좋은 이동(good move)**은 색상 x의 토큰을 이미 같은 색상 x의 토큰이 있는 칸으로 이동시키는 경우에만 성립합니다.
게임의 목표는 가능한 한 많은 좋은 이동을 하는 것입니다. 좋은 이동을 엄격하게 더 많이 한 플레이어가 게임에서 승리합니다. 두 플레이어가 같은 수의 좋은 이동을 했다면 무승부이며 아무도 이기지 못합니다.
이 게임은 무한정 플레이될 수 있습니다. 하지만 Aldo와 Bondan은 Aldo가 첫 번째 이동을 하고 총 10^100번의 이동을 하기로 합의했습니다.
Bondan은 이런 종류의 게임이 지루하다고 생각하여 게으르게 플레이하기로 결정했습니다. Bondan의 턴이 될 때마다, 그는 Aldo가 바로 직전 턴에 이동시킨 것과 같은 토큰을 선택하고, 그 토큰을 인접한 칸으로 균일하게 무작위로 이동시킵니다.
그럼에도 불구하고 Bondan은 지는 것을 좋아하지 않습니다. 게임이 시작되기 전에, 그는 보드 크기를 변경하거나 토큰의 초기 위치를 이동시켜 Bondan이 게으르게 플레이하더라도 Aldo가 게임에서 이길 확률이 정확히 0이 되도록 보드를 변경할 수 있습니다.
구체적으로, 보드는 R × C에서 R’ × C’로 확장될 수 있으며(R’ ≥ R이고 C’ ≥ C), 각 토큰의 초기 위치는 각 칸에 최대 하나의 토큰만 있도록 보장하면서 다른 칸으로 이동될 수 있습니다. 토큰을 버리거나 새로운 토큰을 보드에 추가할 수 없습니다.
이 문제에서 여러분의 과제는 Bondan이 게으르게 플레이하더라도 총 10^100번의 이동으로 Aldo(첫 번째 플레이어)가 게임에서 이길 확률이 0이 되도록 하는 새로운 보드 설정을 찾는 것입니다. 새로운 보드 설정은 최소 총 칸 수를 가져야 합니다. 여러 해답이 있다면 그 중 하나만 출력하면 됩니다.
입력#
첫 줄에 두 정수 R C (1 ≤ R, C ≤ 1000)가 주어지며, 이는 보드의 초기 행 수와 열 수를 나타냅니다. 보드에는 최소 2개의 칸이 있음이 보장됩니다.
다음 R개의 줄에는 각각 C개의 문자가 포함되어 초기 보드 상태를 나타냅니다. ‘.’ 문자는 빈 칸을 나타내고, 소문자 알파벳(‘a-z’)은 해당 색상의 토큰을 나타냅니다. 보드에는 최소 1개의 토큰이 있음이 보장됩니다.
출력#
첫 줄에 두 정수 R’ C’를 출력하며, 이는 새로운 보드의 행 수와 열 수를 나타냅니다.
다음 R’개의 줄에는 각각 C’개의 문자가 포함되어 새로운 보드 상태를 나타냅니다. ‘.’ 문자는 빈 칸을 나타내고, 소문자 알파벳(‘a-z’)은 해당 색상의 토큰을 나타냅니다.
새로운 보드는 Bondan이 게으르게 플레이하더라도 총 10^100번의 이동으로 Aldo(첫 번째 플레이어)가 게임에서 이길 확률이 0임을 보장해야 합니다. 최소 총 칸 수를 가져야 하며 초기 보드와 동일한 토큰 세트를 가져야 합니다.
🧐 관찰 및 접근#
- 같은 알파벳들끼리의 격자그래프 홀짝성을 맞추면 되는거같다. (다 짝수로)
- 알파벳별로 개수가 정해졌을때, 어떻게 밀어넣냐인데..
- $a$만 엄청 많다고 할때, 여러줄로 하는거보다 한줄에 밀어넣는게 더 좋다.
- 근데 뭐가됐든 $R'*C'$를 최소화해야하는데..
- $R'$를 정했다고 가정하면, 모든 토큰들을 넣을수 있게 되는 $C'$를 찾는건 단조성이 있으니 이분탐색으로 가능할 것 같다.
- $R', C'$를 정했을때 그리디하게 알파벳들을 집어넣어도 될까?
- 이건 된다!
- 그러면 짝수칸 / 홀수칸에 맘대로 넣을 수 있다는걸 생각하면, 배낭문제처럼 보인다.
- 그런데, 짝수칸은 홀수칸보다 최대 한개 많을 수 있다.
- 그렇다면, 양쪽 배낭의 합의 차이를 최소로 만드는 전략이 유효해보인다.
- 그런데, 짝수칸은 홀수칸보다 최대 한개 많을 수 있다.
- 이분탐색 등을 잘 버무려서, 어케어케 짝수칸 / 홀수칸의 합을 넘기는 $R', C'$를 구하자.
- 이후 그리디하게 문자들을 채워넣으면 된다.
💻 풀이#
- 코드 (C++):
int calc_evenCnt(int r, int c){
return ((r+1)/2) * ((c+1)/2) + (r/2) * (c/2);
}
void solve(){
cin >> R >> C;
rep(i, 0, R){
string S; cin >> S;
for(auto c: S) if(c != '.') cnt[c-'a']++;
}
rep(i, 0, 26) sum += cnt[i];
vector<bitset<mxRC>> DP(27, bitset<mxRC>());
DP[0][0] = 1;
rep(i, 0, 26) DP[i+1] = DP[i] | (DP[i] << cnt[i]);
int mnDiff = mxRC, mnSum = -1;
rep(i, 0, mxRC) if(DP[26][i]){
if(abs(i - (sum - i)) < mnDiff){
mnDiff = abs(i - (sum - i));
mnSum = sum - i;
}
}
int goal = max(mnSum, sum - mnSum);
vector<bool> used(26, false);
int cidx = 26, csum = goal;
while(cidx && csum){
if(cnt[cidx-1] && csum-cnt[cidx-1] >= 0 && DP[cidx-1][csum - cnt[cidx-1]]){
used[cidx-1] = true;
csum -= cnt[cidx-1];
}
cidx--;
}
pii ret = {-1, -1};
int mnRC = mxRC;
rep(nR, R, R*C*2){
if(nR * C > mnRC) break;
int ok = R*C*2, ng = C-1;
while(ok - ng > 1){
int mid = (ok + ng) / 2;
int evenCnt = calc_evenCnt(nR, mid);
int oddCnt = nR * mid - evenCnt;
if(evenCnt >= goal && oddCnt >= sum - goal) ok = mid;
else ng = mid;
}
if(nR * ok < mnRC){
mnRC = nR * ok;
ret = {nR, ok};
}
}
auto [nR, nC] = ret;
cout << nR << ' ' << nC << '\n';
queue<char> Q[2];
rep(i, 0, 26){
if(used[i]) rep(_, 0, cnt[i]) Q[0].push(char('a' + i));
else rep(_, 0, cnt[i]) Q[1].push(char('a' + i));
}
rep(i, 0, nR) rep(j, 0, nC){
if((i+j)%2){
if(!Q[1].empty()){
cout << Q[1].front();
Q[1].pop();
}
else cout << '.';
}
else{
if(!Q[0].empty()){
cout << Q[0].front();
Q[0].pop();
}
else cout << '.';
}
if(j == nC-1) cout << '\n';
}
}