ABC442 振り返り

※ 本記事は競技プログラミング初心者による振り返りです。 内容に誤りが含まれる可能性があります。

こんにちは。
私は tRu といいます。
今回から、学んだことを整理して発信するために Quita を始めることにしました。
それでは、ABC422の振り返りをしていきます。

A - Count .

文字列を走査して、その文字が、 i または j であった場合にカウントしていけば、答えが求められます。

計算量 O(|S|)

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

int main () {
    string s;
    cin >> s;
    int cnt = 0;
    for (auto tmp : s) {
        if (tmp == 'i' || tmp == 'j') cnt++;
    }
    cout << cnt << endl;
}

B - Music Player

「今、曲が再生されているかどうか」と「現在の音量」を、それぞれ管理して、クエリを処理します。音量を下げる場合のみ、max(0, vol - 1) で更新します。

計算量 O(Q)

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

int main () {
   bool playing = false; // 今、曲が再生されているかどうか
   int vol = 0; // 現在の音量

   int q;
   cin >> q;
   while (q--) {
       int a;
       cin >> a;
       if (a == 1) vol++;
       else if (a == 2) vol = max(0, vol - 1);
       else playing = !playing;
       if (playing && vol >= 3) cout << "Yes" << endl;
       else cout << "No" << endl;
   }
}

C - Peer Review

初期値を n-1 とし、 各研究者について「利害関係のない人数」を管理します。

その人数を n とすると、 そこから 3 人を選ぶ組み合わせ数は、
$$
nC3 = \frac{n \times (n-1) \times (n-2)}{6}
$$
で求められます。

計算量 O(N+M)

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

 int main () {
     int n, m;
     cin >> n >> m;
     vector<long long> cnt(n + 1, n - 1); // 1-indexed

     for (int i = 0; i < m; i++) {
         int a, b;
         cin >> a >> b;
         cnt[a]--;
         cnt[b]--;
     }
     for (int i = 1; i <= n; i++) {
         long long ans = cnt[i] * (cnt[i] - 1) * (cnt[i] - 2) / 6;
         cout << ans << endl;
     }
 }

D - Swap and Range Sum

数列を累積和 sum で管理すると、
区間和は、
$$
sum[r] - sum[l-1]
$$
で求められます。

そして、隣接する要素 A[x] と A[x+1] を入れ替えても、累積和の変化は局所的です。

例えば、以下の配列において、A[2] と A[3] を入れ替えると、

A   = {1, 8, 10, 18, 52}     → swap →     {1, 10, 8, 18, 52} 
sum = {1, 9, 19, 37, 89}                  {1, 11, 19, 37, 89}
          ↑   　　　　　　　　　　　　　　　    　 ↑
                                        ここしか変化していない

sum[2] のみが変化していることがわかります。
数式で書くと、
$$
sum[x] = sum[x-1] + A[x+1]
$$
このように、A[x] と A[x+1] の swap は、累積和の 局所的な差分 にしか影響しません。
他の部分には影響を与えないことが確認できます。

計算量 O(N+Q)

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

 int main () {
    int n, q;
    cin >> n >> q;
    vector<int> a(n + 1); // 1-indexed
    vector<long long> sum(n + 1, 0); // 1-indexed
    
    // 累積和の作成
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        sum[i] += sum[i - 1] + a[i];
    }

    while (q--) {
        int f;
        cin >> f;
        if (f == 1) {
            int x;
            cin >> x;
            sum[x] = a[x + 1] + sum[x - 1];
            swap(a[x], a[x + 1]);
        }
        else {
            int l, r;
            cin >> l >> r;
            long long ans = sum[r] - sum[l - 1];
            cout << ans << endl;
        }
    }
 }

まとめ

今回のABCはD問題が灰DIFと易化していました。
…にもかかわらず、C問題でnC3をnCrの公式に当てはめて!nをしようとして沼ったり、D問題をFenwick Treeで殴ったりと、大負けでした(´;ω;｀)