AtCoder Beginner Contest 265

2022年8月23日 15:25

結果

A - Apple:AC(8:42)
B - Explore:AC(39:59)(2ペナ)
C - Belt Conveyor:AC(64:07)
D - Iroha and Haiku (New ABC Edition):提出無し

A - Apple

りんご1個と3個セットの値段がそれぞれ与えられ、$${N}$$個購入した時の最低値を求める問題

自分の回答

int main() {
  int X, Y, N;
  cin >> X >> Y >> N;
 
  vector<int> a(N + 1, 0);
 
  a[1] = X;
  a[2] = X * 2;
 
  for(int i = 3; i < N + 1; i++){
    int b1, b3;
 
    b1=a[i - 1] + X;
    b3=a[i - 3] + Y;
 
    a[i] = min(b1, b3);
  }
  
  printf("%d\n",a[N]);
}

動的計画法で0から$${N}$$個までの最低値を求める
1個を買って$${i}$$個になった時と3個セットを買って$${i}$$個になった時の小さい方を$${i}$$個に入れていく

A問題なことを考えると1個を3回買った時の値段と3個セットの値段を比較する方向が想定解なのかな

公式解説

int main() {
  int X, Y, N;
  cin >> X >> Y >> N;
  if (X * 3 > Y) {
    cout << (N / 3) * Y + (N % 3) * X << endl;
  } else {
    cout << X * N << endl;
  }
}

https://atcoder.jp/contests/abc265/editorial/4642より

やっぱりそうか、こっちの方がコードも短いか

B - Explore

$${N}$$個の部屋が1列に並んでおり、部屋$${i}$$の次の部屋へ行くには$${A_{i}}$$の時間を使う、また、部屋$${i}$$に到達すると時間を$${Y_{i}}$$得られるボーナス部屋が$${M}$$個あり、最初に時間$${T}$$を持っているときに部屋$${N}$$まで到達できるかを求める問題

自分の回答

int main() {
  int N, M, T;
  cin >> N >> M >> T;
 
  vector<int> usetime(N);
  for(int i = 1; i < N; i++){
    cin >> usetime[i];
  }
 
  map<int, int> bonus;
  for(int i = 0; i < M; i++){
    int r;
    cin >> r >> bonus[r];
  }
 
  int64_t nowtime = T;
  for(int i = 1; i < N; i++){
    nowtime -= usetime[i];
 
    if(nowtime <= 0){
      printf("No\n");
      break;
    }
    else if(i == N - 1){
      printf("Yes\n");
      break;
    }
 
    if(bonus.count(i + 1)){
      nowtime += bonus[i + 1];
    }
  }
}

シンプルに持ち時間を次の部屋へ行ったら減らし、時間が0以下ならNoを出力、ボーナス部屋があるならその分追加、部屋$${N}$$に到達したらYesを出力
WAを2回出して、1回はシンプルな=と==のミス、もう1回はnowtimeのオーバーフロー
1つ1つの数値はintでもオーバーフローしない設定になっているが、加算されてオーバーフローすることを見逃してた

公式解説

基本は同じため省略

ボーナスを配列で管理していたから、そっちの方がコード良くなるのはなるほど

C - Belt Conveyor

縦$${H}$$横$${W}$$のマスにそれぞれU,D,L,Rのどれか1つがあり、Uは上、Dは下、Lは左、Rは右のマスが存在するならばそのマスへ移動し、無いならば終了、$${(1,1)}$$からスタートしてどのマスにたどり着くか、もしくはループするかを求める問題

自分の回答

int main() {
  int H, W;
  cin >> H >> W;
 
  vector<vector<char>> bord(H, vector<char>(W));
  for(int i = 0; i < H; i++){
    for(int j = 0; j < W; j++){
      cin >> bord[i][j];
    }
  }
 
  vector<vector<bool>> check(H, vector<bool>(W, 0));
  pair<int, int> now(0, 0);
  while(true){
    if(check[now.first][now.second]){
      printf("-1\n");
      break;
    }
 
    if(bord[now.first][now.second] == 'U' && now.first != 0){
      check[now.first][now.second] = 1;
      now.first--;
    }
    else if(bord[now.first][now.second] == 'D' && now.first != H - 1){
      check[now.first][now.second] = 1;
      now.first++;
    }
    else if(bord[now.first][now.second] == 'L' && now.second != 0){
      check[now.first][now.second] = 1;
      now.second--;
    }
    else if(bord[now.first][now.second] == 'R' && now.second != W - 1){
      check[now.first][now.second] = 1;
      now.second++;
    }
    else{
      printf("%d %d\n", now.first+1, now.second+1);
      break;
    }
  }
}

現在位置をpairで管理して、移動部分はシンプルに条件に合うなら移動、条件に合わないならば終了なため現在位置を出力
前に踏んだマスを再び踏んだら同じ動きをすることになるためループになる、そこから考えて1度踏んだマスを同じ縦横マス数のbool配列で管理

ただ後から考えると現在地をpairで管理したのはコードが長くなるだけだったか
あとチェック用の配列は用意しなくても元の配列に上書きで行けたかな

公式解説

基本は同じため省略

D - Iroha and Haiku (New ABC Edition)

長さ$${N}$$の数列$${A}$$が与えられ、$${A_{x}+A_{x+1}+……+A_{y-1}=P}$$,$${A_{y}+A_{y+1}+……+A_{z-1}=Q}$$,$${A_{z}+A_{z+1}+……+A_{w-1}=R}$$となる整数の組$${\text{\textbraceleft}x,y,z,w\text{\textbraceright}}$$が存在するかを求める問題

自分の回答

$${P,Q,R}$$の素となる数列は全て連続しているため$${x,y-1}$$を全て求め、それを基に$${z,w}$$が存在するかを確認する方向で書いてみたけど時間内に書ききれず、終了後に書ききってもサンプルすら通らなかったためギブ

公式解説

using ll=long long;

int main(){
	int n;
	ll p,q,r;
	cin >> n >> p >> q >> r;
	ll crr=0;
	set<ll>s({0});
	for(int i=0;i<n;i++){
		int a;
		cin >> a;
		crr+=a;
		s.insert(crr);
	}
	
	for(auto x:s){
		if(s.find(x+p)!=s.end() && s.find(x+p+q)!=s.end() && s.find(x+p+q+r)!=s.end()){
			cout << "Yes" << endl;
			return 0;
		}
	}
	cout << "No" << endl;
}

https://atcoder.jp/contests/abc265/editorial/4591より

0番目から$${i}$$番目までの総和を$${N}$$まで入れたsetを用意して、
その中に$${s_{i}+P}$$が等しくなる$${s_{j}}$$が存在するならば、$${P = s_{j} - s_{i}}$$なため$${A_{i+1}}$$から$${A_{j}}$$までの総和が$${P}$$となる、すなわち$${\text{\textbraceleft}x,y\text{\textbraceright}}$$が存在する
同様に$${s_{j}+Q=s_{k},s_{k}+R=s_{l}}$$が存在すれば$${\text{\textbraceleft}x,y,z,w\text{\textbraceright}}$$が存在する

なるほど

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