12월 30일, 31일 PS 일기

월요일과 화요일에 각각 앳코더 ARC와 코포 딥2를 돌았습니다.
https://atcoder.jp/contests/arc060

https://codeforces.com/contest/2158

전자는 3솔/4솔로 2600, 후자는 4솔/7솔로 2300 정도 되는 퍼포먼스를 냈습니다.
앳코더의 경우 2016년 셋이라 퍼포먼스가 높게 찍힌 것 같습니다.

ARC 060부터 간단하게 후기 쓰겠습니다.

C번(00:04 WA, 00:06 AC)

문제 조건을 보았을 때 (i, i번째 카드 중 고른 카드의 수, 고른 카드들에 적힌 수의 합)을 가지고 dp를 돌리면 될 것 같이 생겼습니다.
마지막에 경우의 수를 셀 때 어딘가 잘 못 세서 WA를 하나 받았지만 금방 고치고 6분만에 AC가 나왔습니다.

체감 난이도: G5~G4
푸는 데 걸린 시간과 별개로 3차원 dp를 사용한다는 점에서 솔브닥으로 들고 가면 티어가 약간 높게 찍힐 것 같습니다.
제 체감 난이도는 "이 문제를 백준에서 풀고 기여를 준다면 어떤 티어가 나올 것인가" 를 상정해서 정했습니다. 발상하고 구현하는 난이도만 본다면 실버 중위권이 나올 겁니다..

D번(00:14 WA, 00:17 WA, 00:21 WA, 00:22 AC)

Idea 1) f(b,n)은 n을 b진법으로 나타냈을 때 자릿수의 합니다.
Idea 2) 100만 이하의 b에 대해서 f(b,n) != s라면, 답이 있을 때 n은 b진법으로 2자리이다.
루트질을 한다는 것을 발상해서 위와 같이 관찰했습니다.
100만 이하의 b에 대해서 처리했는데 답이 안 나온다면, n은 b진법으로 2자리입니다.
즉 b^1의 자릿값을 정하면 b^0의 자릿값은 자동으로 정해집니다. b^1의 자릿값은 최대 sqrt(n)이므로 sqrt(n) 시간에 f(b,n) = s를 만족하는 b>100만이 있는지 확인할 수 있습니다.

전자는 구현하기 쉬웠는데 후자를 구현할 때 식 정리를 몇 번 잘못해서 3틀을 했습니다. 여기서 크게 말렸다고 생각합니다.

체감 난이도: P3
발상, 구현하는 난이도는 제곱근 분할법을 안다는 가정 하에 G4 정도인 것 같습니다.

E번(00:30 AC)

Idea 1) 문제를 "a에서 출발해서 x일 이후 b에 도달할 수 있는가?"라는 결정 문제로 바꿀 수 있습니다.
즉, a에서 출발해서 x일 동안 어디까지 갈 수 있는지를 빠른 시간 내에 알아낼 수 있다면, 문제를 풀 수 있습니다.
Idea 2) 희소 배열 (or 세그)를 사용해서 위 쿼리를 O(log N)에 처리할 수 있다.

위 아이디어들을 종합해서 이분탐색+세그 박으면 바로 풀립니다.
D에서 많이 뇌절을 쳐서 그런가 D보다 쉽게 느껴졌습니다.

체감 난이도: P4

F번(업솔빙 중)

Idea 1) 답의 첫 번째 줄은 1, 2 또는 |w|만 가능하다.
w가 하나의 문자로만 이루어진 경우, w가 good string인 경우, 그렇지 않은 경우로 나눌 수 있습니다.
w가 하나의 문자로만 이루어지지도 않았으면서 good string인 경우만 빼고 나머지는 자명합니다.

여기서 더 나아가지는 못했습니다. 대회 종료 2분 전에 KMP를 잘 쓰면 풀릴 것 같다는 발상을 했는데, 어떻게 써야 잘 썼다고 소문이 날지는 아직 모르겠습니다.
오늘 더 파 보다가 정 모르겠으면 이미 푼 사람들에게 풀이 또는 힌트를 공유받을 것 같습니다.

못 푼 F번을 제외하더라도, D번은 구현에서 심하게 말릴 건덕지가 없었는데, 3틀과 8분이라는 시간을 손해 봤습니다.
구현을 어떻게 할지를 잘 정리해두고 키보드를 잡도록 해야겠습니다.

셋 이후

원래 계획은 월요일 앳코더, 수요일 코포 / 화,목 업솔빙이었습니다.
하지만 목요일이 공휴일이라는 점을 발상해서 월 앳코더, 화 코포, 수 업솔빙, 목 코포+업솔빙으로 계획을 바꿨습니다.
화요일 저녁에 위에서 언급한 코포 버추얼을 시작했습니다.

A번(00:01 AC)

언제나 그랬듯이 A번은 단순 구현 문제였습니다.
풀이는 쓰지 않겠습니다.

체감 난이도: B3

B번(00:09 AC)

1~2n까지 각 수가 몇 번씩 등장하는지를 "c"라는 배열에 정리하겠습니다. ex) c[1]은 1이 입력으로 주어진 배열 a에 등장한 횟수입니다.
세 가지 경우가 있습니다.
1) c[i] = 2k+1
p에 k개를 넣고 q에 k+1개를 넣을 수도 있고, 그 반대도 가능합니다.
f(p) + f(q)의 값은 1 증가하지만, p의 길이와 q의 길이는 1만큼 차이가 벌어집니다.
2) c[i] = 4k
p에 2k-1개, q에 2k+1개를 넣을 수 있습니다.
f(p) + f(q)의 값은 2 증가하지만, p의 길이와 q의 길이는 2만큼 차이가 벌어집니다.
3) c[i] = 4k+2
p와 q 모두에 2k+1개를 넣을 수 있습니다.
f(p)와 f(q)의 값은 2 증가하고, p의 길이와 q의 길이는 차이가 벌어지지 않습니다.

1~2n까지를 고려한 후 p의 길이와 q의 길이는 같아야 합니다.
2번째 경우가 홀수 번 등장하면서 1번째 경우가 등장하지 않는다면 f(p) + f(q)의 값이 "최대"일 때, p의 길이와 q의 길이가 2만큼 차이납니다.
즉 2번째 경우를 하나 제거함으로서 (q에 있는 i 하나를 p로 넘겨주는 방식으로) p와 q의 길이를 같게 해 줘야 합니다.
나머지 경우는 f(p) + f(q)의 값이 최대일 때 p와 q의 길이가 같게 만들 수 있습니다. 증명은 여기에 넣지 않겠습니다.

체감 난이도: G5

C번(00:29 AC)

k = 0인 경우 max S(i,j)를 S0, k = 1인 경우 max S(i,j)를 S1이라 하겠습니다.
Idea 1) k가 홀수인 경우 답은 S1이다.
proof) Alice가 하나를 고르고, Bob이 직전에 고른 인덱스를 고르면 max S(i,j)가 S1이 됩니다. 따라서 Alice는 Bob의 전략에 상관없이 S1을 만들 수 있습니다.
Bob이 항상 Alice가 직전에 고른 인덱스를 고른다면 k번째 턴 직전에 배열 상태는 변하지 않습니다. 따라서 max S(i,j)는 S1이고, Bob 또한 Alice의 전략에 상관없이 S1을 만들 수 있습니다.
Idea 2) k가 짝수인 경우 답은 S0이다.
proof) Bob이 S0을 만들 수 있음은 자명합니다.
Idea 1과 같은 방법으로 Alice가 최선의 전략을 사용하면 k=2인 경우로 줄어들 겁니다.
그러면 Alice가 S(i,j)가 max가 되는 i, j에 대해서 i<=k<=j인 k 중 b[k]가 최대인 k를 고르면 max S(i,j) >= S0이 됩니다.

S1을 어떻게 계산할 지 고민하다가, 그냥 구조체 세그(or 금광 세그)를 짜기로 했습니다.
에디토리얼에는 조금 더 고능하고 쉬운 구현이 올라와 있습니다.

체감 난이도: G3

D번(01:02 AC)

Idea 1) 임의의 길이가 n인 이진 문자열 s는 주어진 연산을 최대 n번 사용해서 모두 0인 문자열로 만들 수 있다.
s에 "00" 또는 "11"이 존재하면 (wlog 00이 존재한다고 합시다), 처음에 "00"을 선택하고, 이어서 연속되는 1을 모두 선택하고, 이어서 연속되는 0을 모두 선택하고... 를 반복하는 방식으로 가능합니다.
s에 "00"이나 "11"이 없으면, s는 "010101..." 꼴이거나 "101010..." 꼴입니다. 1~3번째를 뒤집으면 연속되는 0이나 1이 생깁니다. 위와 같은 방법으로 해 주면 됩니다.
Idea 2) 모두 0인 문자열에서 s를 만드는 과정은 s에서 모두 0인 문자열을 만드는 과정의 역순이다.
s -> 00...0 -> t가 되는 과정을 구하려면 s -> 00...0, t -> 00...0이 되는 과정을 구하고 후자를 역순으로 출력하면 됩니다.

체감 난이도: G3

E번은 문제 보고 던졌습니다.

F번(업솔빙 중)

Idea 1) m개의 수 a[1], a[2], ..., a[m]에 대해서 gcd(a[i], a[j])가 모두 다른 경우 m개의 수로 최대한 큰 n을 cover할 수 있다.
m-clique에서, 모든 점에 대해 self-edge가 하나씩 있는 그래프를 생각해 봅시다. 이 그래프에서 한붓그리기를 했을 때 방문할 수 있는 간선의 최댓값 + 1 까지의 n을 cover할 수 있습니다.
Idea 2) (2*3*5*7)^7 <= 10^18
즉, 2^0*3^7, 2^1*3^6, ..., 2^7*3^0과 5^0*7^7, ..., 5^7*7^0을 적당히 버무리면 총 64개의 수에서 임의의 2개를 골랐을 때 gcd가 모두 다르고 각 수는 10^18 이하입니다.
n <= 2000인 경우에는 커버할 수 있습니다.
수를 조금 더 고능하게 정하면 n <= 5000인 경우도 커버할 수 있지 않을까요?? 잘 모르겠습니다.
여기까지 1시간 정도 걸려서 발상했습니다.

위 아이디어들을 발상했으면 이제 오일러 투어만 짜면 되는데, 아직 짜진 않았습니다.

에디토리얼을 까 보니까 대충 아이디어는 맞는 것 같은데, 생각보다 구현이 복잡할 수도 있고 코포에서 찍혀 있는 문제 난이도도 F1 2600 / F2 3000이라 체감 난이도를 매기기 조심스럽습니다.
체감상 F1은 다이아까진 아닌 것 같습니다. F2는 플래인 것 같은데 다이아라면 D5일 것 같습니다.

셋 이후

확실히 주말에 비해서 퍼포먼스가 유의미하게 상승했습니다.
딥2긴 하지만 ABCD를 (TC1에서 WA 빼고는) 0틀로 모두 풀어냈고, 2300 퍼포를 띄웠습니다.
이번 겨울방학(~2026년 2월)까지는 계속 1주에 3번 이상 셋을 돌면서 지금처럼 퍼포먼스를 키워나가고 싶네요.
내일은 시간이 많은 만큼 5시간 셋을 돌아보고 싶습니다.

감사합니다.