C++でカップと棚のすっきりとした配置ができるかどうかを判定する方法

問題の概要

3種類ずつのカップ(p[])とソーサー(q[])、および棚の数mが与えられたとき、それらを「きれいに」棚へ配置できるかどうかを判定します。

配置がきれいであるとみなされるためには、次の3つのルールをすべて満たす必要があります。

• ルール1:同じ棚にカップとソーサーを混在させてはいけません。
• ルール2:1つの棚に置けるカップは最大5個までです。
• ルール3:1つの棚に置けるソーサーは最大10枚までです。

入出力例

例1

Input:
p[] = {4, 3, 7}
q[] = {5, 9, 10}
m = 11

Output:
Yes

解説:

カップの総数は14個です。1つの棚に5個までしか置けないため、必要な棚数は切り上げて3つになります。

ソーサーの総数は24枚です。1つの棚に10枚までしか置けないため、必要な棚数は3つになります。

したがって、必要な棚の合計は 3 + 3 = 6つとなり、与えられた棚の数m = 11より少ないため、答えは「Yes」です。

例2

Input:
p[] = {5, 8, 5}
q[] = {4, 10, 11}
m = 3

Output:
No

解説:

カップの総数は18個で、必要な棚数は4つです。

ソーサーの総数は25枚で、必要な棚数は3つです。

必要な棚の合計は 4 + 3 = 7つとなり、与えられた棚の数m = 3を超えているため、答えは「No」です。

解法の考え方

まず、カップの総数sumpとソーサーの総数sumqをそれぞれ求めます。

1つの棚にカップは5個までしか置けないため、カップに必要な棚数は切り上げ除算の式 (sump + 5 - 1) / 5 で計算できます。同様に、ソーサーに必要な棚数は (sumq + 10 - 1) / 10 で求められます。

+5や+10を加えてから割るのは、総数が5未満・10未満の場合でも答えが0ではなく最低1となるようにするためです。

これら2つの値の合計がm以下であれば配置は可能(Yes)、そうでなければ不可能(No)となります。

計算量は配列を一度走査するだけなので、O(n)で非常に効率的です。

C++による実装例

// カップとソーサーをきれいに配置できるかどうかを判定するC++プログラム
#include<bits/stdc++.h>
using namespace std;

// 配置可能性をチェックする関数
void canArrange1(int p[], int q[], int m){
    int sump = 0, sumq = 0;

    // カップの総数を計算
    for(int i = 0; i < 3; i++)
        sump += p[i];

    // ソーサーの総数を計算
    for(int i = 0; i < 3; i++)
        sumq += q[i];

    // 切り上げ除算により必要な棚数を算出
    // (総数が5未満・10未満でも答えが0にならないよう調整)
    int mp = (sump + 5 - 1) / 5;
    int mq = (sumq + 10 - 1) / 10;

    if(mp + mq <= m)
        cout << "Yes";
    else
        cout << "No";
}

// メイン関数
int main(){
    // 各種類ごとのカップの数
    int p[] = {4, 3, 7};

    // 各種類ごとのソーサーの数
    int q[] = {5, 9, 10};

    // 棚の数
    int m = 10;

    // 関数の呼び出し
    canArrange1(p, q, m);

    return 0;
}

出力

Yes

まとめ

この問題は、制約条件(1棚あたりカップ5個・ソーサー10枚)に基づいて必要な棚数を切り上げ除算で求め、それが利用可能な棚数m以内に収まるかを確認するだけのシンプルな数学的アプローチで解けます。実際のコードも数行で済み、競技プログラミングの初級問題として最適な例といえるでしょう。