C++でHPを最高カテゴリにアップグレードするために必要な増加量を求める方法

問題の概要

数値 n が与えられます。あるゲームでは、各キャラクターのヒットポイント（HP）は以下の4つのカテゴリのいずれかに分類されます。

• カテゴリA：HPが (4n + 1) の形式の場合
• カテゴリB：HPが (4n + 3) の形式の場合
• カテゴリC：HPが (4n + 2) の形式の場合
• カテゴリD：HPが 4n の形式の場合

これら4つのカテゴリは A > B > C > D の順に優先度が決まっており、カテゴリAが最も高く、カテゴリDが最も低くなります。ゲーム中、プレイヤーはキャラクターのHPを増やすことが可能です。ここで、Amalは自分のHPを最大2まで（つまり0、1、または2のいずれか）増やしたいと考えています。HPをできる限り高いカテゴリにするには、いくつ増やせばよいのでしょうか？

例として、入力が n = 98 の場合を考えてみましょう。このとき出力は「1 B」になります。98は (4×24 + 2) という形式なのでカテゴリCに該当します。1増やせば99となりカテゴリBへアップグレードできますが、2増やすと100 (4×25) となり、かえってカテゴリDに下がってしまいます。したがって、達成可能な最高カテゴリはBで、必要な増加量は1となります。

解法のアプローチ

この問題は、n を4で割った余り（n mod 4）に着目することで非常にシンプルに解けます。以下の手順に従います。

n mod 4 が 2 の場合:
    「1 B」を返す
それ以外の場合:
    |(n mod 4) − 1| と「A」を返す

なぜこのロジックで正しく動くのか

• n mod 4 = 1（カテゴリA）：すでに最上位カテゴリのため、増加量は0。「0 A」を出力
• n mod 4 = 3（カテゴリB）：2増やすと 4(n+1)+1 の形になりカテゴリAへ到達可能。「2 A」を出力
• n mod 4 = 2（カテゴリC）：1増やせばカテゴリBになるが、2増やすとカテゴリDに下がるため「1 B」が最適
• n mod 4 = 0（カテゴリD）：1増やすだけでカテゴリAになれるため「1 A」を出力

C++での実装例

理解を深めるために、以下の実装例を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
void solve(int n){
    if (n % 4 == 2)
        cout << "1 B";
    else
        cout << abs(n % 4 - 1) << " A";
}
int main(){
    int n = 98;
    solve(n);
}

実行結果

入力

98

出力

1 B

計算量

• 時間計算量：O(1) ― 剰余演算と条件分岐のみで処理が完結
• 空間計算量：O(1) ― 追加のデータ構造は不要