AtCoder ABC 157 復習メモ

AtCoder ABC

A - Duplex Printing


えっ、難し…く、ない？
(A + B - 1) / B で A を B で切り上げて割り算できるそうなのでそうしました

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

int main() {
  int N;
  cin >> N;
  cout << (N + 2 - 1) / 2 << "\n";
}

ABC153のA問題と同じ問題でした。珍しい

B - Bingo


入力を2次元配列で受け取って
縦横斜めとビンゴしているか2重ループでチェックしていきます。難しい
斜めのループの回し方がとっさに思いつかず手入力しました…

そうするくらいなら↓の方が良かったかもしれません

  int cnt1 = 0, cnt2 = 0;
  for (int i = 0; i < N; i++) {
    cnt1 += V.at(i).at(i);
    cnt2 += V.at(i).at(N - 1 - i);
  }
  if (cnt1 == N || cnt2 == N) ans = true;

斜めチェックはこのように回せば良いそうです。天才か

C - Guess The Number


はい…

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

int main() {
  int N, M;
  cin >> N >> M;
  vector<pair<int, int>> V(M);
  for (int i = 0, s, c; cin >> s >> c; i++) V.at(i) = {s, c};

  // 条件に矛盾がないかチェック(入力例2)
  for (int i = 0; i < M; i++) {
    for (int j = 0; j < M; j++) {
      if (V.at(i).first == V.at(j).first && V.at(i).second != V.at(j).second)
        return cout << -1 << "\n", 0;
    }
  }

  for (int i = 0; i < 1000; i++) {
    string tmp = to_string(i);
    if (tmp.size() != N) continue;
    for (int j = 0; j < M; j++) {
      if (tmp.at(V.at(j).first - 1) - '0' != V.at(j).second) goto NG;
    }
    return cout << i << "\n", 0;
    NG:;
  }
  cout << -1 << "\n";
}

pair は make_pair(a, b) しなくても {a, b} で作れるようです
(tuple は make_taple しないとダメ)
といっても今回sortなどはしないので使わなくていいのですが…！

2重ループを抜けるときはgoto文に甘えがち

D - Friend Suggestions


Union Findを知っていますか問題。私は知りませんでした…
平成ABCはCまでしか触れていないのでほぼ出会わず
おそらく唯一のUnion Find問題、ABC075 C - Bridgeは
見様見真似でDFSで解いていました

というわけで今回もDFSで書こうと試みましたが全く書けず。要復習です
Union Findは解説動画や以下のスライドでふんわり理解しましたが

www.slideshare.net

まだ扱えるかあやしいのでこちらも要練習です。やること多すぎる

E - Simple String Queries


26個のsetの配列を使う発想ができるか。無理でしょ

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

int main() {
  int N, Q;
  string S;
  cin >> N >> S >> Q;
  vector<set<int>> V(26);
  for (int i = 0; i < N; i++) V.at(S.at(i) - 'a').insert(i + 1);
  while (Q--) {
    int type;
    cin >> type;
    if (type == 1) {
      int i;
      char c;
      cin >> i >> c;
      V.at(S.at(i - 1) - 'a').erase(i);
      S.at(i - 1) = c;
      V.at(S.at(i - 1) - 'a').insert(i);
    } else {
      int l, r;
      cin >> l >> r;
      int ans = 0;
      for (int i = 0; i < 26; i++) {
        auto iter = V.at(i).lower_bound(l);
        if (iter != V.at(i).end() && *iter <= r) ans++;
      }
      cout << ans << "\n";
    }
  }
}

解説動画のすぬけさんのコードとほとんど同じです
・iter != V.at(i).end() での存在確認
・イテレータに*を付けるとintと比較できる(付けないと出来ない)
はとても重要そうだなと思いました



おしまい