A - What month is it? 解説 by shobonvip


\(X\) 月の \(1\) ヶ月後は、

  • \(1 \le X \le 11\) のとき \(X+1\)
  • \(X=12\) のとき \(1\)

として求められます。 \(X\) 月の \(Y\) ヶ月後を求めるには、「 \(X\) 月の \(1\) ヶ月後を求めて、それを新たな \(X\) とする」ことを \(Y\) 回繰り返せばよいです。

計算量

計算量で表すと、この方針では \(O(Y)\) 時間で、 Tamiji さんの方針では \(O(1)\) 時間であるので、 Tamiji さんの方針の方が計算量的に優れていることになります。

仮にこの問題の制約が \(1 \le Y \le 10^{18}\) であった場合はこの方針では実行時間オーバー(TLE)し、 Tamiji さんの方針では間に合います。

しかし、今回は問題の制約が \(1 \le Y \le 12\) であるので、どちらの方針でもほとんど時間をかけずに正解することができます。非効率なアルゴリズムでも間に合いそうな場合は、計算量が良い方針を思いついたとしても、実装がより簡単な方針で進めることは一つの手です。

実装例

Python

x, y = map(int,input().split())
for _ in range(y):
	if 1 <= x <= 11:
		x = x + 1
	else:
		x = 1
print(x)

C++

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

int main() {
	int x, y; cin >> x >> y;
	for (int i=0; i<y; i++) {
		if (1 <= x && x <= 11) {
			x = x + 1;
		}else{
			x = 1;
		}
	}
	cout << x << '\n';
}

投稿日時:
最終更新: