AtCoder が提供しているABC（AtCoder Beginner Contest）341 のD問題をC++とPythonで解いてみました。ABC341は、2024年2月17日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
D問題 Only one of two（Difficulty : 829）
問題はリンク先をご覧ください。
解の二分探索で解くことができます。AtCoder Problems による Difficulty は 829 でした。
解答案
整数を値にとる以下の関数を考えます。$\lfloor a \rfloor$は、$a$ を整数に切り捨てた値を表します。$lcm(n, m)$ は、$n$ と $m$ の最小公倍数を表します。
$$f(number) = \left\lfloor \frac{number}{N} \right\rfloor + \left\lfloor \frac{number}{M} \right\rfloor\; -\; 2 \times \left\lfloor \frac{number}{lcm(N, M)} \right\rfloor$$
$f(number)$ は、$number$ が $N$ か $M$ で割り切れる場合、$N$ と $M$ のうち ちょうど一方のみ で割り切れる数を表します。意味から分かるように $f(number)$ は、単調に増加します。このため、$f(number)$ の値を二分探索することにより、$K$ を求めることができます。
二分探索では、最小となる境界の値を求めることができます。このため、求めた値は、$N$ と $M$ のうち ちょうど一方のみ で割り切れます。
解の単調性があり最小値を求めるため、「解の二分探索」が使えます。このブログでも何回も紹介しています。以下の2つを実装します。
- 関数 is_ok：条件を満たすか、満たさないか判断する
- 絶対に条件をみたす変数 ok と、条件を満たさない変数 ng を設定して、解の二分探索をする。このコードは、パターン化できている。
C++ プログラム例（ABC341D）
上記の方針で実装します。最小公倍数を求めるために最大公約数を求める関数 gcd を用意しました（8ー15行目）。
- 関数 is_ok
- 上記で紹介した関数 $f$ を実装します。
- ng = 0、ok = 1018 を設定します（31、32行目）。$1 \leqq N, M \leqq 10^8$、$1 \leqq K \leqq 10^{10}$ です。直感的に、$N (or \; M) \times K $ の定数倍が解の上限になることが分かります。厳密な証明は、公式解説で提示されています。
- 残りは定番コードです。これはほとんどの問題で使いまわせます（33ー40行目）。
以下が、C＋＋プログラムとなります。解の二分探索の定番コードの背景色を変更しました。
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll n, m, k, c;
ll gcd(ll a, ll b)
{
if (b == 0) {
return a;
} else {
return gcd(b, a % b);
}
}
bool is_OK(ll mid)
{
ll nd = mid / n;
ll md = mid / m;
ll cd = mid / c;
return nd + md - cd * 2 >= k;
}
int main()
{
cin >> n >> m >> k;
c = n / gcd(n, m) * m;
ll ng = 0;
ll ok = 1000000000000000000ULL;
while (abs(ok - ng) > 1) {
ll mid = (ok + ng) / 2;
if (is_OK(mid)) {
ok = mid;
} else {
ng = mid;
}
}
cout << ok << endl;
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC341D）
Python 版も基本的な考え方は同じです。最小公倍数を求めるために math.gcd を呼び出しています（2、16行目）。以下となります。
"""AtCoder Beginner Contest 341 D"""
import math
def is_OK(mid):
global n, m, c, k
nd = mid // n
md = mid // m
cd = mid // c
return nd + md - cd * 2 >= k
n, m, k = map(int, input().split())
c = n * m // math.gcd(n, m)
ng = 0
ok = 10 ** 18
while abs(ok - ng) > 1:
mid = (ok + ng) // 2
if is_OK(mid):
ok = mid
else:
ng = mid
print(ok)こちらも「AC」と判定されました。
最後に
コンテスト中は、関数 f に気づいていましたが、$N$ と $M$ の両方で割れない解がでる可能性があると誤解していました。解の単調性から、最小値は必ず $N$ と $M$ のどちらかで割れることは、コンテスト直後に気づきました。
結果的にくやしい問題となりましたが、学ぶことができました。
引き続き ABC の問題を紹介していきます。
