AtCoder

ABC278 B問題(Misjudge the Time)を解く

AtCoder_ABC278_B

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

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

B問題 Misjudge the Time(Difficulty : 123)

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

ABC278 B問題 Misjudge the Time

問題から必要な条件を抽出してコーディングする問題です。AtCoder Problems による Difficulty は、123 でした。ABC B問題として、標準的な問題です。

解答案

問題を解く方針を書きだします。

  • h と m を読み込む。
  • 以下を繰り返す。
    • h の2桁目と m の1桁目をひっくり返して、正しい時刻か確認する。
    • 正しくない時刻の場合は、m をひとつ増やして確かめる。
    • 上記が、正しい時刻が見つかるまで繰り返す。

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

先に「見間違いやすい時刻」か判定してbool 型配列 judge に格納する例を示します。bool 型配列に格納するコードは、背景色を変更しました。

「見間違いやすい時刻」か m を進めながら判定して、見つけたら時刻を出力して、終了します。

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

int main()
{
	int h, m;
	cin >> h >> m;

	vector<bool> judge(24 * 60, false);
	for (int i = 0; i < 24; ++i) {
		for (int j = 0; j < 59; ++j) {
			int a = i / 10;
			int b = i % 10;
			int c = j / 10;
			int d = j % 10;
			if ((a * 10 + c < 24)
			  &&(b * 10 + d < 60)) {
				judge[i * 60 + j] = true;
			}
		}
	}

	while (!judge[h * 60 + m]) {
		++m;
		if (m >= 60) {
			m = 0;
			++h;
		}
		if (h >= 24) {
			h = 0;
		}
	}

	cout << h << " " << m << endl;

	return 0;
}

次に、下請け関数 judge で「見間違いやすい時刻」か判断する例を示します。先のプログラムで、bool 型配列の値を決定するロジックを下請け関数 judge に移しました。

プログラムの本体は、配列 judge のアクセスから関数 judge への呼び出しに変更しています。

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

bool judge(int h, int m)
{
	bool result;

	int a = h / 10;
	int b = h % 10;
	int c = m / 10;
	int d = m % 10;
	result = (a * 10 + c < 24) && (b * 10 + d < 60);

	return result;
}

int main()
{
	int h, m;
	cin >> h >> m;

	while (!judge(h, m)) {
		++m;
		if (m >= 60) {
			m = 0;
			++h;
			if (h >= 24) {
				h = 0;
			}
		}
	}

	cout << h << " " << m << endl;

	return 0;
}

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

何回も繰り返して判断する場合は、値をあらかじめ計算して格納した方が速く計算ができます。一方、今回の問題のような場合は、後者のプログラムでも十分です。後者は動作時のメモリを少なくなります。

Python プログラム例(ABC278B)

Python 版として、C++ 版の後者をベースにしました。下請け関数を定義して判断しました。

"""AtCoder Beginner Contest 278 B"""


def judge(h, m):
    a, b = h // 10, h % 10
    c, d = m // 10, m % 10
    result = a * 10 + c < 24 and b * 10 + d < 60
    return result


h, m = map(int, input().split())
while not judge(h, m):
    m += 1
    if m >= 60:
        h, m = h + 1, 0
    if h >= 24:
        h = 0

print(h, m)

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

最後に

今回、解説した問題は、特定のアルゴリズムを適用して問題を解くわけではありません。問題が解きたいことを読み解き、プログラムとして実装する問題となっています。このような問題は、ある程度コーディングしていけば、慣れていくと思います。

ABC278 について、引き続き、D問題まで紹介します。

COMMENT

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

CAPTCHA