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

#結果
ABCまでの3完で, レート変化は730→<font color="Maroon">796</font>(+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)より少ない？

```cpp: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 を計算すれば良い.

```python:b.py

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

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

```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](https://qiita.com/drken/items/3b4fdf0a78e7a138cd9a#4-%E7%B4%AF%E4%B9%97-an)) を用いてmod_pow関数を実装する.
C++ での実装例は以下のようになる.

```cpp: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++ での実装例は以下のようになる.

```cpp: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;
} 
```