Last updated: 2022. 02. 09
Codeforces Round #770 (Div. 2)
\standing.PNG)
\result.PNG)
\rating.PNG)
A. Reverse and Concatenate (AC)
Problem
요약
입력으로 길이가 n인 문자열 s와 정수 k가 주어진다. rev(s) 함수는 s 문자열을 뒤집은 문자열을 의미한다. (ex, rev(abc) = cba) 우리는 다음 2가지 작업 중 하나의 작업을 할 수 있다.
- 문자열 s를 ‘s + rev(s)’ 로 치환한다.
- 문자열 s를 ‘rev(s) + s’ 로 치환한다.
주어진 문자열 s에 대해 위의 작업을 정확히 k번 반복했을 때, 얻을 수 있는 서로 다른 문자열의 종류는 몇가지인가?
입력
t : 테스트 케이스 개수 (1 <= t <= 100)
n : (1 <= n <= 100)
k : (0 <= k <= 1,000)
출력
답은 10^9을 넘지 않는다.
Solution
가능한 경우를 세는 것이 문제이기 때문에 모든 경우에 대해 다 해보고 싶지만 k 가 최대 1,000이기 때문에 가능한 모든 경우를 하려면 2^1000 의 경우의 수가 생긴다.
그렇다면 어떻게 우리는 서로 다른 문자열의 개수를 어떻게 샐 수 있을까?
가장 먼저 떠오른 것은 문자열 s가 대칭 문자열이라면 주어진 2가지 작업 중 어떤 작업을 하더라도 같은 결과가 나올 것이라는 것이다.
그렇다면 어느순간 문자열 s가 대칭이라면 남은 작업 동안 어떻게 작업을 하던 그 결과들은 같아질 것이라는 것이다.
이 생각을 해냈다면 문제는 쉽게 풀 수 있다.
노가다를 두려워하지 않고 몇번 끄적이다보면 위의 2가지 작업 중 어떠한 작업을 하더라도 다음에 나오는 문자열은 무조건 대칭 문자열이라는 것을 알 수 있다. 즉, 2번째 작업부터는 어떤 작업을 선택하든 결과는 같아진다는 것이다.
이는 k번의 작업 후의 결과는 첫번째 작업이 결정한다는 뜻이며, 문제에서는 답이 10^9을 넘지 않는다고 거창하게 말했지만 답은 최대 2가 된다.
그렇다면 언제 답이 1이고, 언제 답이 2일까? 그것은 처음 입력으로 주어진 문자열이 대칭 문자열이면 답은 1이고, 그렇지 않으면 답이 2가 된다.
Code
#include <iostream>
#include <string>
using namespace std;
int main()
{
ios_base :: sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
string s;
int t, n, k, i;
cin >> t;
while(t--){
cin >> n >> k;
cin >> s;
for(i=0; i<n; i++){
if(s[i] != s[n-i-1]) break;
}
if(i < n && k > 0) cout << 2 << '\n';
else cout << 1 << '\n';
}
return 0;
}
B. Fortune Telling (AC)
Problem
요약
Alice와 Bob은 다음과 같은 방법으로 점을 치기로 했다.
1부터 n까지 번호가 붙은 음이 아닌 정수로 이루어진 배열 a가 주어진다. 점을 치는 사람은 음이 아닌 정수 d로 점을 치기 시작하며, 모든 a_i에 대하여 다음의 2가지 작업 중 하나를 수행해 나간다. (작업은 i가 1부터 n까지 1씩 증가하는 순서로 이루어진다.)
- 현재 정수 d를 d + a_i 로 바꾼다.
- 현재 정수 d를 d ⊕ a_i 로 바꾼다. (⊕는 비트 연산자인 XOR 연산이다.)
Alice는 x로 점을 치기 시작하며, Bob은 x+3으로 점을 치기 시작했고, n번의 작업 후 Alice와 Bob 중 정확히 한 명이 정수 y에 도달하였다. 정수 배열 a와 x, y가 주어졌을 때, Alice와 Bob 중 누가 y에 도달하였는지 알아내라.
답은 반드시 존재한다.
입력
t : 테스트 케이스 개수 (1 <= t <= 10^4)
n : (1 <= n <= 10^5)
x : (0 <= x <= 10^9)
y : (0 <= y <= 10^15)
a_i : (0 <= a_i <= 10^9)
모든 테스트 케이스에 대한 n의 총 합이 10^5이 넘지 않음이 보장된다.
출력
“Alice” 혹은 “Bob”으로 출력하라.
Solution
이 문제는 초반에 문제 해석을 잘못했다. ㅜㅜ
첫째는 “Notice that the chosen operation may be different for different i and for different tellees.” 이 문장을 잘못 해석했고,
둘째는 “ i=1,2,…,n in the increasing order of i” 이 문장에 큰 의미를 두지 않고 해석을 해버렸다.
그 결과 a_i 들의 연산 순서와 횟수 모두 자유롭다고 해석해버려 문제를 너무 어렵게 접근했다 ㅜㅜ
문제를 잘못 해석 했으니 당연히 문제가 너무 어려웠고, 예제의 3번째 테스트 케이스를 보다 내가 잘못 해석했다는 것을 깨달았다.
문제를 잘못 해석했을 때에도, 시작 값이 x와 x+3인 것을 보고, 분명 문제의 키가 +3에 있을 것이라는 생각이 들었고, 문제를 제대로 해석하고나자 +3이 있는 이유에 대해 알 수 있었다.
문제에서 비트 연산이 나왔기 때문에 예제를 공책에 끄적일 때 숫자들을 모두 2진수로 바꿔 끄적였었다. 그리고 3이라는 숫자는 2진수로 11 매우 수상한 숫자이다. 여기서 +3을 하면 항상 마지막 비트의 값이 바뀐다는 생각을 했다면 베스트다.
문제에서 주어진 2가지 작업에 대해 살펴보자. 하나는 + 연산이고, 하나는 XOR 연산이다. 이 2가지 연산에 대한 공통점은 무엇일까? 무엇을 하든 마지막 비트에는 똑같은 영향을 끼친다는 것이다. a_i의 마지막 비트가 1이면 두 연산 모두 d의 마지막 비트를 바꾸고, a_i의 마지막 비트가 0이면 두 연산 모두 d의 마지막 비트를 바꾸지 않는다는 것이다.
이 생각까지하면 왜 문제에서 정확히 한 명만이 y에 도달했는지에 대해서도 이해가 된다. Alice와 Bob이 마지막 비트가 다른 상태로 시작하게 되고, 어떤 작업을 고르든 마지막 비트는 항상 동일하게 바뀌므로 n번의 작업 후 Alice와 Bob이 가진 수의 마지막 비트는 항상 다르게 되는 것이다.
여기까지 생각을 했다면 코드는 매우 간단하게 구현 할 수 있다. 우리는 x나 x+3에서 y를 만들어내는 것이 아니라 둘 중 누가 y와 마지막 비트가 같게 되냐이기 때문에 그냥 x에 a_i들을 모두 더하거나 XOR 시킨 후, y와 마지막 비트를 비교해주면 된다. (나는 x를 32bit 정수에서 끝내고 싶어 XOR 연산을 시켰다. 비트 연산이 더 빠르기도 하고….)
주의 : y를 long long 으로 선언하고, 비트연산 우선 순위에 대해 주의해라.
Code
#include <iostream>
using namespace std;
int main()
{
ios_base :: sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int t, n, x, a, i;
long long y;
cin >> t;
while(t--){
cin >> n >> x >> y;
for(i=0; i<n; i++){
cin >> a;
x ^= a;
}
if((x&1) == (y&1)) cout << "Alice\n";
else cout << "Bob\n";
}
return 0;
}
처음에 조건문 안의 조건을 “x&1 == y&1” 로 하였는데, 연산자의 우선 순위가 &보다 ==가 더 빠른지 항상 False가 떴다.
C. OKEA (AC)
Problem
요약
양의 정수 n, k가 주어졌을 때, 다음 조건에 맞게 1부터 n*k까지의 수를 n*k 격자에 배치하는 것이 문제이다.
- 1부터 n*k까지의 수는 정확히 한번씩 나와야 한다.
- 모든 i, l, r에 대하여, i번째 줄의 l번부터 r번까지 격자에 있는 수의 평균이 정수가 되어야 한다.
입력
t : 테스트 케이스 개수 (1 <= t <= 500)
n, k : (1 <= n, k <= 500)
모든 테스트 케이스에 대하여 n과 k의 총합은 각각 500을 넘지 않는다.
출력
문제의 조건에 맞게 수를 격자에 배치가 가능하다면, “YES”를 출력 후, 가능한 경우 중 하나를 출력하고,
불가능 하다면, “NO”를 출력하여라.
Solution
막막하다…. “YES” 혹은 “NO”를 출력하라는 것에서 그치지 않고, “YES”라면 가능한 경우를 출력하라니, 입력 값의 범위가 500이라니… 알고리즘이 복잡할 것이라는 생각이 막 든다.
그러나 n과 k가 각각 500이므로, 시간 복잡도가 O(NK) 혹은 O(NKlogK) 정도가 아닐까 조심스레 추측을 해보았다.
문제가 어려워 보여도 포기할 순 없으니 열심히 끄적여 봤다.
모든 줄에 대해 생각하는 것이 아니라 일단 한줄 한줄 완성해보기로 했다.
l=r이면 뭐 평균이 곧 격자에 해당하는 값일테니 당연히 정수일테고,
l부터 r까지 격자(이하 격자)의 크기가 2인 경우, 평균이 정수이려면 격자 안의 두 수의 홀짝성이 같아야 한다.
격자의 크기가 3이면…. 흐음….. 모르겠다 ㅜ
1이 어딘가엔 쓰여야 하니 처음 수를 1로 두고 다음 수들을 채워나가 보기로 했다. (왠지 1이 중간에 가면 안될거 같았다.)
하지만 여기서도 격자의 크기가 3일때 막혔다.
처음 수를 a라 두고, 다음 수를 a+2k라 두면…. 다음 수는…. a+3k’-2k….
다시 1부터 시작해봤다. 처음 수를 1, 다음 수를 3, 그럼 다음 수는 5….. ?!
갑자기 머릿속에 스쳐가는 생각, 등차수열이어야 하나?
등차수열만 가능한진 모르겠지만 우선 등차수열은 항상 위의 조건을 만족한다. 그렇다면 등차가 2인 수열로 각 줄을 완성한다면? 뭔가 될거 같다.
여기까지 생각하자, 우선 n이 짝수인 경우는 만들 수 있다는 것을 깨달았다.
그런데, n이 홀수인 경우 불가능하다는 것을 증명할 수 있을까? 이는 앞서 생각했던 것들에서 답을 찾았다. 격자의 크기가 2일 땐, 두 격자에 들어 있는 수의 홀짝성이 같아야 한다. 그렇다면 격자를 오른쪽으로 한칸 옮긴다면? 그 두 격자의 수의 홀짝성도 같아야 한다. 그 오른쪽도 마찬가지고 그 오른쪽도 마찬가지다. 즉 한 줄의 홀짝성이 같아야 한다.
그러나 n이 홀수라면? 처음 시작하는 값이 홀수든 짝수든 하나로 시작해야 하는데, 그럼 그 줄에 있는 k개의 홀짝성은 다 같아야 한다. 아무리 내가 처음 시작하는 값을 잘 설정한다고 해도, (n-1)/2개의 줄과 (n+1)/2개의 줄로 짝수든 홀수든 줄의 개수가 하나 많아진다. 그러나 1~n*k의 수에는 홀수와 짝수의 개수가 같거나 홀수가 하나 더 많다. n이 홀수일 때 답이 YES가 되는 경우는, 예제에 나와 있는 경우인 k가 1인 경우 단 하나 밖에 존재하지 않는다는 것을 알 수 있다.
사족이 길었다. 그럼 이제 코드로 넘어가보자.
우선 YES가 되는 경우는, k가 1이거나 n이 짝수인 경우이다. 반대로 NO인 경우는 k가 1이 아니면서 n이 홀수인 경우이다.
YES인 경우는 첫 줄은 1부터 1+2(k-1)까지 공차가 2인 수열을 출력해주고, 두번째 줄은 2부터 2+2(k-1)까지, 세번째 줄은 1+2k부터 1+4k-2까지 …. 이런식으로 출력해주면 된다.
이 부분은 알아서 짜도록 ㅎㅎ
+ 그리고 풀이를 적으면서 떠오른 방법인데, 각 줄이 등차수열이기만 하면 되므로, 공차가 n인 수열로 하면 i번째 줄의 시작 값을 i로 매우 쉽게 격자를 완성할 수 있다는 것을 깨달았다.
Code
대회 코드:
#include <iostream>
using namespace std;
int main()
{
ios_base :: sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int t, n, k, i, j;
int a[2];
cin >> t;
while(t--){
cin >> n >> k;
if(k != 1 && n%2 == 1) cout << "NO\n";
else{
cout << "YES\n";
a[0] = 1;
a[1] = 2;
for(i=0; i<n; i++){
for(j=0; j<k; j++){
cout << a[i%2] << ' ';
a[i%2] += 2;
}
cout << '\n';
}
}
}
return 0;
}
추가 수정 코드:
#include <iostream>
using namespace std;
int main()
{
ios_base :: sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int t, n, k, i, j;
cin >> t;
while(t--){
cin >> n >> k;
if(k != 1 && n%2 == 1) cout << "NO\n";
else{
cout << "YES\n";
for(i=1; i<=n; i++){
for(j=0; j<k; j++){
cout << i+j*n << ' ';
}
cout << '\n';
}
}
}
return 0;
}
D. Finding Zero (WA > AC)
Problem
요약
This is an interactive problem.
상호작용 문제이다. 업다운 문제처럼 내가 질문을 하면 답변을 주고, 이를 바탕으로 답을 맞추는 매우 재미있는 문제이다.
정수 n이 주어지고, 컴퓨터는 크기가 n인 정수 수열 a를 생각한다. 수열의 각 수는 0부터 10^9까지의 정수로 이루어져 있으며, 0은 정확히 1개 들어 있다. 우리는 수열 a에서 0의 위치를 찾아내는 것이 목표이다. (수열의 인덱스는 1부터 n까지 붙어있다.)
질문은 아래와 같이 할 수 있다.
? i j k
이에 대한 답변은 max(a_i, a_j, a_k) - min(a_i, a_j, a_k) 의 값이다. 즉, i, j, k번째 수 중 가장 큰 값에서 가장 작은 값을 뺀 결과를 알려주는 것이다.
질문은 최대 2*n-2번 할 수 있으며, 정답은 단 한번 외칠 수 있고, 한번에 2개의 수를 말할 수 있다. 2개의 수 중 하나라도 답이면 정답이다. 정답은 다음과 같이 외칠 수 있다.
! i j
입력
t : 테스트 케이스 개수 (1 <= t <= 500)
n : (4 <= n <= 1,000)
모든 테스트 케이스에 대하여 n의 총 합은 3,000을 넘지 않는다.
출력
쿼리를 출력하고 나면 버퍼 flush를 해줘라.
- fflush(stdout) or cout.flush() in C++;
- System.out.flush() in Java;
- flush(output) in Pascal;
- stdout.flush() in Python;
- Read documentation for other languages.
Solution
이 문제만 1시간 반을 고민했지만, 풀어내지 못하였다 ㅜㅜ
보통 이런 문제는 기준을 잡아놓고 하나씩 정보를 알아가는 것이 좋다.
그렇기에 나는 0, 1번째 수를 기준으로 잡았고, 나머지 하나의 수를 2~n-1까지의 수로 잡았다. (문제를 제대로 안읽어서 인덱스가 0번부터 n-1번까진 줄 알았다 ㅜㅜ 인덱스가 0부터 n-1인걸로 후술하도록 하겠다)
a_0와 a_1이 0과 가장 큰 수가 아니라고 가정하면, “? 0 1 i” 중 가장 큰 값을 가지는 a_i가 0 혹은 가장 큰 값일 것이다.
%5CD_img.png)
a_0와 a_1이 빨간 점이라고 한다면, a_i가 a_0와 a_1 사이의 값이면 항상 동일하게 a_0와 a_1의 차가 입력된 것이고(파란 화살표), a_i가 a_0와 a_1 두 값보다 작다면 노란 화살표 길이만큼의 값이 입력될 것이고, 이 중 최댓값은 a_i가 0일 때일 것이다. 반대로 a_i가 두 값보다 크다면 초록색 화살표 길이만큼의 값이 입력될 것이고 최댓값은 a_i가 최댓값일 때이다. 위의 그림에서 노란 화살표와 초록 화살표 내부에서는 굵은 화살표가 제일 길지만, 노란 화살표와 초록 화살표 중에는 어떤 값이 더 클지는 상황에 따라 다르다. 즉, 맨 끝 값의 위치만 알 수 있지 그 값이 0인지 최댓값인지는 알지 못한다.
그러나 우리에게는 2*n-2 번의 질문 횟수가 있다. 위에서 n-2번의 질문을 했으니 n번의 질문이 아직 남아 있는 것이다. 앞의 방법으로 찾은 위치가 0의 위치라면 좋겠지만, 최댓값의 위치라면 0의 위치를 찾아야 한다. 위에서 답변의 값이 최대였던 위치를 x라고 한다면, 이번엔 0과 x를 기준으로 나머지를 물어본다. “? 0 x i” 와 같은 방법으로 말이다. 여기서 i가 1이면 “? 0 1 x”와 같은 질문이므로 굳이 안해도 된다.
이 과정에서도 질문에 대한 답변이 최대인 값을 구하면 이 값은 또 다른 끝의 위치일 것이다. 즉, 처음 n-2번의 질문과 다음 n-3번의 질문으로 우리는 양 끝 값의 위치를 알아낼 수 있게 된 것이다.
처음 n-2번의 질문으로 얻어낸 위치를 x, 다음 n-3번의 질문으로 얻어낸 위치를 y라고 하면 “! x y”를 출력해주면 우리는 답을 맞출 수 있는 것이다!
라고 생각했지만 이게 답이 아닌 경우가 있을 것이다. 바로 0번째 혹은 1번째 값 중에 0 혹은 최댓값이 있는 경우이다. x와 y에서 0과 1은 고려 대상이 아니기 때문에 이 경우 오답이 나오게 된다.
더 많은 경우가 있을 수도 있지만(아마 이것 때문에 틀리지 않았을까 싶다.), 나는 대부분의 경우 x, y 중에 답이 있고, 그게 아니라면 0과 1 중에 답이 있을 것이라고 생각하였다. 그렇다면 우리는 0, 1, x, y 4개의 숫자 중 2개를 고르면 되는 것이 아닌가? 그렇다면 어떻게 저 4개의 숫자 중 2개의 수를 고를 수 있을까?
여기서 내가 생각한 방법은 (0, 1, x), (0, 1, y), (0, x, y), (1, x, y) 에 대한 질문의 답변을 바탕으로 이를 결정하는 것이었다.
%5CD_img2.png)
0, 1, x, y 위치에 해당하는 값의 대소관계는 잘 모르겠지만 (0, 1, x), (0, 1, y), (0, x, y), (1, x, y) 에 대한 질문의 값은 각각 위 그림에서 4개의 화살표 길이 중 하나일 것이다. 즉, 4개의 답변 중 최댓값 2개를 뽑고, 이 질문에 동시에 들어가는 2개의 값이 최종 답이 되는 것이다.
그리고 이를 하기 위해선 모르는 값이 있는데, 바로 (1, x, y)를 질문하지 않았다는 것이다. 그러나 우리에겐 3번의 질문 기회가 더 있으므로 한번 정돈 더 질문해도 된다. 즉, 마지막으로 “? 1 x y”를 질문한 뒤 앞서 말한 4개의 값을 비교해 답을 찾으면 된다.
라고 생각했는데 왜 틀렸을까 ㅜㅜ
+ 설명하지 않은 추가 고려 사항들
- 일단 앞서 언급한 인덱스를 잘못 생각한 부분은 대회 끝나고 고쳐서 제출해 봤으나 여전히 틀렸다.
- 내 생각에는 컴퓨터가 생각한 수열에 중복된 값이 있을 수 있는 것 같은데, 이를 언급하지는 않았으나 충분히 생각해봤으며, 이를 무시하고 위의 방법을 실행해도 고려된 결과가 나온다고 판단하였다.
- 마지막 0, 1, x, y 중 2개를 뽑는 방법은 항상 4개의 서로 다른 수가 필요하기에 a_0과 a_1이 끝 값이고, a_0, a_1, a_x 중 답이 있더라도 0, 1, x가 아닌 y를 선택해줘야 한다고 판단하였다. (위에서 서술한 방법대로 하면 문제 없이 진행된다.)
+ 풀이는 맞았다. y아래 코드에서 y만 초기화해주면 된다. 자세한 내용은 여기서 확인할 수 있다.
Code
#include <iostream>
#define MAXN 1000
using namespace std;
int d_01[MAXN], d_0x[MAXN], d_1xy;
int main()
{
ios_base :: sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int t, n, i, x, y, maxi, a, b;
cin >> t;
while(t--){
cin >> n;
for(i=2; i<n; i++){
cout << "? 0 1 " << i << '\n';
cout.flush();
cin >> d_01[i];
}
x = 2;
for(i=2; i<n; i++){
if(d_01[i] > d_01[x]) x = i;
}
d_0x[1] = d_01[x];
for(i=2; i<n; i++){
if(x == i) continue;
cout << "? 0 " << x << ' ' << i << '\n';
cout.flush();
cin >> d_0x[i];
}
for(i=2; i<n; i++){
if(i == x) continue;
if(d_0x[i] > d_0x[y]) y = i;
}
cout << "? 1 " << x << ' ' << y << '\n';
cout.flush();
cin >> d_1xy;
maxi = max(d_01[x], max(d_01[y], max(d_0x[y], d_1xy)));
if(d_01[x] == maxi && d_01[y] == maxi) cout << "! 0 1\n";
else if(d_01[x] == maxi && d_0x[y] == maxi) cout << "! 0 " << x << '\n';
else if(d_01[y] == maxi && d_0x[y] == maxi) cout << "! 0 " << y << '\n';
else if(d_01[x] == maxi && d_1xy == maxi) cout << "! 1 " << x << '\n';
else if(d_01[y] == maxi && d_1xy == maxi) cout << "! 1 " << y << '\n';
else if(d_0x[y] == maxi && d_1xy == maxi) cout << "! " << x << ' ' << y << '\n';
cout.flush();
}
return 0;
}
%20-%20D/status.png)
