ABC302 A問題（Attack）を解く

AtCoder が提供しているABC（AtCoder Beginner Contest）302 のA問題をC++とPythonで解いてみました。ABC302は、2023年5月20日21:00に実施されました。

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

A問題 Attack（Difficulty : 24）

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

ABC302 A問題 Attack

割り算の切上げ結果を求める問題です。AtCoder Problems による Difficulty は 24 でした。

解答案

C++ プログラム例（ABC302A）

A から B を引いていきますが、引いた結果が少しでも残っていれば、もう1回余分に攻撃が必要になります。必要な攻撃回数を条件文で実現しました（12-16行目）。

注意としては、A と B の上限は、10¹⁸ となっており、32ビット整数の範囲を超えています。このため、整数の型は、unsigned long long 型としました（4、8行目）。整数の大きさについては、この記事で紹介しています。

以下が、C＋＋プログラムとなります。

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

typedef unsigned long long int ull;

int main()
{
	ull a, b;
	cin >> a >> b;

	ull result;
	if (a % b == 0) {
		result = a / b;
	} else {
		result = a / b + 1;
	}

	cout << result << endl;

	return 0;
}

結果的に割り算の切り上げた結果を求めています。上のプログラムでは条件文を使って切上げの計算をしました。次の切上げ結果の公式を使うと、条件文がなくても、切上げ計算ができます。割り算は切下げである前提です。

$$\left\lceil \frac{a}{b} \right\rceil = (a + b \,-\, 1) / b$$

$\lceil x \rceil$ は、$x$ の切上げを表します。この公式を使ったプログラムは以下となります。

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

typedef unsigned long long int ull;

int main()
{
	ull a, b;
	cin >> a >> b;

	cout << (a + b - 1)/ b << endl;

	return 0;
}

どちらも AC（Accepted＝正しいプログラム）と判定されました。

Python プログラム例（ABC302A）

Python の整数は大きさに制限がありません。そのため、すっきりと書けています。計算は、切上げの公式を使いました。

"""AtCoder Beginner Contest 302 A"""
a, b = map(int, input().split())
print((a + b - 1) // b)

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

最後に

問題自体は簡単になっていましたが、64ビット整数が必要でした。A問題では、初めて出題されたかもしれません。これからも64ビット整数が必要なA問題が出題されるかもしれません。

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