AtCoder Beginner Contest 307

Tokio Marine & Nichido Fire Insurance Programming Contest 2023（AtCoder Beginner Contest 307) - AtCoder

結果

A - Weekly Records : AC(2:43)
B - racecar : AC(8:47)
C - Ideal Sheet : AC(95:38)(3ペナ)
D - Mismatched Parentheses : AC(66:36)(2ペナ)

A - Weekly Records

高橋君が$${N}$$週間の間歩いた歩数を記録した
週ごとの歩数を求める問題

自分の回答

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

  for(int i = 0; i < N; i++){
    int ans = 0;
    for(int j = 0; j < 7; j++){
      int a;
      cin >> a;
      ans += a;
    }
    printf("%d ", ans);
  }
  printf("\n");
}

そのまま

公式解説

省略

B - racecar

英小文字からなる文字列が$${N}$$個与えられる
その中から重複無しで2つ選んで連結した文字列が回文となる組み合わせが存在するか求める問題

自分の回答

int main(){
  int N;
  cin >> N;
  vector<string> S(N);
  for(int i = 0; i < N; i++){
    cin >> S[i];
  }

  for(int i = 0; i < N; i++){
    for(int j = 0; j < N; j++){
      if(i == j){
        continue;
      }
      string st = S[i] + S[j];
      bool pal = true;
      for(int k = 0; k < st.size(); k++){
        if(st[k] != st[st.size() - 1 - k]){
          pal = false;
          break;
        }
      }
      if(pal){
        printf("Yes\n");
        return 0;
      }
    }
  }
  printf("No\n");
}

総当たり

公式解説

省略

C - Ideal Sheet

黒いマスと透明なマスからなるシート$${A,B}$$があり、$${2}$$つのシートを向きを変えたり反転することはせずに無限に広がる透明なマスのみのシートの上に自由に置いて切り出すことで、理想とするシート$${X}$$と一致させることができるか判定する問題
ただしシート$${A,B}$$の黒いマスは切り出されたシートに全て含まれている必要がある

自分の回答

int main(){
  vector<pair<int,int>> A, B;
  set<pair<int, int>> X;
  int ha, wa;
  cin >> ha >> wa;
  for(int i = 0; i < ha; i++){
    for(int j = 0; j < wa; j++){
      char c;
      cin >> c;
      if(c == '#'){
        A.push_back({i, j});
      }
    }
  }
  int hb, wb;
  cin >> hb >> wb;
  for(int i = 0; i < hb; i++){
    for(int j = 0; j < wb; j++){
      char c;
      cin >> c;
      if(c == '#'){
        B.push_back({i, j});
      }
    }
  }
  int h, w;
  cin >> h >> w;
  for(int i = 0; i < h; i++){
    for(int j = 0; j < w; j++){
      char c;
      cin >> c;
      if(c == '#'){
        X.insert({i, j});
      }
    }
  }

  for(int ia = -10; ia <= 10; ia++){
    for(int ja = -10; ja <= 10; ja++){
      for(int ib = -10; ib <= 10; ib++){
        for(int jb = -10; jb <= 10; jb++){
          set<pair<int, int>> now;
          for(auto [i, j] : A){
            now.insert({i + ia, j + ja});
          }
          for(auto [i, j] : B){
            now.insert({i + ib, j + jb});
          }
          if(X == now){
            printf("Yes\n");
            return 0;
          }
        }
      }
    }
  }
  printf("No\n");
}

黒マスの座標を加減算してsetに入れてXの黒マスの座標のsetと一致するか調べる

ABの黒マスが全て含まれている必要があることを見逃して1ペナ
加減算の範囲を間違えて2ペナ
コンテスト終了が迫ってて慌ててたのはわかるけど落ち着けば1ペナ減らせた

公式解説

省略

D - Mismatched Parentheses

英小文字及び「(」「)」からなる文字列$${S}$$が与えられる
最初の文字が(で、間に( )のどちらも存在せず)で終わる連続部分文字列を削除する操作を可能な限りした後の文字列$${S}$$を求める問題

自分の回答

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

  deque<char> ans;
  int c = 0;
  for(int i = 0; i < N; i++){
    if(S[i] == ')' && c > 0){
      while(ans.back() != '('){
        ans.pop_back();
      }
      ans.pop_back();
      c--;
    }
    else{
      if(S[i] == '('){
        c++;
      }
      ans.push_back(S[i]);
    }
  }

  for(char c : ans){
    printf("%c", c);
  }
  printf("\n");
}

dequeで(がある時に)が来たら後ろから最も近い(まで消す
stackでもできるけど出力を考えてこっち

最初vectorでやってTLE
調整でどうにかできるかと思ってもう一つTLE

公式解説

int main(){
	int n;
	cin >> n;
	string s;
	cin >> s;
	string ans;
	int depth=0;
	for(auto c:s){
		if(c==')'&&depth>0){
			while(ans.back()!='(')ans.pop_back();
			ans.pop_back();
			depth--;
		}else{
			ans+=c;
			if(c=='(')depth++;
		}
	}
	cout << ans << endl;
}

https://atcoder.jp/contests/abc307/submissions/42735739より

そうかstringでもpop_backできたか