AtCoder Beginner Contest 292

OKU

結果

A - CAPS LOCK:AC(1:23)
B - Yellow and Red Card:AC(5:26)
C - Four Variables:AC(28:20)
D - Unicyclic Components:AC(70:40)(2ペナ)
E - Transitivity:提出無し

A - CAPS LOCK

英小文字のみからなる文字列$${S}$$が与えられるため、全て英大文字にする問題

自分の回答

int main(){
  string S;
  cin >> S;

  for(char c : S){
    printf("%c", c - 32);
  }
  printf("\n");
}

そのまま

公式解説

省略

B - Yellow and Red Card

$${1}$$から$${N}$$までの番号がついた$${N}$$人の選手がサッカーの試合をし、選手が反則をした際にはイエローカードかレッドカードが提示され、イエローカードを累計2枚、もしくはレッドカードを提示された選手は退場処分となる
$${Q}$$個のイベントが与えられるため、それを全て処理する問題
イベントは以下の3種類のうちいずれか1つ
・「1 x」選手xにイエローカードを提示
・「2 x」選手xにレッドカードを提示
・「3 x」選手xが退場処分を受けているならば「Yes」を、受けていないならば「No」を出力

自分の回答

int main(){
  int N, Q;
  cin >> N >> Q;

  vector<int> P(N + 1, 0);
  int ope, x;
  for(int i = 0; i < Q; i++){
    cin >> ope >> x;
    if(ope == 1){
      P[x]++;
    }
    else if(ope == 2){
      P[x] += 2;
    }
    else{
      printf(P[x] >= 2 ? "Yes\n" : "No\n");
    }
  }
}

イエローを1、レッドを2として2以上なら退場と判定

公式解説

省略

C - Four Variables

正整数$${N}$$が与えられ、正整数の組$${(A,B,C,D)}$$であって$${AB+CD=N}$$を満たすものの数を求める問題

自分の回答

int main(){
  int N;
  cin >> N;

  int64_t ans = 0;
  for(int i = 1; i < N; i++){
    for(int j = 1; j * j <= i; j++){
      int a, b;
      if(i % j == 0){
        a = j;
        b = i / j;

        for(int k = 1; k * k <= N - i; k++){
          int c, d;
          if((N - i) % k == 0){
            c = k;
            d = (N - i) / k;

            if(a != b && c != d){
              ans += 4;
            }
            else if(a == b && c == d){
              ans++;
            }
            else{
              ans += 2;
            }
          }
        }
      }
    }
  }

  printf("%ld\n", ans);
}

まずABとCDをそれぞれ塊で見ればAB=1~N-1のN-1通り存在し、CD=N-ABなためCDも1つに定まる
そこから1から平方根まで順にAB,CDの約数であるかを確認し共に約数であるならa,b,c,d,として、求め方から同じ組み合わせは現れないためa,b,c,d,での並び方の数を求めて足していく
計算量は$${N\sqrt{N}}$$でいいのかな

公式解説

int main() {
    
	int N;
	cin>>N;
	
	long long ans = 0;
	
	for(int i=1;i<N;i++){
		int X = i,Y = N-i;
		long long x = 0,y = 0;
		for(int j=1;j*j<=X;j++){
			if(X%j==0){
				x++;
				if(X!=j*j)x++;
			}
		}
		for(int j=1;j*j<=Y;j++){
			if(Y%j==0){
				y++;
				if(Y!=j*j)y++;
			}
		}
		ans += x * y;
	}
	
	cout<<ans<<endl;
	
	return 0;
}

https://atcoder.jp/contests/abc292/editorial/5872より

AとB、CとDが同じかの部分と並びの数の数え方そうすればいいのか

なるほど

D - Unicyclic Components

$${N}$$頂点$${M}$$辺の無向グラフが与えられ、連結成分全てにおいて頂点の数と辺の数が等しいかを判定する問題

自分の回答

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

  vector<bool> pass(N + 1, false);
  for(int i = 1; i <= N; i++){
    if(pass[i]){
      continue;
    }

    queue<int> bfs;
    bfs.push(i);
    pass[i] = true;
    int ver = 1, edge = G[i].size();
    while(!bfs.empty()){
      int now = bfs.front();
      bfs.pop();
      for(int x : G[now]){
        if(pass[x] == false){
          bfs.push(x);
          pass[x] = true;
          ver++;
          edge += G[x].size();
        }
      }
    }
    if(ver * 2 != edge){
      printf("No\n");
      return 0;
    }
  }
  printf("Yes\n");
}

最初は辺で通過済みかのチェックをするようにしたらTLE、考え直したら各頂点に繋がる辺の総和÷2=辺の数なことに気付いてその通りに書いたら通った

公式解説

int main() {
    
	int N,M;
	cin>>N>>M;
	vector<int> u(M),v(M);
	for(int i=0;i<M;i++){
		cin>>u[i]>>v[i];
		u[i]--,v[i]--;
	}
	
	dsu D(N);
	for(int i=0;i<M;i++){
		D.merge(u[i],v[i]);
	}
	
	vector<int> vs(N),es(N);
	for(int i=0;i<N;i++){
		vs[D.leader(i)]++;
	}
	
	for(int i=0;i<M;i++){
		es[D.leader(u[i])]++;
	}
	
	if(vs==es)cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
	
	return 0;
}

https://atcoder.jp/contests/abc292/editorial/5873より

ACLで使えるもの無いかなと調べてはみたもののいい方法は思いつかずあの回答になったが、頂点と辺の片方でそれぞれ代表元を返す関数を使ってどれに何個属するかを数えるのか

なるほど

E - Transitivity

$${N}$$頂点$${M}$$辺の単純有向グラフが与えられ、相異なる頂点$${a,b,c}$$すべてについてa→b、b→cの辺が共に存在するならばa→cの辺も存在する、とするには最小でいくつの辺を追加する必要があるかを求める問題

自分の回答

a,b,cを全パターン調べたらそれだけでTLEしそうな時点でお手上げ
探索する過程で何かするんだろうなとは思うが一切思いつかない

公式解説

int main() {
    
	int N,M;
	cin>>N>>M;
	vector<vector<int>> E(N);
	
	for(int i=0;i<M;i++){
		int u,v;
		cin>>u>>v;
		E[u-1].push_back(v-1);
	}
	
	int ans = 0;
	
	for(int i=0;i<N;i++){
		vector<bool> f(N,false);
		f[i] = true;
		queue<int> Q;
		Q.push(i);
		
		while(Q.size()>0){
			int x = Q.front();
			Q.pop();
			for(int j=0;j<E[x].size();j++){
				int y = E[x][j];
				if(f[y])continue;
				f[y] = true;
				Q.push(y);
				ans++;
			}
		}
	}
	
	ans -= M;
	cout<<ans<<endl;
	
	return 0;
}

https://atcoder.jp/contests/abc292/editorial/5874より

まず根本的な理屈として1→2→3→4→5というグラフを考えると1→2,2→3から1→3が作られるがそれにより1→3,3→4となるため1→4ができる…を繰り返すため作られる辺の数は初期状態で頂点iからの距離が2以上の頂点の数の総和である
しかしわざわざ距離を記録しなくても初期状態の辺の数=距離1の頂点の数なため全ての頂点を始点にして幅優先探索してそこから行ける頂点の数を調べてMを引く

なるほど


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