AtCoder

ABC290 D問題(Marking)を解く

AtCoder_ABC290_D

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

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

D問題 Marking(Difficulty : 1036)

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

ABC290 D問題 Marking

最大公約数を求めて、法則に従い演算をして解答を求めることができます。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$ は、すべて異なる。(「互いに素」とは、最大公約数が 1 であることと同値です。)

これは、入力例の後半 $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 に挑戦して、解説記事を書いていきます。

COMMENT

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

CAPTCHA