AtCoder

ABC336 C問題(Even Digits)を解く

AtCoder_ABC336_C

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

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

C問題 Even Digits(Difficulty : 343)

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

ABC336 C問題 Even Digits

5進数と考えると楽になります。AtCoder Problems による Difficulty は 343 でした。

解答案

制約が $1 \leqq N \leqq 10^{12}$ と大きいため、数字に含まれている桁が偶数だけか確認していては、間に合いません。

一方、登場する数字が、0、2、4、6、8 の5種類しかないため、5進数と考えると上手く行きます。

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

以下の関数を自作して持っていました。

関数 Kfrom10 の仕様(6ー18行目)

  • 整数 n と基数 k を与える。
  • 整数 n を k 進数表記した文字列を返す。

プログラム全体の補足をします。

  • 数字0を1番目とするため、入力 $n$ から1を引いて処理します(24行目)。
  • 5進数の数字を元の数字に戻す必要があります(30行目)。
     0→0、1→2、2→4、3→6、4→8

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

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

typedef unsigned long long int ull;

string Kfrom10(ull n, int k) {
	string result = "";

	while (n > 0) {
		result = (char)(n % k + '0') + result;
		n /= k;
	}
	if (result == "") {
		result = "0";
	}

	return result;
}

int main()
{
	ull n;
	cin >> n;
	--n;

	string s = Kfrom10(n, 5);

	string result;
	for (int i = 0; i < s.length(); ++i) {
		result += (s[i] - '0') * 2 + '0';
	}

	cout << result << endl;

	return 0;
}

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

Python プログラム例(ABC336C)

Python 版も基本的な考え方は同じです。以下となります。

"""AtCoder Beginner Contest 336 C"""


def Kfrom10(n, k):
    result = ""

    while n > 0:
        result = chr((n % k) + ord('0')) + result
        n //= k
    if result == "":
        result = "0"

    return result


n = int(input()) - 1

s = Kfrom10(n, 5)

result = ""
for _, ch in enumerate(s):
    result += chr((ord(ch) - ord('0')) * 2 + ord('0'))

print(result)

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

最後に

コンテストでは、AからC問題のACを 9分17秒でもらうことができました。わたくしにとっては、非常に速かったです。自作ライブラリの整備は、速解きには有効であると感じました。

引き続き ABC の問題を紹介していきます。

COMMENT

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

CAPTCHA