Dashboard - Codeforces Round #720 (Div. 2) - Codeforces
codeforces.com
오...
학회 내 코드포스 스터디에서 매주 금요일 23:35에 버추얼 라운드를 도는데, 본 라운드가 있는 날에는 그 라운드를 다같이 친다.
백만년만의 코포라 당연히 떨어질 줄 알았는데 올랐다...
블루를 가기 바로 직전인 이 레이팅에서 가장 고통스럽다는 걸 잘 알고 있지만.
minigimbob 계정이 블루를 달성하고 나서는 쭉 minigb 계정으로 참여했는데, 부계정이기도 하고 크게 동기부여 될만 한 게 없어서 별로 진지하진 않았다.
근데 요즘 코드포스를 다시 열심히 하고 싶어져서 꾸준히 잘 해볼 생각이다.
ㅎㅎ
지금 내 실력은 딱 오늘 같은 수준이다.
B까지는 꽤 빠르게 풀지만 C는 결국 풀지 못하는...
당분간 목표는 C까지 안정적으로 푸는 실력이 되는거다.
A.
처음에 a, b 범위가 10^18까지인 줄 착각해서 놀랐다. 그럴리가 없지!
x = a, y = a * (b - 1), z = a * b이면 된다고 생각했는데, b가 2이면 x != y이어야 한다는 조건을 만족하지 못한다.
그래서 예외 처리를 하려다가 그냥 y = a * b, z = a * (b + 1)로 했다.
그리고 만약 b가 1이면 가능한 경우가 없으므로 "NO"를 출력해준다.
1의 배수가 아닐 순 없으니까..ㅎㅎ
int main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int tc; cin >> tc;
while (tc--) {
ll a, b; cin >> a >> b;
if (b == 1) {
cout << "NO" << ENDL;
continue;
}
cout << "YES" << ENDL;
cout << a << ' ' << a * b << ' ' << a * (b+1) << ENDL;
}
return 0;
}
B.
처음엔 막막했는데 쉽게 푼 문제.
모든 인접한 두 수가 서로소여야 하기 때문에
인접한 두 인덱스에 대해 하나는 두 수의 최솟값을, 하나는 매우 큰 소수를 가지면 된다.
문제에 각 수가 가질 수 있는 최댓값에 대한 제한 같은 게 없기 때문에.
const int PRIME = 1e9 + 7;
int main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int tc; cin >> tc;
while (tc--) {
int n; cin >> n;
vector<int> arr(n);
for (int i = 0; i < n; i++) cin >> arr[i];
vector < pair<pair<int, int>, pair<int, int>>> ans;
for (int i = 0; i < n - 1; i += 2) {
ans.push_back({ {i + 1, i + 1 + 1}, {min(arr[i], arr[i + 1]), PRIME} });
}
cout << ans.size() << ENDL;
for (int i = 0; i < ans.size(); i++) {
cout << ans[i].first.first << ' ' << ans[i].first.second << ' '
<< ans[i].second.first << ' ' << ans[i].second.second << ENDL;
}
}
return 0;
}
C.
interactive 문제
라운드가 끝날 때까지 거의 1시간 50분 정도 고민했지만 결국 못 풀었다.
내가 생각한 풀이는 O(n^2)가 최선이었다. ('최선'이라는 표현을 사용해도 되는걸까 다 이 정도는 생각했을 거 같은데)
끝나고 학회 스터디에서 풀이를 들었다.
t = 1: max(min(x, p[i]), min(x + 1, p[j]))
t = 2: min(max(x, p[i]), max(x + 1, p[j]))
전반적인 풀이는 t = 2의 쿼리를 이용해 1의 위치를 찾고 이를 이용해 t = 1 쿼리로 나머지 값들을 찾는 것이다.
(반대로 t = 1 쿼리로 n - 1의 위치를 찾고 t = 2 쿼리로 나머지 값들을 찾아도 된다.)
질문 가능한 횟수가 최대 3*n / 2번이어서 이 수가 특별한 의미가 있을 것 같았는데
1의 위치를 찾을 때 둘씩 짝지어 검사하므로 n / 2회 질문하고,
이를 이용해 전체 값을 찾을 때 n회 질문하므로 전체 약 3*n / 2회의 질문이 필요하다.
역시.. 모든 수에는 다 의미가 있다.
이를 구체화해보면
우선 1의 위치를 찾을 때는 t = 2, x = 1로 두고 인접한 두 인덱스씩 짝지어 질문하면 된다. (for i in range(0, n-1, 2): j = i + 1)
만약 p[i] = 1이면 답변이 1이다.
역으로 답변이 1이면 1의 위치가 i라는 게 성립하는데, p[i] = 1인 것 외에는 답변이 1이 나오는 상황이 없기 때문.
만약 p[j] = 1이면 답변이 2가 나오는데,
답변이 2인 또 다른 경우로는 p[i] >= 3, p[j] = 2인 상황도 있다.
그래서 i, j를 바꿔서 다시 질문해 둘 중 어떤 경우인지 판단할 수 있는데
답변이 1이면 p[j] = 1이라는 의미이고, 그렇지 않으면 그냥 무시하면 된다.
이 과정에서 주의할 점은 i를 2씩 증가시키다가 n이 홀수이고 마지막 인덱스에 1이 있는 상황을 놓칠 수 있다는 거다.
그 부분을 꼭 체크해야 한다.
이렇게 1의 위치를 찾고 나면 t = 1의 쿼리를 이용해 나머지 값들을 모두 찾을 수 있는데
i = (1의 인덱스), j = (확인하는 인덱스), x = n - 1로 질문하면 된다.
min(x, p[i]) = 1, min(x + 1, p[j]) = p[j]이므로 답변은 max(1, p[j]) = p[j]이다.
int GetResponse(int t, int i, int j, int x) {
cout << "? " << t << ' ' << i + 1 << ' ' << j + 1 << ' ' << x << ENDL;
cout.flush();
int response; cin >> response;
return response;
}
int main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int tc; cin >> tc;
while (tc--) {
int n; cin >> n;
vector<int> ans(n, -1);
int oneIdx = -1;
for (int i = 0; i + 1 < n; i += 2) {
int res = GetResponse(2, i, i + 1, 1);
if (res == 1) {
oneIdx = i; break;
}
else if (res == 2) {
if (GetResponse(2, i + 1, i, 1) == 1) {
oneIdx = i + 1; break;
}
}
if (n % 2 == 1 && i + 2 == n - 1) i--;
}
for (int i = 0; i < n; i++) {
if (i == oneIdx) {
ans[oneIdx] = 1;
continue;
}
ans[i] = GetResponse(1, oneIdx, i, n - 1);
}
cout << "! "; cout.flush();
for (int i = 0; i < n; i++) {
cout << ans[i] << ' ';
cout.flush();
}
cout << ENDL; cout.flush();
}
return 0;
}와 진짜 엄청난 문제..
재밌구만...!!
그리고 이 문제 풀 때 가장 중요한 포인트가 배열이 permutation이라는 거다
그 조건이 없으면 이렇게 못 푼다.