AtCoder

ABC296 D問題(M<=ab)を解く

AtCoder_ABC296_D

AtCoder が提供しているABC(AtCoder Beginner Contest)296 のD問題をC++とPythonで解いてみました。ABC296は、2023年4月1日21:00に実施されました。

AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。

D問題 M<=ab(Difficulty : 999)

問題はリンク先をご覧ください。

ABC296 D問題 M<=ab

掛け算についての問題ですが、探索範囲に工夫が必要です。AtCoder Problems による Difficulty は 999 でした。

解答案

$a \leqq b \; (\leqq N)$ と考えても答えは変わりません。これは、問題の条件を満たす $a$ と $b$ に対して、大きくない方を $a$ として、残りを $b$ と置き換えればよいからです。

$a$ に対して、$b = M / a$ または $b = M / a + 1$ とします。$1 \leqq a \leqq \sqrt{M}$ の範囲で、$a \times b$ の $M$ 以上の最小値を調べれば十分な範囲の探索となります。

$M$ の上限は $10^{12}$ ですが、$\sqrt{M} = 10^6$ まで調べればよいため、計算量的には間に合います。

C++ プログラム例(ABC296D)

変数 $r = \sqrt{M}$ として、$1 \leqq a \leqq r + 1$ に対して、上記の方針で調べます。変数 result の初期値を十分大きくしておいて、そのままの値であれば、$-1$ を出力します。 $r + 1$ まで調べているのは、浮動小数点数の誤差を考慮して、念のため 1 多くしています。

以下が、C++プログラムとなります。

#include <bits/stdc++.h>
using namespace std;

typedef long long int ll;
#define INF (1LL << 60)

int main()
{
	ll n, m;
	cin >> n >> m;

	ll r = (ll)(sqrt(m) + 0.5);

	ll result = INF;
	for (ll a = 1; a <= r + 1; ++a) {
		ll b1 = m / a;
		ll b2 = m / a + 1;
		if ((a <= n)&&(b1 <= n)&&(a * b1 >= m)) {
			result = min(result, a * b1);
		}
		if ((a <= n)&&(b2 <= n)&&(a * b2 >= m)) {
			result = min(result, a * b2);
		}
	}

	if (result == INF) {
		cout << -1 << endl;
	} else {
		cout << result << endl;
	}

	return 0;
}

AC(Accepted=正しいプログラム)と判定されました。

Python プログラム例(ABC296D)

Python も、C++ 版をそのまま移植しました。

"""AtCoder Beginner Contest 296 D"""
import math

INF = 1 << 60
n, m = map(int, input().split())
r = int(math.sqrt(m) + 0.5)

result = INF
for a in range(1, r + 2):
    b1 = m // a
    b2 = m // a + 1
    if a <= n and b1 <= n and a * b1 >= m:
        result = min(result, a * b1)
    if a <= n and b2 <= n and a * b2 >= m:
        result = min(result, a * b2)

print(-1 if result == INF else result)

こちらも「AC」と判定されました。

最後に

この問題は、なにかのアルゴリズムを活用して解くわけではありません。計算が持つ意味から、探索範囲を狭くすることができました。

ABC296 について、引き続き、E問題まで紹介します。

COMMENT

メールアドレスが公開されることはありません。 が付いている欄は必須項目です

CAPTCHA