【競プロ精進ログ】【2021/03/03】ABC169:C, D

競技プログラミングのための精進履歴をブログ形式で残していきます。

目標は AtCoder 水色！
今のレートは茶色です。

本日の精進ツリーは以下のとおり。

精進ツリー

ABC169: C – Multiplication 3
ABC169: D – Div Game
まとめ

ABC169: C – Multiplication 3

ABC169 より、 C – Multiplication 3を解きました。
難易度は茶色。

普通に A と B の積を取って整数キャスト！
ではダメなことまではすぐにわかりました。

とりあえずキャスト時の誤差を避けるために B をまず100倍して整数化するのと合わせて、積の下2桁を削除する際も除算を使わず文字列キャストを使いました。

にもかかわらず、 1 WA が突破できず…。
しばらく悩んでも答えがでなかったので解説をみたところ、B を 100 倍する際に、「計算機イプシロン」の考慮が必要だった模様。

「計算機イプシロン」とは、「浮動小数点数において、「1より大きい最小の数」と1との差のこと」らしいです。
計算機イプシロン – Wikipedia

この説明だと何のことかわからなかったのですが、要するに機械計算における浮動小数点は、数学のように厳密な小数ではないことに起因しているようです。
※ 間違ってたらごめんなさい。

そのため、下の写真のように、浮動小数点型の値を倍算した場合、想定と違う解になる場合があり、これが誤差となって現れます。

うっわまじじゃん。
全然知らなかった。
こっわ。 pic.twitter.com/z4AYYT3eEn
— かしわば (@yuki_kashiwaba) March 3, 2021

回避方法としては次の方法があるようですが、今回は文字列化を選択しました。

・計算機イプシロン分の微小値を加算する
・文字列にして数を操作する

提出コードはこちら。

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define SIZE_OF_ARRAY(array) (sizeof(array) / sizeof(array[0]))
using namespace std;

#define MAX 100010
#define NIL -1

using lint = long long int;
using P = pair<lint, lint>;

/*************************************************************************************
NOTE: 

・小数点切り捨て問題
・B は小数 2 位までとのことなので、事前に 100 倍しておけば誤差がでなさそう
・コーナーケースがわからん

以下解説参照
・「double 型には 15〜16 桁程度の精度しかない」ことが問題
A の有効数字は 15 桁、B の有効数字は 3 桁なので、A×B の計算には、18 桁程度の有効数字が必要

解法としては、double より大きい有効数字をもつ long double を使うか、先に掛け算をして誤差を削除する

*************************************************************************************/

/*************************************************************************************
LOGIC: 

1. B を 100倍する
2. A * B の下 2桁を削除する
3. 文字列にして下 2桁のあるなしの場合分け
// ここまでで 1 WA

どうやら上の流れではだめで、次の流れにしないといけなさそう
1. B を文字列にして小数点を削除(100倍した時と同じ)
2. A * B を計算
3. 計算結果を文字列にして下 2 桁を削除
*************************************************************************************/

int main()
{
    lint A;
    double  B;
    cin >> A >> B;

    string S;
    S = to_string(B);
    string SB = "";
    for (int i = 0; i < S.length(); i++)
    {
        if (S[i] == '.')
        {
            SB += S[i + 1];
            SB += S[i + 2];
            break;
        }
        SB += S[i];
    }

    lint tmp = A * stoi(SB);
    string T = to_string(tmp);
    if (tmp > 99)
    {
        for (int i = 0; i < T.length() - 2; i++)
        {
            cout << T[i];
        }
        cout << endl;
    }
    else
    {
        cout << 0 << endl;
    }
    
    return 0;
}

ABC169: D – Div Game

ABC169 より、 D – Div Gameを解きました。
難易度は茶色。

普通に解けなかったです。
茶色Diff 難しい。。

始めは N の約数を列挙して、その中から素数と素数のべき数を判別しようと考えてました。
結果的にはそれでは上手くいかないことがわかりました。(素因数が取れないため)

その後の方針として、Nの素因数を洗い出し、各素数ごとの数をカウントすることで解く方法にシフトしました。
素因数の列挙には、O(NlogN)のエラストテネスの篩の実装で対応しようとしたのですが、一部 TLE になりました。

AtCoder 版！マスター・オブ・整数 (素因数分解編) – Qiita

また、過去の提出コードを参考にして実装したのですが、vectorにpair型をpush_backしようとするとコンパイルエラーが返ってきました。

解消方法として、コンストラクタの引数から直接コンテナオブジェクトを生成できる emplace_back を使います。

詳しくはこちらが参考になりました。

push_backとemplace_back – Qiita

提出コードはこちら。


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

/*************************************************************************************
NOTE: 

・Zは
  1. 任意の素数の e乗
  2. N の約数
  3. まだ選んでない

・最大で何回操作できるか、ということはDPか？
  → 違う気がする
  → N の約数のうちの素数のべき乗の順列でいいのでは？
  → 順列にする必要すらなく(小さい順に選べばいいので)
    Nの約数のうちの素数のべき乗の個数

・N の最大値は10^12
・素数のべき乗判定をするには、
  ・重複無しの約数が2つ(素数)
  ・その素数の繰り返しで割り切れる = 素数のべき乗
  ・素数のべき乗バケットを作りたいけど、要素数10^12だとオーバーフローする

↓

・N の約数ではなく、素因数分解を考える
・各素因数について、連続した個数で処理の数が求められる
  例: N = 16 : 素因数 2 2 2  : 取りうる Z  2 / 4  2 つ
*************************************************************************************/

/*************************************************************************************
LOGIC: 
1. N の素因数を洗い出す O(logN)
2. Nの素因数のうち、同じ素数をカウントする
3. 抜き出した要素の1, 2, 3, 4 ... 個ごとの回数操作ができる
*************************************************************************************/

lint get_ans(lint tmp, lint p)
{
    lint a = 0; lint i = 1; lint j = 0;

    while (p > 0)
    {
        p--; j++;
        if (i == j)
        {
            a++; j = 0; i++;
        }
    }

    return a;
}

int main()
{
    lint N;
    cin >> N;

    vector<pair<lint, lint>> A;
    for (lint i = 2; i * i <= N; i++)
    {
        if (N % i == 0)
        {
            lint cnt = 0;
            while (N % i == 0)
            {
                N /= i;
                cnt++;
            }
            A.emplace_back(i, cnt);
        }
    }

    if (N != 1)
        A.emplace_back(N, 1);

    lint ans = 0;
    for (auto a : A)
    {
        ans += get_ans(a.first, a.second);
    }

    cout << ans;
}