AtCoder Beginner Contest 303

NS Solutions Corporation Programming Contest 2023（AtCoder Beginner Contest 303） - AtCoder

結果

A - Similar String : AC(4:14)
B - Discord : AC(12:22)
C - Dash : AC(24:46)
D - Shift vs. CapsLock : WA

A - Similar String

長さ$${N}$$の文字列$${S,T}$$が与えられ、$${S,T}$$の$${i}$$文字目全てが同じ、もしくは片方が「1」でもう片方が「l」、もしくは片方が「0」でもう片方が「o」であるとき似た文字列である
$${S,T}$$が似た文字列であるか判定する問題

自分の回答

int main(){
  int N;
  string S, T;
  cin >> N >> S >> T;

  for(int i = 0; i < N; i++){
    char s = S[i], t = T[i];
    if(s == t){
      continue;
    }
    else if((s == '1' && t == 'l') || (s == 'l' && t == '1')){
      continue;
    }
    else if((s == '0' && t == 'o') || (s == 'o' && t == '0')){
      continue;
    }
    printf("No\n");
    return 0;
  }
  printf("Yes\n");
}

そのまま

公式解説

省略

B - Discord

$${1}$$から$${N}$$までの番号が付けられた人が$${M}$$回一列に並んで集合写真を撮った
$${M}$$回の撮影を通して$${1}$$回も隣り合わなかったペアが何組あるか求める問題

自分の回答

int main(){
  int N, M;
  cin >> N >> M;
  vector<vector<bool>> R(N + 1, vector<bool>(N + 1, false));

  for(int i = 0; i < M; i++){
    vector<int> A(N);
    for(int j = 0; j < N; j++){
      cin >> A[j];
    }
    for(int j = 0; j < N - 1; j++){
      R[A[j]][A[j + 1]] = true;
      R[A[j + 1]][A[j]] = true;
    }
  }

  int ans = 0;
  for(int i = 1; i <= N; i++){
    for(int j = i + 1; j <= N; j++){
      if(R[i][j] == false){
        ans++;
      }
    }
  }
  printf("%d\n",ans);
}

二次元配列でペアが隣り合ったかを管理

公式解説

省略

C - Dash

二次元平面上の点$${(0,0)}$$に体力$${H}$$の高橋君が存在し、$${M}$$個の体力回復アイテムが点$${(x_{i},y_{i})}$$にある
高橋君の行動を決める長さ$${N}$$の文字列$${S}$$があり、$${i}$$文字目が「R」の時右に、「L」の時左に、「U」の時上に、「D」の時下に体力を$${1}$$消費して$${1}$$マス移動する
体力が負になった時高橋君は倒れ、そうでない場合、かつ移動したマスにアイテムがあり体力が$${K}$$未満の場合そのマスのアイテムを消費して体力を$${K}$$まで回復する
高橋君が倒れることなく最後まで移動できるか求める問題

自分の回答

int main(){
  int N, M, H, K;
  string S;
  cin >> N >> M >> H >> K >> S;
  set<pair<int, int>> P;
  for(int i = 0; i < M; i++){
    int x, y;
    cin >> x >> y;
    P.insert({x, y});
  }

  int X = 0, Y = 0;
  for(char c : S){
    if(c == 'R'){
      X++;
    }
    else if(c == 'L'){
      X--;
    }
    else if(c == 'U'){
      Y++;
    }
    else{
      Y--;
    }

    H--;
    if(H < 0){
      printf("No\n");
      return 0;
    }
    if(H < K && P.count({X, Y})){
      H = K;
      P.erase({X, Y});
    }
  }
  printf("Yes\n");
}

アイテムの位置を二次元配列で管理すると無駄が多そうだったからpairのsetで管理

公式解説

省略

D - Shift vs. CapsLock

aキー、Shiftキー、CapsLockキーの$${3}$$つのキーがあるキーボードがあり、始めCapsLockはオフである
以下の$${3}$$つの操作を利用し、「A」と「a」からなる文字列$${S}$$を打ち込むには最短何ミリ秒必要か求める問題
・$${X}$$ミリ秒かけてaキーのみを押す、CapsLockがオフならaが、オンならAが打ち込まれる
・$${Y}$$ミリ秒かけてShiftキーとaキーを押す、上の逆
・$${Z}$$ミリ秒かけてCapsLockキーを押す、CapsLockがオフならオンに、オンならオフになる

自分の回答

同じ文字の塊で貪欲法をしたけど書いてる時点でダメなパターンは見えたし実際WAが出た

そうなると動的計画法っぽいけどどう組むかを思いつかなかった

公式解説

constexpr long long INF = 1000000000000000000;
int main() {
    
	long long X,Y,Z;
	cin>>X>>Y>>Z;
	
	string S;
	cin>>S;
	
	vector dp(S.size()+1,vector<long long>(2,INF));
	dp[0][0] = 0;
	
	for(int i=0;i<S.size();i++){
		int cur;
		if(S[i]=='a')cur = 0;
		else cur = 1;
		for(int j=0;j<2;j++){
			for(int k=0;k<2;k++){
				long long v = dp[i][j];
				if(j!=k)v += Z;
				if(cur==k)v += X;
				else v += Y;
				dp[i+1][k] = min(dp[i+1][k],v);
			}
		}		
	}
	
	cout<<min(dp[S.size()][0],dp[S.size()][1])<<endl;
  for(int i=0;i<S.size()+1,i++){
    printf("%d %d\n",dp[i][0],dp[i][1]);
  }
	
	return 0;
}

https://atcoder.jp/contests/abc303/editorial/6442より

i文字目でのオンオフそれぞれの最短時間か

なるほど