AtCoder Beginner Contest 274

2022年10月25日 14:35

結果

A - Batting Average:AC(3:10)
B - Line Sensor:AC(10:59)
C - Ameba:AC(37:25)
D - Robot Arms 2:WA

A - Batting Average

整数$${A,B}$$が与えられ、$${\frac{B}{A}}$$を小数第4位で四捨五入した値を出力する問題

自分の回答

int main(){
  double A, B;
  cin >> A >> B;
  printf("%4.3lf\n", B/A);
}

そのまま

公式解説

同じため省略

B - Line Sensor

縦$${H}$$、横$${W}$$マスのグリッドがあり、各マスに「.」か「#」がある
各列に#がいくつあるかを求める問題

自分の回答

int main(){
  int H, W;
  cin >> H >> W;
  vector<int> count(W, 0);
  for(int i = 0; i < H; i++){
    for(int j = 0; j < W; j++){
      char C;
      cin >> C;
      if(C == '#'){
        count[j]++;
      }
    }
  }
  for(int i = 0; i < W; i++){
    printf("%d", count[i]);
    if(i == W - 1){
      printf("\n");
    }
    else{
      printf(" ");
    }
  }
}

そのまま

公式解説

同じため省略

C - Ameba

最初アメーバが1匹存在し、それに1という番号をつけた
$${A_{i}}$$のアメーバが分裂して消滅し、生まれた2匹のアメーバにそれぞれ$${2i、2i+1}$$という番号をつけたという記録が$${N}$$個ある
このとき$${2i、2i+1}$$に対する$${A_{i}}$$を親という
1から$${2N+1}$$番まで何代遡れば1のアメーバとなるかを求める問題

自分の回答

int main(){
  int N;
  cin >> N;
  vector<int> gen(N * 2 + 2);
  gen[1] = 0;
  printf("0\n");
 
  for(int i = 1; i <= N; i++){
    int A;
    cin >> A;
    gen[i * 2] = gen[A] + 1;
    gen[i * 2 + 1] = gen[A] + 1;
    printf("%d\n%d\n", gen[i * 2], gen[i * 2 + 1]);
  }
}

1から順番に分裂先へ親の世代+1を入れていく
あと1回出てきた番号はそれで終わりだから出力も組み込んだ
直感的に書きやすいようにアメーバの番号と配列の番号を一致させた

公式解説

同じため省略

D - Robot Arms 2

長さ$${N}$$の正整数列$${(A_{1},A_{2},…A_{N})}$$と整数$${x,y}$$が与えられ、座標平面上において点$${p_{1}=(0,0)}$$から$${p_{2}=(A_{1},0)}$$へ移動し、その後は左右どちらかへ90度曲がり$${A_{i}}$$だけ移動した点を$${p_{i+1}}$$とする操作を$${N}$$回繰り返し、最終的に$${(x,y)}$$へたどり着けるかを判定する問題

自分の回答

int N, gx, gy;
 
void DFS(int nowx, int nowy, char Bmove, int count, vector<int> &dis){
  if(count == N){
    if(nowx == gx && nowy == gy){
      printf("Yes\n");
      exit(0);
    }
    else{
      return;
    }
  }
 
  int next = count + 1;
  if(Bmove == 'X'){
    DFS(nowx, nowy + dis[count], 'Y', next, dis);
    DFS(nowx, nowy - dis[count], 'Y', next, dis);
  }
  if(Bmove == 'Y'){
    DFS(nowx + dis[count], nowy, 'X', next, dis);
    DFS(nowx - dis[count], nowy, 'X', next, dis);
  }
}
 
int main(){
  cin >> N >> gx >> gy;
  vector<int> dis(N);
  for(int i = 0; i < N; i++){
    cin >> dis[i];
  }
 
  DFS(dis[0], 0, 'X', 1, dis);

  printf("No\n");
}

深さ優先探索で解けそうだから書いてみた
$${N}$$が最大$${10^3}$$で分岐が2だから時間大丈夫かなと思ったけどダメだった

コード自体はちゃんと書けたから多分根本的なやり方が違う

公式解説

constexpr int M = 10000;
int N, x, y, A[1010], buf1[2 * M + 1], buf2[2 * M + 1], buf3[2 * M + 1];

int main() {
  cin >> N >> x >> y;
  for (int i = 0; i < N; i++) cin >> A[i];
  int *dp1 = buf1 + M, *dp2 = buf2 + M, *dp3 = buf3 + M;
  dp1[A[0]] = dp2[0] = true;
  for (int i = 1; i < N; i++) {
    for (int j = -M; j <= M; j++) dp3[j] = 0;
    int a = A[i];
    if (i % 2 == 0) {
      for (int j = -M; j <= M - a; j++) {
        dp3[j + a] |= dp1[j], dp3[j] |= dp1[j + a];
      }
      swap(dp1, dp3);
    } else {
      for (int j = -M; j <= M - a; j++) {
        dp3[j + a] |= dp2[j], dp3[j] |= dp2[j + a];
      }
      swap(dp2, dp3);
    }
  }
  cout << (dp1[x] and dp2[y] ? "Yes" : "No") << endl;
}

https://atcoder.jp/contests/abc274/editorial/5079より

まず$${i}$$が奇数の時$${x}$$軸方向に動き、偶数の時$${y}$$軸方向に動くからそれぞれ分けて考えられるのか
で、dp1が$${x}$$軸、dp2が$${y}$$軸でどの位置なら行くことができるのかdp3が1,2から$${A_{i}}$$で移動できる場所の一時保管用
全ての位置に対して終わったら3の結果を元のに移して次の$${i}$$に行くのを$${i=1}$$から繰り返していく動的計画法

なるほど、その発想は無かった

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