AtCoder Beginner Contest 333

OKU

結果

A - Three Threes : AC(1:33)
B - Pentagon : AC(13:47)
C - Repunit Trio : AC(24:43)
D - Erase Leaves : AC(57:57)
E - Takahashi Quest : AC(81:06)

A - Three Threes

$${1～9}$$の正整数$${N}$$が入力されるため、それを$${N}$$個繋げた文字列を出力する問題

自分の回答

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

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

そのまま

公式解説

省略

B - Pentagon

頂点を時計回りに$${A,B,C,D,E}$$と付けられた正五角形がある
これの点$${P_{1}}$$と点$${P_{2}}$$を結ぶ線分と点$${T_{1}}$$と点$${T_{2}}$$を結ぶ線分の長さが等しいか求める問題

自分の回答

int main(){
  char S1, S2, T1, T2;
  cin >> S1 >> S2 >> T1 >> T2;

  vector<pair<char, char>> E = {{'A','B'}, {'B','A'}, {'B','C'}, {'C','B'}, {'C','D'}, {'D','C'}, {'D','E'}, {'E','D'}, {'E','A'}, {'A','E'}};
  bool S = false, T = false;
  for(auto [p1, p2] : E){
    if(p1 == S1 && p2 == S2){
      S = true;
    }
    if(p1 == T1 && p2 == T2){
      T=true;
    }
  }

  if(S == T){
    printf("Yes\n");
  }
  else{
    printf("No\n");
  }
}

正五角形において対角線は全て長さが等しいため長さのパターンは辺と対角線の二通り
辺のリストを作ってそれと照合し両方とも辺であるか対角線であるならYes

もっときれいにできないもんかね

公式解説

int main() {
	char a, b, c, d;
	cin >> a >> b >> c >> d;
	auto near = [](char x, char y) {
		if(x > y) swap(x, y);
		return y - x == 1 or y - x == 4;
	};
	if(near(a, b) == near(c, d))
		cout << "Yes\n";
	else
		cout << "No\n";
}

https://atcoder.jp/contests/abc333/editorial/7978より

そうか引き算して絶対値が1か4かか

なるほど

C - Repunit Trio

レピュニット数$${3}$$つの和として表わせる数のうち小さい方から$${N}$$番目の数はいくつか求める問題

自分の回答

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

  int64_t R1 = 1, R2 = 1, R3 = 1;
  int i = 1;
  while(i < N){
    R3 *= 10;
    R3 += 1;
    if(R3 > R2){
      R3 = 1;
      R2 *= 10;
      R2 += 1;
    }
    if(R2 > R1){
      R2 = 1;
      R1 *= 10;
      R1 += 1;
    }
    i++;
  }

  printf("%ld\n", R1 + R2 + R3);
}

3つを区別しないためA>=B>=Cとして順番に見ていく

公式解説

省略

D - Erase Leaves

$${N}$$頂点からなる木が与えられ、辺はそれぞれ頂点$${u_{i}}$$と$${v_{i}}$$を結んでいる
葉である頂点とそれに繋がる辺を消す操作を繰り返し、頂点$${1}$$を消すには最低何回の操作が必要か求める問題

自分の回答

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

  vector<int> R;
  vector<bool> seen(N + 1, false);
  seen[1] = true;
  for(int r : G[1]){
    queue<int> bfs;
    bfs.push(r);
    seen[r] = true;
    int sum = 1;
    while(!bfs.empty()){
      int n = bfs.front();
      bfs.pop();
      for(int g : G[n]){
        if(seen[g]){
          continue;
        }
        bfs.push(g);
        seen[g] = true;
        sum++;
      }
    }
    R.push_back(sum);
  }
  sort(R.begin(), R.end());

  printf("%d\n", N - R[R.size() - 1]);
}

頂点1に繋がる辺が1つになるまで削除する、すなわち頂点1を消した際にできる木を1つ残すことができ、残す木は頂点数が最も多い物がいい
よって頂点1から出る頂点をそれぞれ根としてその木の頂点数を調べ、最大の木以外の頂点数+頂点1が答え

公式解説

省略

E - Takahashi Quest

高橋君が冒険に出かける
冒険では$${N}$$個の出来事が起こり、出来事は整数の組$${(t_{i},x_{i})}$$で表され
・$${t}$$が$${1}$$の時タイプ$${x}$$のポーションを見つけ拾うか捨てるか選ぶ
・$${t}$$が$${2}$$の時タイプ$${x}$$の敵と遭遇する、同じタイプのポーションを持っている場合それを消費し倒すことができる、そうでない場合敗北する
である
高橋君が全ての敵を倒すことができるか、またその場合一度に所持しているポーションの数の最大値を最小でいくつにできるか求める問題

自分の回答

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

  vector<int> need(N + 1, 0);
  stack<int> ans;
  int a = 0, now = 0;
  for(int i = N - 1; i >= 0; i--){
    if(C[i] == 2){
      need[X[i]]++;
      now++;
    }
    else{
      if(need[X[i]] > 0){
        need[X[i]]--;
        ans.push(1);
        now--;
      }
      else{
        ans.push(0);
      }
    }
    a = max(a, now);
  }

  if(count(need.begin(), need.end(), 0) != N + 1){
    printf("-1\n");
  }
  else{
    printf("%d\n", a);
    while(!ans.empty()){
      printf("%d ", ans.top());
      ans.pop();
    }
    printf("\n");
  }
}

ポーションは必要になる直前で拾うのがベストなため、後ろから見て行って敵が現れたらそのタイプと数を記録しそれと同じポーションが出たら拾う
所持数は敵が現れたらその時点で持っているべきポーションの数を++しポーションを拾ったら--
全て倒せるかの判定は必要なタイプで見てるけど所持数が0かで判定できたね
操作の記録はstackで積んでおけば楽

公式解説

省略

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