AtCoder が提供しているABC（AtCoder Beginner Contest）290 のD問題をC++とPythonで解いてみました。ABC290は、2023年2月19日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
D問題 Marking（Difficulty : 1036）
問題はリンク先をご覧ください。
最大公約数を求めて、法則に従い演算をして解答を求めることができます。AtCoder Problems による Difficulty は 1036 でした。
解答案
テストケース数
手順を繰り返すことなく解答を求める必要があります。高校で履修する数学Aで整数について学ぶと以下が分かります。
これは、入力例の後半
- 0 = 0 (mod 5)
- 1 × 8 = 8 = 3 (mod 5)
- 2 × 8 = 16 = 1 (mod 5)
- 3 × 8 = 24 = 4 (mod 5)
- 4 × 8 = 32 = 2 (mod 5)
次に
この場合は、入力例の前半
- 0 = 0 (mod 4)
- 1 × 2 = 2 = 2 (mod 4)
- 2 × 2 = 4 = 0 (mod 4) → 1 （1加える）
- 3 × 2 = 6 = 2 (mod 4) → 3 （1加える）
C++ プログラム例（ABC290D）
いままで考察した式をプログラムで表現します。最大公約数を求める関数 gcd を用意します。
以下が、C＋＋プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long int ull;
ull gcd(ull a, ull b)
{
if (b == 0ULL) {
return a;
} else {
return gcd(b, a % b);
}
}
int main()
{
int t;
cin >> t;
for (int i = 0; i < t; ++i) {
ull n, d, k;
cin >> n >> d >> k;
ull g = gcd(n, d);
if (g == 1) {
cout << ((k - 1) * d)% n << "\n";
} else {
ull temp1 = (k - 1)/(n / g);
ull temp2 = ((k - 1)%(n / g)) * d;
cout << (temp1 + temp2) % n << "\n";
}
}
return 0;
}実際のコンテスト中は、上記のプログラムを提出しました。
コンテスト後にプログラムを見直しました。互いに素な場合、
また、C++17 から最大公約数を求める gcd が使えるようになりました。現在のAtCoderの環境を調べると、以下のように C++17 が使えることが分かりました。
- g++: -std=gnu++17（C++17とGNU拡張に対応）
- clang: -std=c++17（C++17に準拠）
最後に式を簡潔に記すために、k の値を1減らし、中間的な変数 n2 を導入します。
この3点の工夫を盛り込んだプログラムは以下となります。プログラムがすっきりと書けています。
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long int ull;
int main()
{
int t;
cin >> t;
for (int i = 0; i < t; ++i) {
ull n, d, k;
cin >> n >> d >> k;
--k;
ull g = gcd(n, d);
ull n2 = n / g;
cout << (k / n2 + k % n2 * d) % n << "\n";
}
return 0;
}どちらも AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC290D）
Python では、最大公約数を求める gcd は、以下のように仕様が変わりました。
- Python 3.4 まで: fractions.gcd()
- Python 3.5 以降: math.gcd()
AtCoder の Python 環境は 3.8.2（2023年2月19日時点）なので、math.gcd() を使います。C++ の先に紹介したプログラムを書きなおしました。
"""AtCoder Beginner Contest 290 D"""
import math
t = int(input())
for _ in range(t):
n, d, k = map(int, input().split())
g = math.gcd(n, d)
if g == 1:
print((k - 1) * d % n)
else:
temp1 = (k - 1) // (n // g)
temp2 = (k - 1) % (n // g) * d
print((temp1 + temp2) % n)if 文を無くし、中間変数を導入した改良版は以下となります。
"""AtCoder Beginner Contest 290 D"""
import math
t = int(input())
for _ in range(t):
n, d, k = map(int, input().split())
k -= 1
g = math.gcd(n, d)
n2 = n // g
print((k // n2 + k % n2 * d) % n)どちらも「AC」と判定されました。
最後に
この問題は、わたしが解けた問題としては、Difficulty が高かったです。コンテスト後に公式解説やプログラムの見直しを行い、すっきりと書き直すことができました。このような活動で、アルゴリズムの理解度を深めていきたいです。
引き続き ABC の問題を紹介していきます。
