AtCoder Beginner Contest 288

2023年2月13日 13:38

結果

A - Many A+B Problems:AC(2:04)
B - Qualification Contest:AC(4:49)
C - Don’t be cycle:AC(40:11)
D - Range Add Query:WA

A - Many A+B Problems

$${N}$$個の整数2つの組$${(A_{1},B_{1}),(A_{2},B_{2}),…,(A_{N},B_{N})}$$が与えられ、$${A_{i}+B_{i}}$$を求める問題

自分の回答

int main(){
  int N;
  cin >> N;
  int a, b;
  for(int i = 0; i < N; i++){
    cin >> a >> b;
    printf("%d\n", a + b);
  }
}

そのまま

公式解説

省略

B - Qualification Contest

$${N}$$人の人がコンテストに参加し、名前が順位順に与えられる
上位$${K}$$人の名前を辞書順に出力する問題

自分の回答

int main(){
  int N, K;
  cin >> N >> K;
  vector<string> S;
  string s;
  for(int i = 0; i < K; i++){
    cin >> s;
    S.push_back(s);
  }

  sort(S.begin(), S.end());

  for(string s : S){
    printf("%s\n", s.c_str());
  }
}

文字列のソートが辞書順なためソートして終わり

公式解説

省略

C - Don’t be cycle

$${N}$$頂点$${M}$$辺の単純無向グラフが与えられ、そのグラフが閉路を持たないようにするには最低何本の辺を削除すればいいか求める問題

自分の回答

int main(){
  int N, M;
  cin >> N >> M;
  vector<vector<int>> G(N + 1);
  int a, b;
  for(int i = 0; i < M; i++){
    cin >> a >> b;
    G[a].push_back(b);
    G[b].push_back(a);
  }

  queue<pair<int,int>> bfs;
  vector<bool> check(N + 1, false);
  int ans = 0;
  for(int i = 1; i <= N; i++){
    if(check[i]){
      continue;
    }

    bfs.push({i, 0});
    check[i] = true;
    while(!bfs.empty()){
      pair<int, int> now = bfs.front();
      bfs.pop();
      for(int x : G[now.first]){
        if(check[x]){
          if(x != now.second){
            ans++;
          }
          continue;
        }
        check[x] = true;
        bfs.push({x, now.first});
      }
    }
  }
  printf("%d\n", ans / 2);
}

閉路がある=一度踏んだ頂点をもう一度踏む、なため
幅優先探索にどの頂点から来たかの情報を追加してその頂点以外で探索済みの頂点があったらカウント、両方の頂点でカウントされるため最後にそれを2で割って終わり

今思えば深さ優先探索の方がきれいにできるかなぁ

公式解説

int main() {
	int n, m;
	cin >> n >> m;
	vector<vector<int>> graph(n, vector<int>());
	for (int i = 0; i < m; i++) {
		int u, v;
		cin >> u >> v;
		u--; v--;
		graph[u].push_back(v);
		graph[v].push_back(u);
	}
	vector<bool> used(n);
	int s = 0;
	for (int i = 0; i < n; i++) {
		if (!used[i]) {
			s++;
			queue<int> que;
			que.push(i);
			while (!que.empty()) {
				int q = que.front(); que.pop();
				for (int v : graph[q]) {
					if (!used[v]) {
						used[v] = true;
						que.push(v);
					}
				}
			}
		}
	}
	cout << m - n + s << '\n';
}

https://atcoder.jp/contests/abc288/editorial/5662より

削除する辺の本数ではなくて残せる辺の数を考える
$${n}$$頂点のグラフを頂点全て閉路なく繋ぐと辺の数は$${n-1}$$本、そのため連結成分が$${S}$$個、各連結成分の頂点数が$${X_{1},X_{2},…,X_{S}}$$とするとその辺の総和は$${\displaystyle\sum_{i=1}^{S}(X_{i}-1)}$$、また頂点数$${N}$$は$${\displaystyle\sum_{i=1}^{S}X_{i}}$$なため$${N-S}$$が連結成分が$${S}$$のとき引かれる辺の数
よって幅優先探索で連結成分を求めて$${M-(N-S)}$$

なるほど

公式解説おまけ

int main() {
	int n, m;
	cin >> n >> m;
	dsu d(n);
	int ans = 0;
	for (int i = 0; i < m; i++) {
		int u, v;
		cin >> u >> v;
		u--; v--;
		if (d.same(u, v)) ans++;
		d.merge(u, v);
	}
	cout << ans << '\n';
}

dsuがn頂点0辺のグラフを作成
sameが頂点u,vが連結のときtrueを返す
margeが頂点u,vに辺を繋げる

ACL便利だなぁ

D - Range Add Query

長さ$${N}$$の整数列$${A=(A_{1},A_{2},…,A_{N})}$$が与えられ、$${A}$$の$${l_{i}}$$番目から$${r_{i}}$$番目までを取り出した数列を$${X}$$とする
$${X}$$の任意の位置の連続する$${K}$$個の要素に任意の整数$${c}$$を足す操作を好きな回数行い全ての要素を0にすることができるとき$${X}$$を「いい数列」と呼ぶ
全ての$${l_{i},r_{i}}$$に対してその数列が良い数列かを判定する問題

自分の回答

操作の順番は関係ないから先頭から0にしていくように操作する方法で書いてみたがTLE
駄目だろうなとは思ってたけどサンプルと1しか通らないのは流石に想定外だった

項の差に規則性が見えたからそのあたり何かAの時点でできるのかなと思ったり

公式解説

#define rep(i, x) for(int i = 0; i < (x); i++)

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    rep(i, n) cin >> a[i];
    vector<vector<long long>> cum(k, vector<long long>(n + 1));
    rep(j, k) {
        rep(i, n) {
            cum[j][i + 1] = cum[j][i] + (i % k == j ? a[i] : 0);
        }
    }
    auto get = [&](int j, int l, int r) {
        return cum[j][r] - cum[j][l];
    };
    int q;
    cin >> q;
    while(q--) {
        int l, r;
        cin >> l >> r, --l;
        bool same = 1;
        long long val = get(0, l, r);
        for(int j = 1; j < k; j++) {
            same &= val == get(j, l, r);
        }
        cout << (same ? "Yes" : "No") << endl;
    }
}

https://atcoder.jp/contests/abc288/editorial/5664より

まずXが良い数列であるためには$${i (mod \space K)}$$が同じ$${X_{i}}$$の総和がすべて等しい必要があり、これが必要条件でもある
そのためAの時点で分けて累積和を求めておき、l,rに応じて総和が全て等しいかを調べる

この理解で合ってるのかな
D問題ってこんなに難しかったっけ

この記事が気に入ったらサポートをしてみませんか？