ABC404の振り返り

Bあかん
見出しにて問題のリンクが見えない人(少なくとも自分)は、見出しにカーソルおいてみてください、何か出てきます直ったっぽいです

A問題(diff:24)

404だしNot Found来るとは思った
$c_i$ を、文字 $i$ が $S$ に含まれていないかのフラグとします。$c_i = true$ である $i$ をどれか一つ出力すればOKです。僕は辞書順最小である一文字を出力することにしました。
計算量は文字の種類数を $\alpha$ として $O(S + \alpha)$ です。
ACコード(pypy56ms,C++1ms)

S = input()
c = [1] * 26
for i in range(len(S)):
  c[ord(S[i]) - 97] = 0
for i in range(26):
  if c[i]:
    print(chr(i + 97))
    break

AC時間:2:17

B問題(diff:181)

安定のグリッド弱者
回転操作自体をするのは面倒なので、回転操作をした時にあるマスがどこに行っているのかを考えます。
具体的には

• 0回回転:$i, j → i, j$
• 1回回転:$i, j → N - j + 1, i$
• 2回回転:$i, j → N - i + 1, N - j + 1$
• 3回回転:$i, j → j, N - i + 1$
  この4つに関して、(回転の回数) $+$ (回転した上での $S_{i, j} \neq T_{i, j}$ であるような $(i, j)$ の個数($S$ に上記の変換を行えばよい))の最小値が答えになります。
  計算量は $O(N ^ 2)$ です。
  実装に関して、0_indexedの時はちょっと変わります。気を付けましょう。
  ACコード(1ms)

#include <bits/stdc++.h>
using namespace std;

int main() {
  int N;
  cin >> N;
  vector<string> S(N), T(N);
  for(auto &o : S) {
    cin >> o;
  }
  for(auto &o : T) {
    cin >> o;
  }
  int ans = (int)2e4, cnt = 0;
  for(int i = 0; i < N; i++) {
    for(int j = 0; j < N; j++) {
      cnt += (S[i][j] != T[i][j]);
    }
  }
  ans = min(ans, cnt), cnt = 1;
  for(int i = 0; i < N; i++) {
    for(int j = 0; j < N; j++) {
      cnt += (S[N - j - 1][i] != T[i][j]);
    }
  }
  ans = min(ans, cnt), cnt = 2;
  for(int i = 0; i < N; i++) {
    for(int j = 0; j < N; j++) {
      cnt += (S[N - i - 1][N - j - 1] != T[i][j]);
    }
  }
  ans = min(ans, cnt), cnt = 3;
  for(int i = 0; i < N; i++) {
    for(int j = 0; j < N; j++) {
      cnt += (S[j][N - i - 1] != T[i][j]);
    }
  }
  ans = min(ans, cnt), cnt = 0;
  cout << ans << endl;
}

AC時間:1:03:36(えぇ…)

C問題(diff:371)

Bと並列で考えたけどやっぱりCは典型多いから簡単だなぁ!(1ペナ)
全ての頂点において次数が $2$ であり、グラフ全体が連結であればYes、そうでなければNoです。サイクルグラフの条件を言い換えると「長さ $N$ のサイクルがあり、それ以外の辺が存在しない」となります。まず、長さ $N$ のサイクルができるには、$N$ 個の頂点全てが連結である必要があります。また、サイクルだけができるには全ての頂点において次数が $2$ である必要があります。
また詳しく証明できたら記事書くかもです。
解法としては、各頂点の次数をカウントし、$2$ であるか調べ、グラフ全体が連結であるかはUnionFindで調べることができます。
計算量は $O((N + M)\alpha(N))$ です。
ACコード(77ms,77ms)

//自作UnionFind
#include <bits/stdc++.h>
using namespace std;
struct UnionFind {
  vector<int> par, rank;
  
  UnionFind(int N) {
    par.assign(N + 1, 0), rank.assign(N + 1, 0);
  }
  
  int root(int x) {
    if(par[x] == 0) {
      return x;
    }
    return par[x] = root(par[x]);
  }
  
  int unite(int x, int y) {
    int rx = root(x), ry = root(y);
    if(rx != ry) {
      if(rank[rx] > rank[ry]) {
        swap(rx, ry);
      }
      par[rx] = ry, rank[ry] += (rank[rx] == rank[ry]), rank[rx] = 0;
    }
    return ry;
  }
  
  bool same(int x, int y) {
    return root(x) == root(y);
  }
};
//library end

int main() {
  int N, M;
  cin >> N >> M;
  vector<int> cnt(N + 1, 0);
  UnionFind uf(N);
  for(int i = 0; i < M; i++) {
    int A, B;
    cin >> A >> B, cnt[A]++, cnt[B]++, uf.unite(A, B);
  }
  for(int i = 1; i <= N; i++) {
    if(cnt[i] != 2 || !uf.same(1, i)) {
      cout << "No" << endl;
      return 0;
    }
  }
  cout << "Yes" << endl;
}

//ACL
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;

int main() {
  int N, M;
  cin >> N >> M;
  vector<int> cnt(N, 0);
  atcoder::dsu uf(N);
  for(int i = 0; i < M; i++) {
    int A, B;
    cin >> A >> B, A--, B--, cnt[A]++, cnt[B]++, uf.merge(A, B);
  }
  for(int i = 0; i < N; i++) {
    if(cnt[i] != 2 || !uf.same(0, i)) {
      cout << "No" << endl;
      return 0;
    }
  }
  cout << "Yes" << endl;
}

AC時間:8:09

D問題(diff:803)

Bで詰まってなかったら行けましたね…(あと3Byte修正するだけ)
3パターン(その動物園に行かない、1回行く、2回行く)についてだけ考えればいいので、それを $N$ 園の動物園各々に関して調べていけば良いことが分かります。bit全探索は2パターンでしたが、それを3パターンにすることでできます。計算量は $O(3 ^ N(M + \sum_{i = 1}^M K_i))$ となります。総和の部分を上から抑えることで $O(3 ^ NNM)$ になります。
3パターンをN乗の例題
ACコード(31ms)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
//library end

int main() {
  int N, M;
  cin >> N >> M;
  vector<ll> C(N), cnt(M + 1, 0);
  for(ll &o : C) {
    cin >> o;
  }
  vector<vector<int>> A(N + 1, vector<int>(0, 0));
  for(int i = 1; i <= M; i++) {
    int K;
    cin >> K;
    for(int j = 0; j < K; j++) {
      int a;
      cin >> a, A[a].push_back(i);
    }
  }
  ll ans = (ll)2e18;
  for(int i = 0; i < POW(3, N); i++) {
    ll tmp = 0, f = 1;
    for(int j = 0; j < N; j++) {
      int b = i / POW(3, j) % 3;
      for(int o : A[j + 1]) {
        cnt[o] += b;
      }
      tmp += C[j] * b;
    }
    for(int j = 1; j <= M; j++) {
      f = f & (cnt[j] > 1);
    }
    if(f) {
      ans = min(ans, tmp);
    }
    cnt.assign(M + 1, 0);
  }
  cout << ans << endl;
}

感想

こwれwはwひwどwいw(パフォ614、レート745)
どのようなジャンルにも対応できるようになりたいです。