AtCoder ABC085C – OtoshidamaでのWAの原因とC++初心者向け解説

AtCoderのABC085C問題『Otoshidama』で一部のテストケースがWA（Wrong Answer）になる原因について、C++初心者向けに詳しく解説します。提出コードのロジック自体は大筋で正しいですが、細かい条件処理や範囲の扱いに問題があります。

提出コードの概要
WAになる原因
改善方法
C++での安全な実装例
まとめ

提出コードの概要

提示されたコードは、1000円単位に換算した金額を、1万円札(i)、5千円札(j)、千円札(k)の組み合わせで表す処理です。三重ループでi, j, kを総当たりして、条件を満たす最初の組み合わせを出力しています。

問題の本質は、与えられた枚数(n)と合計金額(y)から、各紙幣の組み合わせを求めることです。

WAになる原因

提出コードで一部テストケースがWAになる原因は、整数の割り算や範囲指定の問題ではなく、解が存在しない場合のチェックやループの条件です。

具体例として、i+j+k=nの関係式を正確に扱っていますが、10*i + 5*j + k == amountの条件において、金額を1000円単位に変換した際、1万円札や5千円札の組み合わせで端数が生じる場合に一致しないケースがあります。

改善方法

改善策として、金額(amount)を1000円単位にせず、元の金額(y)をそのまま計算する方法があります。例えば、i*10000 + j*5000 + k*1000 == yとすることで、端数処理による誤差を避けられます。

また、ループ上限をi <= nやj <= n-iとしている点は正しいですが、整数除算を行う前に元の金額を使用する方が安全です。

C++での安全な実装例

以下は改善例です。

#include <iostream>
using namespace std;
int main(){
    int n, y;
    cin >> n >> y;
    for(int i=0; i<=n; i++){
        for(int j=0; j<=n-i; j++){
            int k = n-i-j;
            if(10000*i + 5000*j + 1000*k == y){
                cout << i << ' ' << j << ' ' << k << endl;
                return 0;
            }
        }
    }
    cout << "-1 -1 -1" << endl;
    return 0;
}

このように元の金額で計算することで、全てのテストケースに対応できます。