Contest - 2023 부산대학교 CodeRace Open Contest

대회 링크

간만에 백준에서 열리는 대회에 참여했고, 올솔로 5등을 했다.

대회를 밥먹고와서 풀어서 패널티는 망해있다.

난이도는 대략 다음과 같이 집계되었다.

보통 난이도를 까고 풀기때문에 난이도가 없으면 체감상 좀 더 어려운데, 실제로 대회에서 체감했던 것보다 한단계씩 난이도가 낮다.

A 첨탑 밀어서 부수기

단순히 $a_{i+1} \ge a_i$ 인 것의 개수를 세면 된다.

B 영역 색칠

문제를 잘못읽어서 산을 깎는 것처럼 세는 그리디문제인줄 알았는데, 그냥 하나의 행에서 이어진 구간을 기준으로 $1$로 나뉘어진 부분과 $2$로 나뉘어진 부분을 세서 어떤 색을 처음으로 다 칠하고 나머지 색을 부분 부분 칠해줄지를 결정해주는 그리디 문제이다,

void solve() {
   int Y, X;
   cin >> Y >> X;
   vvi b(Y, vi(X));
   fv2(b);

   auto calc = [&](int y, int l, int r) -> int {
      int ret = b[y][l];
      debug(y, l, r);
      int seg1 = b[y][l] == 1, seg2 = b[y][l] == 2;
      for (int i = l + 1; i <= r; i++) {
         if (b[y][i] != b[y][i - 1]) {
            if (b[y][i] == 1) seg1++;
            else seg2++;
         }
      }
      debug(seg1, seg2);
      if (seg1 == 0 || seg2 == 0) return 1;
      return 1 + min(seg1, seg2);
   };
   int ans = 0;
   for (int y = 0; y < Y; y++) {
      int sx = -1;
      for (int x = 0; x <= X; x++) {
         if (x == X || b[y][x] == 0) {
            if (sx != -1) ans += calc(y, sx, x - 1);
            sx = -1;
         } else {
            if (sx == -1) {
               sx = x;
            }
         }
      }
   }
   cout << ans;
}

C 경품 추첨

$D, E$가 많이 풀려있어서 $C$를 스킵하려했는데 그냥 $C$부터 풀고 진행했다.

처음엔 삽질을 많이했고 당황했는데, 생각해보니 다음과 같이 풀 수 있었다.

$dp[y][x][k]$를 $(y,x)$까지 내려오는데 $k$번 두 번으로 나뉘어진 개수라고 하자.

이건 $O(N^2M)$으로 모두 구할 수 있고,

이제 $y=N-1$ 부분의 모든 $x$에 대해 이진수처럼 왼쪽으로 밀기를 반복하면 결국 어떤 곳에 가장 올 확률이 높은지 정수만 써서 계산할 수 있다.

예상대로 골드2 라는 티어가 잡혔다.

D 게임을 클리어하자

단순히 $dp[i][p]$ 를 이전에 $p$를 썼을 때 끝까지 진행하는데 최소 값이라고 할 때, $O(NM^2)$ 으로 구해줄 수 있다.

E 시간이 겹칠까?

iMos 법으로 쉽게 구할 수 있고, 구간합 배열 문제라서 세그먼트 트리가 필요없어 난이도는 높게 책정되지 않았다.

F 산지니의 여행계획

지문해석에 난항을 겪어 쓸데없이 시간을 많이썼는데, 단순히 Max MST를 구성한다음 DFS를 통해 $s$에서 이동할 때, 가장 긴 경로를 하나 빼주면 된다.

G Attention

세그먼트 트리임은 자명해보였고, 좀더 꼬아생각해서 최고의학생 정도의 기법인줄 알았으나 그건 아니였다.

$b$에 대해 순회하며 $b[i]$가 $a$에서 있는 위치를 $j$라고 할 때, 지금까지 거쳐온 $i$들에 대해서는 $a$애서 모두 체크가 되어있는 상태이므로

현재 $i$에 대해 $b[i]$ 가$a$ 에 있는 위치 $j$ 미만의 것의 합을 세그먼트 트리로 구하면 $i$에서 문제에서 요구하는 길이 $2$인 쌍 중 $b[i]$ 로 끝나는 쌍의 개수를 구할 수 있다.

이 과정을 한 번 더 하면 길이 $3$에 대해서 구성이 가능하다.