AtCoder Beginner Contest 295

AtCoder Beginner Contest 295 - AtCoder

結果

A - Probably English : AC(2:34)
B - Bombs : AC(11:34)
C - Socks : AC(17:12)
D - Three Days Ago : TLE

A - Probably English

英小文字からなる文字列が$${N}$$個与えられ、その中に「and」「not」「that」「the」「you」が1つでもあるならば「Yes」、そうでないならば「No」を出力する問題

自分の回答

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

  string w;
  for(int i = 0; i < N; i++){
    cin >> w;
    if(w == "and" || w == "not" || w == "that" || w == "the" || w == "you"){
      printf("Yes\n");
      return 0;
    }
  }
  printf("No\n");
}

そのまま

公式解説

省略

B - Bombs

$${R}$$行$${C}$$列の盤面があり、「.」は空きマス、「#」は壁、1～9はそれぞれその数字の威力の爆弾であることを表す
爆弾は爆発すると、爆弾からのマンハッタン距離が威力以下であるマスを空きマスにする
全ての爆弾が同時に爆発した時、どのような盤面になるかを求める問題

自分の回答

int main(){
  int R, C;
  cin >> R >> C;
  vector<vector<char>> B(R, vector<char>(C));
  for(int i = 0; i < R; i++){
    for(int j = 0; j < C; j++){
      cin >> B[i][j];
    }
  }

  for(int i = 0; i < R; i++){
    for(int j = 0; j < C; j++){
      if(isdigit(B[i][j])){
        for(int k = 0; k < R; k++){
          for(int l = 0; l < C; l++){
            if(abs(i - k) + abs(j - l) <= B[i][j] - 48 && B[k][l] == '#'){
              B[k][l] = '.';
            }
          }
        }
        B[i][j] = '.';
      }
    }
  }

  for(int i = 0; i < R; i++){
    for(int j = 0; j < C; j++){
      printf("%c", B[i][j]);
    }
    printf("\n");
  }
}

爆弾があったら盤面全てのマスを見て行ったけどもっときれいに行けないかなとは思った

公式解説

省略

C - Socks

$${N}$$枚の靴下があり、$${i}$$番目の靴下の色は$${A_{i}}$$である
同じ色の靴下のペアがいくつあるかを求める問題

自分の回答

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

  set<int> cs;
  map<int, int> c;
  int a;
  for(int i = 0; i < N; i++){
    cin >> a;
    cs.insert(a);
    c[a]++;
  }

  int ans = 0;
  while(!cs.empty()){
    ans += c[*begin(cs)] / 2;
    cs.erase(*begin(cs));
  }
  printf("%d\n", ans);
}

mapで色ごとにいくつあるかをまとめて全ての値をそれぞれ/2して足し合わせて終わり

公式解説

int main() {
    int n;
    cin >> n;
    map<int, int> mp;
    for (int i = 0; i < n; i++) {
        int a;
        cin >> a;
        ++mp[a];
    }
    
    int ans = 0;
    for (auto [_, cnt]: mp) ans += cnt / 2;
    cout << ans << endl;
}

https://atcoder.jp/contests/abc295/editorial/6047より

そうかmapは範囲forできたか

D - Three Days Ago

数字のみからなる文字列があり、その文字を並び替えることによって同じ列を2回繰り返す文字列にできるものを嬉しい列と呼ぶ
数字のみからなる文字列$${S}$$が与えられ、$${l}$$文字目から$${r}$$文字目までの部分文字列が嬉しい列となる$${(l,r)}$$の組み合わせはいくつあるか求める問題

自分の回答

要は部分文字列に存在する文字の個数が全種類偶数個であるか、だけどl,rを全て調べようとするとSの長さの二乗になってTLEなのは目に見えてる…
一応提出はしてみたけど当然TLE
こういうのは累積和っぽいんだけどそれでも結局l,rの総当たりでは？となって削減できなかった

公式解説

int main(){
  string s;
  cin >> s;
  map<vector<int>,long long> mp;
  vector<int> cnt(10,0);
  mp[cnt]++;
  for(auto &nx : s){
    cnt[nx-'0']++;
    cnt[nx-'0']%=2;
    mp[cnt]++;
  }
  long long res=0;
  for(auto &nx : mp){
    long long x=nx.second;
    res+=(x*(x-1))/2;
  }
  cout << res << "\n";
  return 0;
}

https://atcoder.jp/contests/abc295/editorial/6034より

まずiという数字がj文字目までで偶数回出てきた時R[i][j]が0、奇数回の時1である累積和の表$${R}$$を考えるとR[0~9][k]=R[0~9][l]の時k+1番目からl番目の部分列が嬉しい列となり、R[0~9][j]が等しいjの中から2つを選んだ組み合わせ数が嬉しい列の数なため、そのR[0~9]の種類ごとに個数を数えて組み合わせの数を足し合わせる

なるほど