대회후기: Hello 2020

새해의 첫 대회이다.

구사과님의 출제로 오랜만에 코포에서 한글을 본다.

---

A: New Year and Naming

매우 한국적인 주제의 등장에 웃겼다. 연도가 주어지면 육십갑자를 출력하면 된다.

2분에 AC

---

B: New Year and Ascent Sequence

배열 $n$개가 들어온다. 이들 중 두개를 중복을 허용하여 골라 concatenate했을때, 연속된 두 숫자 중 증가하는 숫자가 있다면 이는 ascent sequence이다. (사실 ascent sequence의 조건은 $i<j$이면서 $a_i<a_j$인 $i$와 $j$가 존재하는 것인데, 모든 인접한 숫자가 감소한다면 앞의 조건을 만족하는 $i$, $j$쌍이 존재할 수 없으므로 대우 명제에 의해 인접한 두 수만 확인하면 된다.)

문제는 주어진 배열들을 앞의 설명처럼 concatenate했을 때, ascent sequence의 개수를 물어본다.

Ascent sequence가 subarray인 sequence는 당연히 ascent sequence이므로 입력 중 ascent가 존재하는 배열들은 따로 labelling해주고, 나머지 배열들은 시작값과 끝값만 기록해서 붙였을 때 경계에서 증가가 발생하는지 확인하면 되겠다는 생각이 들었다. 여기까지가 문제를 읽으면서 바로 든 생각이다.

주어진 배열 뒤에 증가가 발생하도록 붙일 수 있는 배열들의 수를 세는 것은 이진 탐색을 이용하면 된다. 이는 문제를 읽은 후 1분 이내에 든 생각이다.

하지만 ascent가 이미 존재하는 배열의 개수로부터 조합되는 배열의 수를 잘못 생각해 알고리즘/코드 디버깅을 하느라 시간을 좀 버렸다.

21분에 AC

---

C: New Year and Permutation

n-permutation마다 (크기 - 1) == (최대 - 최소)인 subarray의 개수를 다 더하면 된다.

n-permutation이란 [1, 2, ... , n]의 모든 permutation들을 뜻한다.

.......................................................

..................................

.....................

.............

........

.....

...

..

.

.

 

- 뇌정지 -

 

.

.
..
...
.....
........
.............
.....................
..................................
.......................................................

 

Subarray의 길이 기준으로 조건을 만족하는 subarray가 총 몇개 존재하는지 더해주면 된다. 계산 과정에 필요한 factorial값은 미리 계산해 배열에 저장해둔다.

재귀적 혹은 DP 비슷한 풀이를 생각하다가 한시간을 말아먹었다.

1시간 33분에 AC

---

D: New Year and Conference

Graph isomorphism을 low complexity로 판별하는 문제인 줄 알았다.

 

Segment tree with lazy propagation이라 카더라.

어림도 없지 (제출 안함)

---

총평

C에서 뇌정지가 와 30분동안 누워있지 않았다면 무난한 대회였겠지만 어림도 없었기 때문에 무난한 방어가 되었다.

대회만 뛰느라 공부할 틈이 없다. 대회 두번 중 한번은 그냥 공부하는 시간으로 쓸까?

 

레이팅 변화 1695 + 27 = 1722

My Performance: ★★☆☆☆