AtCoder Beginner Contest 157
今回は A から E までの 5 完。わりと調子良かった。
入水できるんじゃないかなと期待もしたが、思っていたよりレーティングは上がらなかった。 もう 2 回位は水パフォーマンスが必要そう。
A
n を 2 で割ったものに、n が奇数ならさらに 1 加算する。
B
愚直に 3x3 の2次元配列を作って、それがビンゴの条件を満たしているか確認する。
ちょっと実装がめんどいぐらい。
C
調べればいい範囲がたかだか 1000 以下だったので、総当りで条件にあっているものを探す。
こっちも愚直な実装になった。
D
Union Find 木を使って、グループ分けをする。
その後 1 から N までについて、グループのサイズから「直接の友人関係にある人数」と「グループ内でブロックしている人数」、「自分自身」の数を引く。 Union Find 木のテンプレートを持ってなかったので０から実装したがなんとか間に合った。テンプレ実装は用意しておいたほうが良さそう。
なお、自分はこれよりも E を先に解いていた。他にも同じような判断をした人はそこそこいるっぽい。
E
競技プログラミングでよくある発想の転換が要求される問題だと思う。
最初に考えた 2 個目のコマンドの「l 文字目から r 文字目までで含まれる文字種のカウント」は、愚直にやっていたら計算量が大きくなりそう。
最悪の場合は N x Q で 1010 かかるので、時間内に終わらないと判断した。
考えを変えて、ある文字が「l 文字目から r 文字目までで含まれる」かどうかを 26 回高速に判定できれば良さそう、と考えた。
なので 26 個アルファベットごとに std::set<ll> を用意して、出現位置を入れておく。
コマンド 1 は set への追加と削除で済ませて、コマンド 2 の方は l より大きい出現位置を lower_bound でとってそれが r 以下なら条件を満たすとしてそれぞれカウントすればよい。
int main() {
ll n;
cin >> n;
string s;
cin >> s;
vector<set<ll>> d(26, set<ll>());
for (ll i = 0; i < n ; ++i) {
int c = s[i] - 'a';
d[c].insert(i+1);
}
ll m;
cin >> m;
for (ll j = 0; j < m; ++j) {
int com;
cin >> com;
if (com == 1) {
ll i;
int idx;
char c;
cin >> i >> c;
idx = c - 'a';
for (ll k = 0; k < 26; ++k) {
d[k].erase(i);
}
d[idx].insert(i);
} else {
ll left, right;
cin >> left >> right;
ll count = 0;
for (ll k = 0; k < 26; ++k) {
auto iter = d[k].lower_bound(left);
if (iter != d[k].end() && *iter <= right) {
++count;
}
}
cout << count << endl;
}
}
}
