OMC021 プログラミングを用いた解法

はじめに

数学コンテストサイト「OnlineMathContest」の「OMC021 (for beginners)」において、B, C問題を解く際に、プログラミング (Python) を利用しました。
そのコードと解法・解説を記載します。
(コンテスト終了後に、より良さそうな方法やより分かりやすそうな記法などを発見した場合には、そちらを記載しています。)

OMC021 (for beginners)
https://onlinemathcontest.com/contests/omc021

注意: 2021年8月より、OnlineMathContest のコンテストでは、プログラミングを含む外部ツールの使用が禁止される予定ですので、ご注意ください。
(本記事は、外部ツールの使用が許可されていたコンテストについてのものです。)

B問題

問題
https://onlinemathcontest.com/contests/omc021/tasks/131

最小公倍数が $10^{10} = 2^{10} 5^{10}$ であることより、 $a, b$ はどちらも $10^{10}$ 以下であり、かつ $2, 5$ 以外の素因数をもっていてはいけないことがわかります。
よって $a, b$ は、それぞれ $2^p 5^q ; (0≦p, q≦10)$ と表すことができます。
ここからさらに考察を進められますが、この時点で、プログラミングを使った $11^4$ 通りの全探索をすることでも解けます。
最小公倍数は $\mathrm{lcm}(a, b) = \frac{a \times b}{\mathrm{gcd}(a, b)}$ という公式より、math.gcdを利用して求められます。
(Python 3.9からmath.lcmが使えるようですが、2021年3月時点で競技プログラミングなどの環境では対応していないものがあります。)

from math import gcd

A = [2**i for i in range(11)]
B = [5**i for i in range(11)]
n = 10**10

ans = 0
for i in range(len(A)):
    for j in range(len(B)):
        for k in range(len(A)):
            for l in range(len(B)):
                a = A[i] * B[j]
                b = A[k] * B[l]
                lcm = (a * b) // gcd(a, b)
                if a <= b and lcm == n:
                    ans += 1

print(ans)

C問題

問題
https://onlinemathcontest.com/contests/omc021/tasks/132

コインのすべての出方は $2^{10} = 1024$ 通りなので、全パターンについて $3$ 回連続で表または裏が出ることがあるかをプログラミングで (計算時間的に) 十分早く求められます。
各パターンを「表表裏表裏裏裏表裏表」のように表記し、表を $0$ 、裏を $1$ に置き換えると、全 $1024$ パターンを $0$ ～ $1023$ を表す $2$ 進数 ( $0$ 埋めをして $10$ 桁になるようにしたもの) で表すことができます。
このとき、「表/裏が $3$ 回続くこと」は「 $2$ 進数の文字列内に $000$ / $111$ が登場すること」と言い換えられます。
条件を満たすパターン数が求まったら、最後に約分を行います。全パターン数 (＝分母) が $2$ の $10$ 乗なので ( $2$ 以外の素因数をもたないので) 、 $2$ で約分できるかだけを確認すれば大丈夫です。

n = 10
ans = 0
for i in range(2**n):
    ib = format(i, "b").zfill(n)  # 例えばi=5ならば、ibは「0000000101」という文字列になる
    ng = False
    for j in range(n):
        if ib[j : j+3] in ("000", "111"):  # 3回連続で同じ面が出ていたら
            ng = True
    if not ng:
        ans += 1

den = 2**10  # 分母
while den % 2 == 0 and ans % 2 == 0:  # 可能な限り2で約分する
    ans //= 2
    den //= 2

print(ans, den, ans + den)

Pythonでは整数 $i$ について「format(i, "b")」と書くことで $2$ 進数に変換できます (bはたぶんbinary (2進数) の略です) 。
zfillでゼロ埋めを行っており、例えば $i=5$ ならば、ibは「0000000101」という文字列になります。
$3$ 連続で同じ面が出た時点でngがTrueになり、答えのカウントからは除外されます。
分母は英語で「denominator」というらしいので、「den」という変数名にしています (私は本番では別の変数名でやりました) 。
「ans + den」の値が、最終的な答えとなります。