AtCoder Beginner Contest 270

TOYOTA MOTOR CORPORATION Programming Contest 2022(AtCoder Beginner Contest 270) - AtCoder

結果

A - 1-2-4 Test:AC(13:28)
B - Hammer:AC(29:49)(1ペナ)
C - Simple path:提出無し

A - 1-2-4 Test

高橋君、青木君、すぬけ君が配点1点、2点、4点のテストを受け、すぬけ君は高橋君、青木君の少なくとも片方が解けた問題は解け、どちらも解けなかった問題は解けない
このとき高橋君の点数が$${A}$$、青木君の点数が$${B}$$だった場合のすぬけ君の点数を求める問題

自分の回答

int main() {
  int A, B, S = 0;
  cin >> A >> B;
 
  if(A >= 4 && B >= 4){
    S += 4;
    A -= 4;
    B -= 4;
  }
  else if(A >= 4 && B < 4){
    S += 4;
    A -= 4;
  }
  else if(B >= 4 && A < 4){
    S += 4;
    B -= 4;
  }
 
  if(A >= 2 && B >= 2){
    S += 2;
    A -= 2;
    B -= 2;
  }
  else if(A >= 2 && B < 2){
    S += 2;
    A -= 2;
  }
  else if(B >= 2 && A < 2){
    S += 2;
    B -= 2;
  }
 
  if(A >= 1 || B >= 1){
    S++;
  }
 
  printf("%d\n",S);
}

4点問題を解けているならば所持点数は4点以上なため、その人がいればSに4点加点し、4点以上の人から4点減らす
これを2点と1点についてもやってSを出力

最初どちらか片方のみと勘違いして書いたコードを修正したため無駄はある
あと根本的にもっと短く書く方法はありそう

公式解説

int main() {
	int a, b;
	cin>>a>>b;
	cout<<(a|b)<<endl;
	return 0;
}

https://atcoder.jp/contests/abc270/editorial/4877より

そうか点数を2進数で表せばOR演算が答えか！
1,2,4なのはbitだったか

なるほど

B - Hammer

数直線上の$${X}$$にゴール、$${Y}$$に壁、$${Z}$$にハンマーがあり、ハンマーを取らないと壁を越えられない
原点からスタートし、ゴールまでの最小距離を求める問題、ただしゴールできないときは-1

自分の回答

int main() {
  int X, Y, Z;
  cin >> X >> Y >> Z;
 
  if(X > 0){
    if(Y < 0 || Y > X){
      printf("%d\n",X);
      return 0;
    }
    else if(Z < Y){
      if(Z > 0){
        printf("%d\n",X);
        return 0;
      }
      else{
        printf("%d\n",abs(Z) * 2 + X);
        return 0;
      }
    }
  }
  else{
    if(Y > 0 || Y < X){
      printf("%d\n",abs(X));
      return 0;
    }
    else if(Z > Y){
      if(Z < 0){
        printf("%d\n",abs(X));
        return 0;
      }
      else{
        printf("%d\n",Z * 2 + abs(X));
        return 0;
      }
    }
  }
 
  printf("-1\n");
}

まず先の分岐のためにゴールの位置の正負で分け、原点とゴールの間に壁が無いならその距離を出力
壁があるがハンマーが壁より自分側にあるならばゴールでき、ハンマーがゴールと同符号なら直行なためゴールまでの距離を出力、異符号ならばハンマーまで行って帰ってくるためハンマーまでの距離を2倍したものを追加して出力
全て当てはまらなかったらゴールできないため-1を出力

2倍する場所を間違えて1ペナ

公式解説

int main(){
	int x,y,z;
	scanf("%d%d%d",&x,&y,&z);
	
	if(y<0){
		x=-x;
		y=-y;
		z=-z;
	}
	
	if(x<y){
		printf("%d\n",abs(x));
	}else{
		if(z>y){
			puts("-1");
		}else{
			printf("%d\n",abs(z)+abs(x-z));
		}
	}
}

https://atcoder.jp/contests/abc270/editorial/4849より
C言語によるもの

壁が負のとき符号を反転させると条件分けが減らせるのか

なるほど

C - Simple path

$${N}$$頂点の木があり、$${i(1\leqq i \leqq N-1)}$$番目の辺が頂点$${U_{i}}$$と$${V_{i}}$$を結んでいる
このとき頂点$${X,Y}$$が与えられ、$${X}$$から$${Y}$$までの頂点を出力する問題

自分の回答

深さ優先探索を調べながら書いてみたがサンプルの時点で139エラーが出た

公式解説

vector<int>e[200010];
bool flag[200010];
deque<int> deq;
bool stop;
 
void dfs(int k,int to){
	if(!stop)deq.push_back(k);
	if(k==to)stop=true;
    flag[k]=true;
	int sz=e[k].size();
    for(int i=0;i<sz;i++){
        if(!flag[e[k][i]])dfs(e[k][i],to);
    }
	if(!stop)deq.pop_back();
	return;
}
int main(void) {
    int n,x,y;
    int u,v;
	cin>>n>>x>>y;
    for(int i=0;i<n-1;i++){
		cin>>u>>v;
		e[u].push_back(v);
		e[v].push_back(u);
    }
    for(int i=1;i<=n;i++)flag[i]=false;
    stop = false;
　dfs(x,y);
    while(!deq.empty()){
		cout<<deq.front();
		deq.pop_front();
		if(deq.empty())cout<<endl;
		else cout<<" ";
	}
	return 0;
}

https://atcoder.jp/contests/abc270/editorial/4878より

stopが$${Y}$$に到達しているかの管理
stopがfalseの間は到達した頂点をdeqに入れて再帰
$${Y}$$に到達せず行き先が無くなったら後ろの値を削除して1つ戻る

この理解で合ってるのかな