AtCoder が提供しているABC（AtCoder Beginner Contest）296 のD問題をC++とPythonで解いてみました。ABC296は、2023年4月1日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
D問題 M<=ab（Difficulty : 999）
問題はリンク先をご覧ください。
掛け算についての問題ですが、探索範囲に工夫が必要です。AtCoder Problems による Difficulty は 999 でした。
解答案
C++ プログラム例（ABC296D）
変数
以下が、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」と判定されました。
最後に
この問題は、なにかのアルゴリズムを活用して解くわけではありません。計算が持つ意味から、探索範囲を狭くすることができました。
引き続き ABC の問題を紹介していきます。
