C++で4桁の数字から作成できる最大の時刻を求める方法

はじめに

このチュートリアルでは、4つの数字から作成できる最大の時刻を求めるC++プログラムについて解説します。

具体的には、4つの数字を要素として持つ配列が与えられます。この4つの数字をすべて使い、24時間形式で表せる最大の時刻を見つけることが課題です。例えば、{0, 0, 0, 9}という配列が与えられた場合、作成できる最大の時刻は「09:00」となります。

アルゴリズムの考え方

時刻は「HH:MM」の形式で表されますが、それぞれの桁には次のような範囲の制約があります。

• 時間の十の位： 0〜2
• 時間の一の位： 十の位が「2」の場合は0〜3、それ以外の場合は0〜9
• 分の十の位： 0〜5
• 分の一の位： 0〜9

まず、与えられた4つの数字の出現回数を記録した頻度マップ(hash map)を作成します。その後、上記の制約に従って、左の桁から順に使用可能な最大の数字をマップから探して割り当てていきます。ある桁で候補となる数字が1つも見つからない場合は、有効な時刻を構成できないため「-1」を返します。

この手法では、各桁につき最大10通りの候補を確認するだけで済むため、4桁の並べ替え(24通り)をすべて試す力任せの方法よりも効率的に処理できます。

C++による実装例

#include <bits/stdc++.h>
using namespace std;
// 更新された頻度マップを返す関数
map<int, int> getFrequencyMap(int arr[], int n) {
    map<int, int> hashMap;
    for (int i = 0; i < n; i++) {
        hashMap[arr[i]]++;
    }
    return hashMap;
}
// 指定した数字が頻度マップに存在するかを確認する関数
bool hasDigit(map<int, int>* hashMap, int digit) {
    if ((*hashMap)[digit]) {
        (*hashMap)[digit]--;
        return true;
    }
    return false;
}
// 24時間形式の最大時刻を文字列で返す関数
string getMaxtime_value(int arr[], int n) {
    map<int, int> hashMap = getFrequencyMap(arr, n);
    int i;
    bool flag;
    string time_value = "";
    flag = false;
    // 時間の十の位：0〜2の中で最大のものを選ぶ
    for (i = 2; i >= 0; i--) {
        if (hasDigit(&hashMap, i)) {
            flag = true;
            time_value += (char)i + 48;
            break;
        }
    }
    if (!flag)
        return "-1";
    flag = false;
    // 時間の一の位：十の位が「2」なら0〜3、それ以外なら0〜9
    if (time_value[0] == '2') {
        for (i = 3; i >= 0; i--) {
            if (hasDigit(&hashMap, i)) {
                flag = true;
                time_value += (char)i + 48;
                break;
            }
        }
    }
    else {
        for (i = 9; i >= 0; i--) {
            if (hasDigit(&hashMap, i)) {
                flag = true;
                time_value += (char)i + 48;
                break;
            }
        }
    }
    if (!flag)
        return "-1";
    time_value += ":";
    flag = false;
    // 分の十の位：0〜5の中で最大のものを選ぶ
    for (i = 5; i >= 0; i--) {
        if (hasDigit(&hashMap, i)) {
            flag = true;
            time_value += (char)i + 48;
            break;
        }
    }
    if (!flag)
        return "-1";
    flag = false;
    // 分の一の位：0〜9の中で最大のものを選ぶ
    for (i = 9; i >= 0; i--) {
        if (hasDigit(&hashMap, i)) {
            flag = true;
            time_value += (char)i + 48;
            break;
        }
    }
    if (!flag)
        return "-1";
    return time_value;
}
int main() {
    int arr[] = { 0, 0, 0, 9 };
    int n = sizeof(arr) / sizeof(int);
    cout << (getMaxtime_value(arr, n));
    return 0;
}

出力結果

09:00

コードのポイント

• getFrequencyMap関数： 配列内の各数字の出現回数をmapに記録します。同じ数字が複数回現れても正しく管理できます。
• hasDigit関数： 指定した数字がまだ未使用(残数あり)かどうかを確認し、存在すればカウントを1減らして使用済みにします。
• getMaxtime_value関数： 各桁の制約に従い、大きい数字から順に候補を調べ、最初に見つかった数字を確定させていく貪欲法(グリーディ法)のアプローチです。

なお、(char)i + 48という記述は、数値をASCIIコード経由で対応する文字('0'〜'9')に変換するテクニックです。可読性を重視する場合は、to_string(i)を使う方法もあります。

まとめ

本記事では、4つの数字から作成できる最大の時刻を求めるC++プログラムを紹介しました。頻度マップで各数字の残数を管理しながら、桁ごとの制約に従って大きい数字から優先的に割り当てるのがポイントです。このアプローチは、競技プログラミングの「与えられた数字で作れる最大の時刻」系の問題にもそのまま応用できます。