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

AtCoder Beginner Contest 303 の振り返り

• A,C問題を解くことができた
• A問題：一文字ずつ条件を満たすかを調べるだけだがコード量が多い。しかもcharとintを比較していたことに気付くのが遅れた
• B問題：サンプルは通ったが実行時エラーが7つ出た。隣り合う者同士をペアで管理し、あり得るペアの総数と実際のペア数から解を求める。同じ者同士のペアは区別しないのでダブルカウントを防ぐ
• C問題：アイテムの置かれる座標をペアとしてsetで管理した。アイテムを消費した場合は集合から削除する処理も忘れずに
• D問題：動的計画法で実装できず

A問題

atcoder.jp

方針

• 与えられた文字列を一文字ずつ条件のいずれかを満たすかを調べます

解説*1から

• 文字の組み合わせがlと1、oと0となるかを調べずに、1だったらlに、0だったらoに変換します（標準型）
• その後、2つの文字が一致するかを調べます

char normalize(char a) {
    if (a == '1') return 'l';
    if (a == '0') return 'o';
    return a;
}

bool similar(char a, char b) {
    a = normalize(a);
    b = normalize(b);
    return a == b;
}

int main() {
    int n;
    cin >> n;
    string s, t;
    cin >> s >> t;
    for (int i = 0; i < n; i++) {
        if (!similar(s[i], t[i])) {
            cout << "No" << endl;
            return 0;
        }
    }

    cout << "Yes" << endl;
    return 0;
}

B問題

atcoder.jp

方針

• 隣り合う人の組み合わせをpair型で表現しsetで管理します。 とを区別しないので、どちらも組み合わせもsetに追加します
• あり得るpairの総数はなので、setのサイズ数を減算すれば答えを導けます。このとき重複する組み合わせをカウントしているので で割ります
• なお実行時エラーになるケースが存在しました

int main () {

  ifstream in("../../input.txt");
  cin.rdbuf(in.rdbuf());

  int N, M;
  cin >> N >> M;
  vector<vector<int>> snap(N, vector<int>(M));
  for (int i = 0; i < M; i++) {
    for (int j = 0; j < N; j++) cin >> snap[i][j];
  }

  set<pair<int, int>> friends;
   for (int i = 0; i < M; i++) { 
    for (int j = 0; j + 1 < N; j++) {
      int a = snap[i][j];
      int b = snap[i][j+1];
      friends.insert(make_pair(a,b));
      friends.insert(make_pair(b,a));
    }
  }

  cout << (N * (N-1) - (int)friends.size()) / 2 << endl;

  return 0;
}

解説*2から

• 隣り合う組を表現する二次元配列を用意します
• 組み合わせを探索し、上の二次元配列に存在しない組がある場合答えとなる組になります

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> a(m, vector<int>(n));
    for (int i = 0; i < m; i++) cin >> a[i][j];
    for (int i = 0; i < m; i++) a[i][j]--;

    vector<vector<bool>> g(n, vector<bool>(n));
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n-1; j++) {
            g[a[i][j]][a[i][j+1]] = true;
        }
    }

    int ans = 0;
    for (int x = 0; x < n; x++) {
        for (int y = 0; y < x; y++) if (g[x][y] or g[y][x]) continue;
        ans++; 
    }

    cout << ans << endl;

    return 0;
}

C問題

atcoder.jp

方針

• アイテムの存在する座標をpair型で表現し、set型で管理します
• 初期位置や移動先の座標もpair型で表現します
• アイテムを使用した場合はset型からその座標を削除します

int main () {

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

  int x = 0, y = 0;
  for (int i = 0; i < N; i++) {
    char si = S[i];
    H--;
    if (H < 0) {
      cout << "No" << endl;
      return 0;
    }
    if (si == 'R') x++;
    else if (si == 'L') x--;
    else if (si == 'U') y++;
    else if (si == 'D') y--;
    if (items.count({x,y}) == 1 && H < K) {
      H = K;
      items.erase({x, y});
    }
  }
  
  cout << "Yes" << endl;

  return 0;
}

D問題

atcoder.jp

解説*3から

• capslockのオン、オフ、与えられた文字列によっても求める最小時間は変わるので全探索で調べます
• 全探索を高速化する手法として動的計画法とメモ化再帰があります

// メモ化再帰
ll dp[300005][2];
bool memo[300005][2];

int main() {
    
    int x, y, z;
    cin >> x >> y >> z;
    string s;
    cin >> s;

    auto f = [&](auto f, int i, int c) -> ll {
        if (memo[i][c]) return dp[i][c];
        ll res = 1e18;
        int a = s[i] == 'A' ? 1 : 0;
        int const1 = (a == c) ? x : y;
        int const2 = ((a == c) ? x : y) + z;
        res = const1 + f(f, i+1, c);
        res = min(res, const2 + f(f, i+1, !c));
        memo[i][c] = true;
        return dp[i][c] = res;
    }

    cout << f(f, 0, 0) << endl;

    return 0;
}

// 動的計画
int maain() {
    int x, y, z;
    cin >> x >> y >> z;
    string s;
    cin >> s;
    int n = s.size();

    const ll INF = 1e18;
    vector<vector<ll>> dp(n+1, vector<ll>(2, INF));

    dp[0][0];
    for (int i = 0; i < n; i++) {
        for (int c = 0; c < 2; c++) {
            int a = s[i]=='A';
            for (int nc = 0; nc < 2; nc++) {
                ll cost = (a == nc) ? x : y;
                if (c != nc) cost += z;
                dp[i+1][nc] = min(dp[i+1][nc], dp[i][c] + cost);
            }
        }
    }

    cout << min(dp[n][0], dp[n][1] << endl;

    return 0;
}

*1:https://www.youtube.com/live/_toS2Czj1to?feature=share

*2:https://www.youtube.com/live/_toS2Czj1to?feature=share

*3:https://www.youtube.com/live/_toS2Czj1to?feature=share