東京海上日動プログラミングコンテスト2023（AtCoder Beginner Contest 304）

東京海上日動プログラミングコンテスト2023（AtCoder Beginner Contest 304）

---

A. First Player

A. First Player

가장 age가 작은 사람으로 rotate 시켜서 순서대로 출력해주면 된다.

B. Subscribers

B. Subscribers

$N < 10^3$ 이라면 그냥 출력하고 아니면 앞에 세 글자만 보고 뒤에는 $0$을 붙여서 출력한다.

C. Virus (365)

C. Virus

$O(n^2)$로 도달되지 않는 것을 가린다.

D. A Piece of Cake (1015)

D. A Piece of Cake

각 $(p_i, q_i)$ 를 $A, B$ 들의 구간에 어디에 들어갈지 이분 탐색으로 찾은 다음에 모든 구간을 데이터가 있는 곳만 $O(n \log n)$ 으로 탐색해줄 수 있다.

귀찮아서 세그먼트 트리로 풀었다.

E. Good Graph (971)

E. Good Graph

처음에 간선들을 DSU로 이어서 $x_i, y_i$가 같은 컴포넌트에 있는게 있다면 불가능하다.

그렇지 않다면 $p_i, q_i$ 가 쿼리로 들어왔을 때 $p_i, q_i$ 의 컴포넌트끼리 이어지게 되는 것인데, 그럼 두 컴포넌트 사이에 $(x_i, y_i)$ 쌍이 있는지 set 같은걸로 확인한다.

컴포넌트를 나타내는 노드 번호는 DSU에서 각 트리의 루트 번호로 다루면 쉽다.

struct DSU {
   vector<int> p;
   DSU(int n) : p(n, -1) {}
   int gp(int n) {
      if (p[n] < 0) return n;
      return p[n] = gp(p[n]);
   }
   void merge(int a, int b, int to_b = 0) {
      a = gp(a), b = gp(b);
      if (a == b) return;
      if (!to_b && size(a) > size(b)) swap(a, b);
      p[b] += p[a];
      p[a] = b;
   }
   bool is_merged(int a, int b) { return gp(a) == gp(b); }
   int size(int n) { return -p[gp(n)]; }
};
void solve() {
   int n, m, k, q;
   cin >> n >> m;
   DSU dsu(n);
   vvi edges(n);
   for (int i = 0, u, v; i < m; i++) {
      cin >> u >> v, u--, v--, edges[u].pb(v), edges[v].pb(u);
      dsu.merge(u, v);
   }
   cin >> k;
   vector<pi> xy(k);
   for (auto &[x, y]: xy) cin >> x >> y, x--, y--;
   cin >> q;
   // p, q 를 이어도 모든 xy에 대해 여전히 떨어져있을 수 있는가?
   // 처음에 xy 중 붙어있는게있으면 불가능하다.
   // 처음에는 모두 컴포넌트로 분리되어 있을 것이다.
   // p가 속한 컴포넌트와 q가 속한 컴포넌트가 이어졌을 때, 어떤 x[i], y[i]가 존재해 하나는 P에 하나는 Q에 있지 않으면 된다.
   // 컴포넌트별로 번호를 붙이고 (c1, c2) 같은 쌍들을 모두 모은다.
 
   int ok = 1;
   for (int i = 0; i < k; i++) {
      if (dsu.is_merged(xy[i].fi, xy[i].se)) ok = 0;
   }
 
   vector<set<int>> have(n);
   for (auto &[x, y]: xy) {
      x = dsu.gp(x);
      y = dsu.gp(y);
      have[x].insert(y);
      have[y].insert(x);
   }
 
   while (q--) {
      int p, q;
      cin >> p >> q, p--, q--;
      if (!ok) {
         cout << "No\n";
         continue;
      }
      if (dsu.is_merged(p, q)) {
         cout << "Yes\n";
         continue;
      }
      p = dsu.gp(p);
      q = dsu.gp(q);
      if (hass(have[p], q)) cout << "No\n";
      else cout << "Yes\n";
   }
}
 

F. Shift Table (1619)

F. Shift Table

길이 $N$의 진약수 $M$ 들을 채워넣으면 항상 $M$길이의 주기를 이룬다.

$N$의 약수는 그리 많지 않으므로 $O(N \cdot N\text{의 약수 개수})$ 의 시간복잡도로 풀 수 있다는 감을 잡아야한다.

일단 어떤 $M$이 주어졌을 때 가능한 것의 개수를 셀 수 있다.

$S$에서 $M$ 개의 위치 중 꼭 출근을 해야하는 날의 개수를 센다. 이것을 $P$ 라 하자.

그렇지 않아도 상관없는 $M-P$ 개의 날이 있으므로 경우의 수는 $2^{M-P}$ 이다.

그런데 이걸 모두 더해주면 중복된 정답이 생긴다.

그럼 항상 $M$ 길이의 주기가 가장 최소 주기가 되는 것의 개수만 세야한다.

왜냐면 $M=8$에서 앞에 네개와 뒤에 네개가 같아 주기가 $4$ 라면, 그건 $M=4$ 를 볼 때도 처리가 될 것이기 때문이다.

이 때, 최소 주기만 구하는 방법은 DP를 쓰는 것이다.

위의 예시처럼 $M=8$ 라면 최소주기의 개수가 $1,2,4$ 인 것을 모두 $2^{M-P}$ 에서 빼줘야 오롯이 $M$이 최소주기인 것의 개수가 나온다.

즉, $T_M$을 길이 $M$이 최소주기인 것의 개수라고 하면

$\displaystyle T_M= 2^{M-P} \sum_{i \mid M} T_i$ 가 된다.

$M$의 약수 또한 많지 않으므로 그냥 처리해주면 된다.

bitset<MAX + 1> tmp;
int two[MAX + 1];
void solve() {
   sieve();
   two[0] = 1;
   for (int i = 1; i <= MAX; i++) two[i] = md(two[i - 1] * 2);
   int N;
   string S;
   cin >> N >> S;
   vi idx;
 
   for (int i = 0; i < N; i++)
      if (S[i] == '.') idx.pb(i);
   ll ans = 0;
 
   vi dp(N + 1);
   for (int M = 1; M < N; M++)
      if (N % M == 0) {
         tmp.reset();
         for (int i: idx) tmp[i % M] = 1;
         ll t = two[M - tmp.count()];
         dp[M] = t;
         for (int d = 1; d < M; d++) {
            if (M % d == 0) {
               dp[M] = md(dp[M] - dp[d]);
            }
         }
         ans = md(ans + dp[M]);
      }
   cout << ans;
}

G. Max of Medians (3177)

G. Max of Medians

Ex. Constrained Topological Sort (2642)

Ex. Constrained Topological Sort