ARC113 振り返りメモ (C問題まで)

結果

ABCまでの3完で, レート変化は730→796(+66)

A問題 ( A * B * C )

概要

A*B*C <= K となるような (A, B, C) の組の総数を求める

方針

A*B*C <= K となる A, B, C (ただし, A <= B <= C とする)を求め,

• A < B < C なら, 答えを + 6 ( 3 ! ) する.
• A = B = C なら, 答えを + 1 する.
• A, B, C のうち, いずれか2つが等しいなら, 答えを + 3 する.

C++ での実装例は以下のようになる.
計算量の見積もり方が分からなかったが, O(KlogK)より少ない？

a.cpp

#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (long long i = 0; i < (n); i++)
using ll = long long;
using P = pair<ll, ll>;

int main() {
    ll k; cin >> k;
    ll ans = 0;
    for (ll i = 1; i*i*i <= k; i++) {
        for (ll j = i; i*j*j <= k; j++) {
            for (ll l = j; i*j*l <= k; l++) {
                if (i < j && j < l) ans += 6;
                else if (i == j && j == l) ans += 1;
                else ans += 3;
            }
        }
    }
    cout << ans << endl;
} 

公式解説

公式解説では, A, B を固定して数え上げる方針だった.
Aを 1 ~ K まで動かすと, Bは 1 ~ K / A まで動き, その時の C は K / ( A * B ) 個ある.
計算量の見積もりは, 調和級数の考え方を用いると, O(KlogK)になることが分かる.

B問題 ( A ^ B ^ C )

概要

A ^ B ^ C % 10 を求める

方針

実際にシュミレーションして A ^ x % 10 の挙動を確認する.

A % 10	A ^ 2 % 10	A ^ 3 % 10	A ^ 4 % 10	...
0	0	0	0	0
1	1	1	1	1
2	4	8	6	2
3	9	1	3	9
4	6	4	6	4
5	5	5	5	5
6	6	6	6	6
7	9	3	1	7
8	4	2	6	8
9	1	9	1	9

上の表を見ると, A ^ x は周期4で循環していることが分かる.

つまり, A ^ (B ^ C % 4) % 10 を計算すれば良い.

b.py

print(pow(A, pow(B, C, 4) + 4, 10)

Pythonだとこのようにとても短く書くことができる.

b.py

pow(B, C, 4) + 4

ここで + 4 しているのは, 4 で割った余りが 0 のときは 余りが 4 であるとするためである.
このようにしないと, B ^ C % 4 が 0 のときに, A ^ (0) % 10 を求めることになり, 必ず 1 になってしまう.

C++ にはPythonのpow関数のようなものが無いので自分で作る必要がある.
二分累乗法 (参考:累乗a^n) を用いてmod_pow関数を実装する.
C++ での実装例は以下のようになる.

b.cpp

#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (long long i = 0; i < (n); i++)
using ll = long long;
using P = pair<ll, ll>;

// a^n % p を計算する関数
ll mod_pow(ll a, ll n, ll mod) {
    ll res = 1;
    // n を 2進数に変換して考える
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

int main() {
    ll a, b, c;
    cin >> a >> b >> c;
    cout << mod_pow(a, mod_pow(b, c, 4) + 4, 10) << endl;
} 

C問題 ( String Invasion )

概要

長さNの文字列Sに対し, S[ i ] == S[ i+1 ] != S[ i+2 ] のとき, S[ i+2 ] を S[ i ]に置き換えるという操作を最大で何回できるか求める

方針

文字列を後ろから見ると見通しが良くなるので, 文字列をリバースする.
リバースした文字列を頭から見ていって, X Y Y ( X と Y は異なる文字 )という文字列を見つけたら, X と, それ以前の文字列のうち X でないものを Y に置き換える.
つまり, X を S[ i ] とすると, X Y Y の文字列を見つけたら, 答えに + ( i + 1 - ( S[ 0 ] ~ S[ i-1 ] までで X でない文字の個数) すれば良い.
S[ 0 ] ~ S[ i-1 ] に出てきた文字は map などで保持しておくと良い.

C++ での実装例は以下のようになる.

c.cpp

#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (long long i = 0; i < (n); i++)
using ll = long long;
using P = pair<ll, ll>;

int main() {
    string s; cin >> s;
    reverse(s.begin(), s.end());
    ll ans = 0;
    map<char, ll> mp;
    for (ll i = 0; i < (ll)s.size()-2; i++) {
        mp[s[i]]++;
        if (s[i] != s[i+1] && s[i+1] == s[i+2]) {
            ll same = mp[s[i+1]];
            ans += i+1;
            ans -= same;
            map<char, ll> mp_new;
            swap(mp, mp_new);
            mp[s[i+1]] = i+1;
        }
    }
    cout << ans << endl;
}