公式

B - AtCoder Condominium 解説 by mechanicalpenciI


\(i\)\(j\) 号室の部屋番号を \(3\) 桁の整数とみなしたときその数は \(100i+j\) と書く事が出来ます。 これを \(2\) 重のfor文によって足し合わせてあげればよいです。 \(1000\) 未満の数を高々 \(81\) 個足し合わせるだけなので答えは明らかに \(32\) bit 整数の範囲に収まります。

実際には具体的にこの値を式で書く事が出き、 \(100i\)\(j\) ごとに足し合わせることを考えると

\[ 100(1+2+\cdots +N)\times K+(1+2+\cdots +K)\times N=\frac{NK\{100(N+1)+(K+1)\}}{2} \]

と求めることもできます。
この方法でやる際は先に分子を計算してから \(2\) で割らないと値がずれてしまう可能性がある事に注意してください。 例えば、 \(\frac{NK}{2}\)を先に整数型で計算してしまうと、 \(N\), \(K\) がともに奇数のときに切り捨てによって値がずれてしまいます。

以下の実装例は \(1\) つめの方針による実装です。

C++による実装例:

#include<bits/stdc++.h>

using namespace std;

int main(void) {
	int n, k;
	int s = 0;
	cin >> n >> k;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= k; j++) {
			s += (100 * i + j);
		}
	}
	cout << s << endl;
	return 0;
}

Pythonによる実装例:

n, k = map(int, input().split())
s = 0
for i in range(1,n+1):
    for j in range(1,k+1):
        s += (100*i)+j
print(s)

投稿日時:
最終更新: