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

#結果
ABまでの2完で, レート変化は796→<font color="Maroon">747</font>(-49)

#[A問題](https://atcoder.jp/contests/abc193/tasks/abc193_a) ( Discount )
###概要
> 定価 A 円の商品が B 円で販売されているときの割引率を求める

###方針
A * (1 - 割引率 * 0.01) = B を変形すると, 割引率 = 100 * (1 - B / A )となる.

C++ での実装例は以下のようになる.
誤差が10^(-2)まで許されるので, 小数点以下3桁回答すれば十分.

```cpp:a.cpp
#include <bits/stdc++.h>
using namespace std;

int main() {
    double a, b; cin >> a >> b;
    printf("%.3f", 100 * (1 - b/a));

} 
```

#[B問題](https://atcoder.jp/contests/abc193/tasks/abc193_b) ( Play Snuke )
###概要
> 現在地からA [ i ] 分で行ける場所に, P [ i ] 円で商品が X [ i ] 個販売されている. ただし, ( 0.5 + n ) 分に1個ずつ売れていく. このとき, 最も安くで買える価格を求める.

### 方針
A [ i ] = X [ i ] のとき, ギリギリ買うことができない. ( 例えば, A = 3, X = 3 のとき, 0.5, 1.5, 2.5分後に1個ずつ売れるので, 3分後には全て売り切れている.) 逆に, A [ i ] < X [ i ] のときは, ギリギリ買うことができる. よって, A [ i ] < X [ i ] を満たす P [ i ] の最小値を求めれば良い. 条件を満たす P を配列に入れて, ソートすれば最小の P を取り出すことができる.

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;

int main() {
    ll n; cin >> n;
    vector<ll> price;
    rep(i, n) {
        ll a, p, x; cin >> a >> p >> x;
        if (a < x) price.push_back(p);
    }  
    sort(price.begin(), price.end());
    // priceのサイズが0のときは, a < x を満たすものがないということなので -1 を出力する
    if ((ll)price.size() != 0) cout << price[0] << endl;
    else cout << -1 << endl;
} 
```

###公式解説
公式解説では最小値を更新していくという方針だった. こっちの方が計算量が O ( N ) で済むので良い. ソートすると計算量は O ( N log N ) かかってしまう. ただし, B 問題で計算量を気にしないといけない問題はあんまり無い気がする.




#[C問題](https://atcoder.jp/contests/abc193/tasks/abc193_c) ( Unexpressed )
###概要
> N 以下の整数のうち, a ^ b ( a, b は2以上の整数 ) で表すことができないものの数を求める

### 方針
a を 2 ~ √N まで全探索し, a を素因数分解したときに, 

* 素因数の累乗の部分が全て偶数であればその数は X ^ ( 2 * k ) と表されるので飛ばす
* 素因数の数が 1 つで, 累乗の部分が 2 以上であれば飛ばす ( 例 ) 3 ^ 2 ( = 9 )
* 全ての素因数の累乗の部分が等しければ飛ばす ( 例 ) 2 ^ 3 * 3 ^ 3 ( = 216 ) 

それ以外の場合は, n を a で何回割ることができるのか計算する.

という方針でやったが, とても遠回りな上に, 2 ^ 6 * 3 ^ 4 などのケースを漏らしているのでダメだった. 4 の累乗 や 9 の累乗などのをダブルカウントしないように工夫したが, set に入れれば解決だった.

a ^ b の形で表すことのできる数は種類が少ないので, 普通に難しいことをせずに set に入れて行って, 最後に set のサイズを N から引けばできる.

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;

int main() {
    ll n; cin >> n;
    set<ll> S;
    for (ll i = 2; i*i <= n; i++) {
        ll t = i * i;
        while (t <= n) {
            S.insert(t);
            t *= i;
        }
    }
    cout << n - (ll)S.size() << endl;
    return 0;
} 
```

###公式解説
解説では unordered_set を使っていた.

set には以下の特徴がある.

* 配列の中に出現する値の種類数（重複の無い集合の要素数）を求めることができる
* 集合の中にある値が含まれるかを高速に計算できる
* 集合の中に含まれる最小値（最大値）を求めることだできる
* ループでは小さい順に取り出される

それに比べて unordered_set は, 

* ループで取り出すときに、どのような順番で取り出されるかが分からない
* 最大値や最小値を取り出すことができない

などの弱点があるが, 今回のような要素の種類数を取得することだけが目的の場合は set よりも高速である.

( 参考： [APG4b](https://atcoder.jp/contests/apg4b/tasks/APG4b_aa?lang=ja) )

###追記
やろうとした方針を実装するためには, a を素因数分解したときに, 全ての素因数の累乗の部分の最大公約数が 1 じゃない場合は飛ばすという方針だと解けた. 仮に最大公約数 ( g ) が 1 でないと仮定すると, x ^ g = a となる x が存在するので, 飛ばさなければならない.
実際の実装は以下のようになる.

```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>;

// 最大公約数を計算する関数
ll gcd(ll x, ll y) {
    if (x < y) swap(x, y);
    if(x % y == 0) return y;
    else return gcd(y, x % y); 
}
 
// n を素因数分解して, {素因数, 累乗} の形のPairを配列にして求め, 
//累乗の部分の最大公約数が1かどうか判断する関数
bool prime_factorize(ll n) {
    vector<P> res;
    for (ll a = 2; a * a <= n; a++) {
        if (n % a != 0) continue;
        ll ex = 0; // 指数
 
        // 割れる限り割り続ける
        while (n % a == 0) {
            ++ex;
            n /= a;
        }
 
        // その結果を push
        res.push_back({a, ex});
    }
 
    // 最後に残った数について
    if (n != 1) res.push_back({n, 1});
 
    bool ok = true;
    ll g = res[0].second;
    for (auto i : res) {
        g = gcd(g, i.second);
    }
    if (g != 1) ok = false;
    return ok;
}
 
int main() {
    ll n; cin >> n;
    ll ans = n;
    for (ll i = 2; i*i <= n; i++) {
        ll t = i * i;
        // 全ての素因数の累乗部分の最大公約数が1でない場合は飛ばす
        if (!prime_factorize(i)) continue;
        while (t <= n) {
            ans--;
            t *= i;
        }
    }
    cout << ans << endl;
    return 0;
} 
```