AtCoder Beginner Contest 295 に参加しました＆反省会

AtCoder Beginner Contest 295 の振り返り

• C問題まで解くことができた
• A問題：愚直に if 文で判定しようとしたがもっと良い書き方がありそうだ
• B問題：charを数値に変換する際に愚直にintでキャストしたために意図と外れた結果になった。char型の数字を数値にするのだからアスキーコードで変換するとすぐに気づきたかった
  マンハッタン距離は上下左右に限られないと例示から判断する
• C問題：要素毎の個数を求める際にベクターで要素を添え字にし、その個数を数え上げ ようとしたが実行に時間がかかった。
  mapの実装に慣れていないために時間がかかった
• D問題：文字列の文字ごとにすべてが偶数ならカウントアップとC問題に近いと考えていたが、どうも解答が合わない

A問題

atcoder.jp

方針

• for 文の中にif 文を5つ並べる

解説*1から

• 「 if 文の中で変化するものだけを配列に入れて for 文を回す」

vector<string> word={"and", "not", "that", "the", "you"};
for(int i=0;i<n;i++){
    string s;
    cin >> s;
    for(auto &nx : word){
      if(s==nx){res=true;}
    }
}

B問題

atcoder.jp

方針

• のマスが数値のときchar型からint型に変換する（爆弾の威力）
• 現在のマスと爆弾の威力を引数として関数に渡す
• 関数で、すべてのマスを探索し、マンハッタン距離が爆弾の威力内にあるマスを空きマスにする。ただし、数字マスはそのままにする

• 現在のマスを空きマスにする

• char型からint型に変換
  (int)B[i][j]とするとになるのでになるように揃える
  int bomb = (int)B[i][j]-'0';
  実装例

#include<bits/stdc++.h>
using namespace std;

 int R, C;

void destroy(int x, int y, int bomb, vector<string> &B) {

  for (int i = 0; i < R; i++) {
    for (int j = 0; j < C; j++) {
      
      if ((abs(i-x)+abs(j-y)) <= bomb) {
        if (!(B[i][j] >= '1' && B[i][j] <= '9')) {
            B[i][j] = '.';
          }
      }
        
      }
  }
}


int main () {

 
  cin >> R >> C;
  vector<string> B(R);
  for (auto &Bi : B) cin >> Bi;

  for (int i = 0; i < R; i++) {
    for (int j = 0; j < C; j++) {
      if (B[i][j] >= '1' && B[i][j] <= '9') {
        int bomb = (int)B[i][j]-48;
        B[i][j] = '.';
        destroy(i, j, bomb, B);
      }
    }
  }

  for (auto Bi : B) cout << Bi << endl;

  return 0;
}

C問題

atcoder.jp

方針

• mapを利用して「何色の靴下が何枚あるか」という情報を管理する
• ある色の靴下が枚あるとき、この色の靴下同士をペアにする操作を繰り返すことで、回の操作が可能になる

解説*2から

#include<bits/stdc++.h>

using namespace std;

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;
}

D問題

atcoder.jp

方針

• 部分文字列に含まれる数字が偶数回登場するのなら嬉しい列となる
• 登場回数を求めるのに累積和を利用する
• 偶数個あるかどうかを知りたいのでを利用する

解説*3から

#include<bits/stdc++.h>
using namespace std;

int main() {
    string s;
    cin >> s;
    int n = s.size();
    vector<int> x(n+1);
    for (int i = 0; i < n; i++) {
        int c = s[i]-'0';
        x[i+1] = x[i] ^ 1<<c;
    }
    map<int, int> mp;
    for(int i = 0; i < n+1; i++) mp[x[i]]++;

    long long ans = 0;
    for (auto p : mp) {
        long long num = p.second;
        ans += num*(num-1)/2;
    }

    cout << ans << endl;

    return 0;
}

*1:https://atcoder.jp/contests/abc295/editorial/6033

*2:https://atcoder.jp/contests/abc295/editorial/6047

*3:https://atcoder.jp/contests/abc295/editorial/6034