AtCoder が提供しているABC（AtCoder Beginner Contest）290 のD問題をC++とPythonで解いてみました。ABC290は、2023年2月19日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
D問題 Marking（Difficulty : 1036）
問題はリンク先をご覧ください。
最大公約数を求めて、法則に従い演算をして解答を求めることができます。AtCoder Problems による Difficulty は 1036 でした。
解答案
テストケース数 $T$ の制約が $1 \leqq T \leqq 10^5$ です。ひとつのテストケースで手順を $N\, -\, 1$ 回（ $1 \leqq N \leqq 10^9$ ）繰り返すことは、計算量的に明らかに難しいです。
手順を繰り返すことなく解答を求める必要があります。高校で履修する数学Aで整数について学ぶと以下が分かります。
$N$ と $D$ が互いに素な場合、$N$ を法とすると、$D, 2 \times D, \dots, (N\, – \, 1) \times D$ は、すべて異なる。（「互いに素」とは、最大公約数が １ であることと同値です。）
これは、入力例の後半 $N = 5, D = 8$ の場合に相当します。確かめてみます。
- 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)
$K = 0, 1, 2, 3, 4$ に対して、$N$ 未満の $0, 3, 1, 4, 2$ がすべて現れます。
$N$ と $D$ が互いに素な場合 $K$ 番目の値は、$(K – 1) \times D \pmod{N}$ となります。
次に $N$ と $D$ が互いに素ではない場合がを考えます。ここで、$N$ と $D$ の最大公約数を $g (\neq 1)$ とします。この場合は、$D \times (N / g)$ は、0 に戻ります。0 に戻った回数だけ 1 加えられます。
この場合は、入力例の前半 $N = 4, D = 2$ の場合に相当します。$g = 2$ となります。確かめてみます。
- 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加える）
$N$ と $D$ が互いに素な場合でも、素でない場合でも、式によって $K$ 番目の値を求めることができました。
C++ プログラム例（ABC290D）
いままで考察した式をプログラムで表現します。最大公約数を求める関数 gcd を用意します。$N$ と $D$ が互いに素ではない場合は、0 になる回数を変数 temp1、0 からの距離を変数 temp2 に格納します。
以下が、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;
}実際のコンテスト中は、上記のプログラムを提出しました。
コンテスト後にプログラムを見直しました。互いに素な場合、$g = 1$ となります。この場合、互いに素でない場合の式に $g = 1$ を入れると、if 文本体の式と一致することが分かります。結果的に else 節だけで処理をすることができます。
また、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 の問題を紹介していきます。
