오늘의 PS (4) - 220423

앳코더와 코드포스 글로벌 라운드가 있었다.

 

AtCoder Beginner Contest 249

 

A. Jogging (0:05, +) *103

지문이 이상하게 쓰여 있어서 좀 헤멨다. 문제 자체도 평소 ABC A보다 어려웠다.

 

B. Perfect String (0:07, +) *47

하라는대로 하면 된다.

 

C. Just K (0:11, +) *528

이것도 지문이 조금 불친절하긴 했는데, 하라는 대로 완전탐색을 돌려주면 맞는다.

 

D. Index Trio (0:30, +2) *983

인덱스가 같을 수도 있어서 식을 좀 생각해서 써주어야 한다. 예제가 앳코더답지 않게 불친절해서 많이들 틀리는 것으로 보였다.

 

E. RLE (1:00, +) *1970

\(DP[i][j]\)를 i번째 글자까지 쓰고, 압축 길이가 j인 경우로 정의하면 압축 문자열의 한 덩어리는 최대 5글자이기 때문에 \(O(10N^2)\) 정도에 문제를 해결할 수 있다.

 

F. Ignore Operation (1:13) *1786

한 1번 연산이 결과에 적용되려면, 다음에 오는 1번 연산은 모두 무시해야 한다. 따라서 연산을 뒤에서부터 보면서 잘 관리해주면 된다. 가중치가 음수일 수도 있어서 음수 가중치 중 작은 것들을 무시해주어야 하는데, 이는 PQ로 처리할 수 있다.

 

Codeforces Global Round 20

A. Log Chopping (0:02, +)

\(S-N\)의 홀짝성을 판별하면 된다. 2분에 풀 문제는 아니었는데, 긴장 때문인지 손이 꼬였다.

 

B. I love AAAB (0:07, +)

앞에서부터 보았을 때 항상 A의 개수>B의 개수여야 하며, 마지막 글자는 항상 B여야 한다.

 

C. Unequal Array (0:36, +5)

여기서부터 망했다. 될거같은 풀이를 다 제출했기 때문에 풀이가 잘 기억은 나지 않지만, 그리디하게 잘 바꿔주면 되는 것 같다.

 

D. Cyclic Rotation (1:00, +1)

앞에서부터 보면서 같으면 체크하고, 다르면 set등에 넣어서 나중에 잘 나와주는지 확인하면 된다.

 

F1. Array Shuffling (2:09, +6)

망한 원인 2. Constructive 문제인데, 제대로 나오는지 확인하지도 않고 그냥 막 내서 1250점짜리 문제에서 470점을 받는 기염을 토했다.

 

E. notepad.exe (-1)

1이 나오는 최소 길이 \(L\)을 찾아준 후 \(L/i\)꼴에 대해 쿼리를 날려주면 된다. 이분탐색을 한번 하면 \(n+22\)정도의 쿼리를 사용하는 것 같은데, 나는 쓸데없이 두 번 해서 \(n+33\)번 썼다고 틀렸다. 진짜 한심하다.

 

그냥 이상한 습관이 다 나온 것 같다. 쉬운 직관 문제 빠르게 못풀고, 검토 안하고 막 내고, 심지어는 풀이가 틀렸는데도 그냥 내서 시스텟까지 당했다. 원래 글로벌 라운드만 치면 망한다+오렌지에서 오른적이 없다라는 징크스를 가지고 있었어서 과정과 별개로 E 맞은 버전의 퍼포먼스 자체는 나름 만족스러웠는데.. 망해버렸다. 오렌지 갈때마다 광속퇴근하는걸 보면 오렌지 실력은 아닌 것 같다.

 

내일은 ARC + 코드잼 1B가 있다. 또 이상한짓 하면 어떡하지?