AtCoder Beginner Contest 276

AtCoder Beginner Contest 276 - AtCoder

結果

A - Rightmost:AC(6:38)
B - Adjacency List:AC(21:50)
C - Previous Permutation:AC(29:53)
D - Divide by 2 or 3:WA

A - Rightmost

文字列$${S}$$が与えられ、その中で「a」が最後に現れるのが何文字目かを求める問題

自分の回答

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

  int a = S.rfind('a');
  if(a == string::npos){
    printf("-1\n");
  }
  else{
    printf("%d\n", a + 1);
  }
}

rfindで後ろから調べられるためそのまま

公式解説

省略

B - Adjacency List

$${1 \sim N}$$の番号が付けられた$${N}$$個の都市と、その都市を結ぶ道路が$${M}$$本与えられ、都市1から順番にいくつの都市と繋がっているかと、繋がっている都市の番号を昇順に出力する問題

自分の回答

int main(){
  int N, M;
  cin >> N >> M;
  vector<set<int>> city(N + 1, set<int>());

  for(int i = 0; i < M; i++){
    int A, B;
    cin >> A >> B;
    city[A].insert(B);
    city[B].insert(A);
  }
 
  for(int i = 1; i < N + 1; i++){
    printf("%d",city[i].size());
    for(int x : city[i]){
      printf(" %d", x);
    }
    printf("\n");
  }
}

setが重複無し、要素を昇順で記憶のためそれにどの都市と繋がっているかを入れていく
番号をわかりやすくするためにvectorの要素数はN+1にして0番を捨てる

公式解説

基本同じため省略

C - Previous Permutation

$${(1,2,3,…,N)}$$の数列を並べ替えた数列$${P=(P_{1},P_{2},P_{3},…,P_{N})}$$が与えられ、辞書順で$${P}$$の1つ前のものを求める問題

自分の回答

int main(){
  int N;
  cin >> N;
  vector<int> P(N);
  for(int i = 0; i < N; i++){
    cin >> P[i];
  }

  prev_permutation(P.begin(), P.end());
 
  for(int i = 0; i < N; i++){
    printf("%d", P[i]);

    if(i == N - 1){
      printf("\n");
    }
    else{
      printf(" ");
    }
  }
}

辞書順で次にするnext_permutationがあるからその逆もあるかと思って調べたらあったためそれを使って終わり
制約から1つ前があることは確定してるため条件分岐も不要

公式解説

int main() {
    int n;
    cin >> n;
    vector<int> p(n);
    for (int i = 0; i < n; ++i) {
        cin >> p[i];
    }
    int j = n - 2;
    while (p[j] < p[j + 1]) {
        j -= 1;
    }
    int k = n - 1;
    while (p[j] < p[k]) {
        k -= 1;
    }
    swap(p[j], p[k]);
    reverse(begin(p) + j + 1, end(p));
    for (int i = 0; i < n; ++i) {
        cout << p[i] << " \n"[i + 1 == n];
    }
    return 0;
}

https://atcoder.jp/contests/abc276/submissions/36025099より

prev_permutationを使わないやり方
$${P_{n}>P_{n+1} <…< P_{N}}$$となる場所と、$${n \sim N}$$の間で$${P_{n} < P_{m}}$$となる場所を探して$${P_{n}}$$と$${P_{m}}$$を入れ替え、$${n+1 \sim N}$$を逆順にするのか

なるほど

D - Divide by 2 or 3

正整数列$${A=(a_{1},a_{2},…,a_{N})}$$が与えられ、任意の値に対して割り切れる場合2か3で割る操作を任意の回数繰り返し、$${a_{1}=a_{2}=…=a_{N}}$$とすることが可能か、もし可能ならば最小何回の操作でできるかを求める問題

自分の回答

int main(){
  int N;
  cin >> N;
  vector<int> seq(N);
  for(int i = 0; i < N; i++){
    cin >> seq[i];
  }

  vector<int> index2(N), index3(N);
  for(int i = 0; i < N; i++){
    int count2 = 0, count3 = 0;
    while(seq[i] % 2 == 0){
      seq[i] /= 2;
      count2++;
    }
    index2[i] = count2;
    while(seq[i] % 3 == 0){
      seq[i] /= 3;
      count3++;
    }
    index3[i] = count3;
    if(i != 0){
      if(seq[0] != seq[i]){
        printf("-1\n");
        return 0;
      }
    }
  }

  sort(index2.begin(), index2.end());
  sort(index3.begin(), index3.end());
 
  int ans = 0;
  for(int i = 1; i < N; i++){
    ans+=(index2[i] - index2[0]);
    ans+=(index3[i] - index3[0]);
  }
  printf("%d\n", ans);
}

時間内に細部を詰め切れず終了後にACできたもの
全ての要素を素因数分解するイメージ
まず全てを2と3で割れるだけ割って、それぞれ何回割ったかを記録、それで残った値が全て一致したら可能、異なる値が1つでもあるなら不可能
後は2と3の指数でそれぞれ最小のものからの差の総和を取れば操作回数になる

公式解説

int main() {
    
	int N;
	cin>>N;
	
	vector<int> a(N);
	for(int i=0;i<N;i++){
		cin>>a[i];
	}
	
	int g = 0;
	for(int i=0;i<N;i++){
		g = gcd(g,a[i]);
	}
	
	int ans = 0;
	
	for(int i=0;i<N;i++){
		a[i] /= g;
		while(a[i]%2==0){
			a[i] /= 2;
			ans++;
		}
		while(a[i]%3==0){
			a[i] /= 3;
			ans++;
		}
		if(a[i]!=1){
			cout<<-1<<endl;
			return 0;
		}
	}
	
	cout<<ans<<endl;
	
	return 0;
}

https://atcoder.jp/contests/abc276/editorial/5167より

基本的な考えは同じだけど、全ての値の最大公約数を求めればそれが目標値になって、それで割れば後の操作が全ての値を2と3で割った回数をそのままカウントすればよくなって、割った後の値が1でなければ不可能と判定できるのか

なるほど