Mister雑記

競プロ記事がメインになりますが、内容は気分次第です。

ABC114 解説

※各問題名は表記ミスではありません。

beta.atcoder.jp

目次

A. 753 (100)

beta.atcoder.jp

概要

 X歳の高橋くんが七五三で祝われる(つまり7歳、5歳、3歳のいずれかである)かどうかを判定せよ。

制約

  •  1 \leq X \leq 9

解説

if文なり3項演算子で言われた通りに判定をする。or演算子を上手く使いたいところ。

実装例

#include <iostream>

using namespace std;

int main() {
    int X;
    cin >> X;
    if (X == 3 || X == 5 || X == 7) {
        cout << "YES" << endl;
    } else {
        cout << "NO" << endl;
    }
    return 0;
}

あるいは3項演算子を使うと以下のようになる。

#include <iostream>

using namespace std;

int main() {
    int X;
    cin >> X;
    cout << (X == 3 || X == 5 || X == 7 ? "YES" : "NO") << endl;
    return 0;
}

B. 754 (200)

beta.atcoder.jp

概要

各桁が 1 \sim 9からなる文字列 Sが与えられる。

 Sから連続する3桁を取り出し、それと 753との差の絶対値を取ることを考える。

この絶対値の最小値を求めよ。

制約

  •  4 \leq |S| \leq 10

解説

考えうる全ての部分列について、それと753との差の絶対値を実際に計算する。

部分列を取る方法は色々ある。Pythonならスライスを使えば簡単なのだが、C++にはスライスはない。

そこで便利なのがsubstr関数。始点のindexと長さを引数として与えれば、簡単に部分文字列を求めることができる。ただし使うには#include<string>をしなくてはいけないので注意。

実装例

#include <cmath>
#include <iostream>
#include <string>

using namespace std;

int main() {
    string S;
    cin >> S;

    int ans = 1000;
    for (int i = 0; i < S.size() - 2; ++i) {
        // substrでi文字目から始まる長さ3の部分列を抽出
        // それをstoiで整数に変換
        int diff = 753 - stoi(S.substr(i, 3));

        // 最小値を更新
        ans = min(ans, abs(diff));
    }
    cout << ans << endl;
    return 0;
}

無論解が求まればば何でも良いので、絶対substrを使わなくてはならないわけではない。ただ存在だけでも覚えておくといざというときに役立つだろう。

C. 755 (300)

beta.atcoder.jp

概要

10進法表記したときに 7 5 3が最低1回ずつ現れ、他の数字が現れないような数を七五三数と呼ぶことにする。

このとき 1以上 N以下の七五三数はいくつあるか求めよ。

制約

  •  1 \leq N \leq 10^9

解説

まず考えられるのは 1から Nまで全部判定する方法。しかし Nが大きすぎてあまり現実的ではない。

桁DPも考えられるが、C問題にしては高度すぎるし何より実装したくない。

そこで逆に七五三数を全列挙することを考える。サンプル3を見れば分かるのだが、実は七五三数というのは結構少なくて十分全列挙できる。

と言うのは簡単だが、全列挙するのはそこまで簡単ではない。私は以下のように実装した。

  1. 桁数 d 3から 9まで回す。
  2.  b 0から 3^d - 1まで回す。
  3.  bを3進数表記したときの i桁目を 7 5 3に対応させて、長さ d 7 5 3のみからなる数を作る。
  4.  7 5 3が出現したかをチェックして、一度も出てこないものがあったらその数はパスする。
  5. その数が N以下なら答えをインクリメントする。

3について補足しておく。例えば b = 57のとき、 bを3進数表記すると 2010となるので 0 \rightarrow 7 1 \rightarrow 5 2 \rightarrow 3と対応させることで 3757が作れる。

実装例

上の手順の3なのだが、以下の実装例では bを3進数表記して反転させたのちに変換したことになっている。どちらにせよ全列挙はできるので問題はない。

あとmypow関数は普段から持っているテンプレートで、その場で実装した訳ではない。

#include <iostream>
#include <map>
#include <string>

using namespace std;

// b^nを計算する関数
int mypow(int b, int n) {
    if (n == 0) return 1;
    if (n == 1) return b;
    if (n % 2 == 0) {
        return mypow(b * b, n / 2);
    } else {
        return mypow(b, n - 1) * b;
    }
}

// 012と753を変換する変数
const string i2c = "753";
const map<char, int> c2i = {{'7', 0}, {'5', 1}, {'3', 2}};

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

    int ans = 0;

    // dは桁数
    for (int d = 3; d < 10; ++d) {
        for (int b = 0; b < mypow(3, d); ++b) {
            string S;

            int cb = b;
            // 1の位から753に変換してpushしていく
            for (int i = 0; i < d; ++i) {
                S.push_back(i2c[cb % 3]);
                cb /= 3;
            }

            // 7, 5, 3の出現回数を数える
            bool cnt[3];
            fill(cnt, cnt + 3, false);

            for (char c : S) {
                cnt[c2i[c]] = true;
            }

            bool judge = true;
            for (int i = 0; i < 3; ++i) {
                if (!cnt[i]) judge = false;
            }
            if (!judge) continue;

            // N以下ならカウントする
            if (stoi(S) <= N) ++ans;
        }
    }
    cout << ans << endl;
    return 0;
}

大分長い実装になってしまった、実際300にしては難しいと思う。あるいはもっとスマートに実装する方法があるのだろうか。

D. 756 (400)

beta.atcoder.jp

概要

正の約数をちょうど 75個もつ正整数を七五数と呼ぶことにする。

 N!の約数で七五数であるものの個数を求めよ。

制約

  •  1 \leq N \leq 100

解説

まずは正の約数の個数に関する知識が必要となる。

ある正整数 N素因数分解したら N = {p_1}^{a_1} {p_2}^{a_2} \cdots {p_m}^{a_m}と表せたとする( p_iは互いに異なる素数)。 このとき Nの正の約数の個数は (a_1 + 1) (a_2 + 1) \cdots (a_m + 1)で求められる。この解説は偉大なる高校数学の美しい物語様に投げさせていただく。

 75 = 3 \cdot 5^2 (a_1 + 1) (a_2 + 1) \cdots (a_m + 1)の形で表すことを考えると、七五数は以下の4パターンしかない事が分かる。

  •  p^{74}
  •  p^2 q^{24}
  •  p^4 q^{14}
  •  p^2 q^4 r^4

したがって N!素因数分解して、 p,q,rを全パターン調べると答えが分かる。  100以下の素数の数は25個なので、パターン数は 25^3 = 15625程度になって余裕で間に合う。

ただし p^2 q^4 r^4のパターンは注意が必要で、 q rで重複して数えてしまうことがある。これは q \lt rとすることで防げる。

実装例

エラトステネスの篩を実装するのが面倒だったので、ネットから引っ張ってきた素数一覧をそのままコピペしている。

#include <iostream>

using namespace std;

// 100以下の素数一覧
const int prime[25] = {
    2, 3, 5, 7, 11,
    13, 17, 19, 23, 29,
    31, 37, 41, 43, 47,
    53, 59, 61, 67, 71,
    73, 79, 83, 89, 97};

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

    int cnt[25];
    fill(cnt, cnt + 25, 0);
    // cnt[i] = N!を素因数分解したときのprime[i]の指数

    for (int n = 1; n <= N; ++n) {
        int m = n;

        // mを素因数分解する
        for (int i = 0; i < 25; ++i) {
            while (m % prime[i] == 0) {
                ++cnt[i];
                m /= prime[i];
            }
        }
    }

    int ans = 0;

    // p^74の形
    for (int p = 0; p < 25; ++p) {
        if (cnt[p] >= 74) ++ans;
    }

    // p^2 q^24とp^4 q^14の形
    for (int p = 0; p < 25; ++p) {
        for (int q = 0; q < 25; ++q) {
            if (p == q) continue;
            if (cnt[p] >= 4 && cnt[q] >= 14) ++ans;
            if (cnt[p] >= 2 && cnt[q] >= 24) ++ans;
        }
    }

    // p^2 q^4 r^4の形
    for (int p = 0; p < 25; ++p) {
        for (int q = 0; q < 25; ++q) {
            // 重複カウントを防ぐためにq < rにしている
            for (int r = q + 1; r < 25; ++r) {
                if (p == q || r == p) continue;
                if (cnt[p] >= 2 && cnt[q] >= 4 && cnt[r] >= 4) ++ans;
            }
        }
    }

    cout << ans << endl;
    return 0;
}

数学が得意な人なら多分Cよりも簡単な一方、約数の個数の性質を知らないと詰むというとても数学寄りな問題。

感想

  • Dで最初 p^2 q^4 r^4しか頭に無かったのが情けない。
  • 全体的にABCらしい難易度だと思った。
  • 最初「AtCoderがついに問題名を誤植したか......」と思いませんでしたか?私は思いました。