AOJ-ICPC 1153

今日といたのがこの問題。

Equal Total Scores | Aizu Online Judge

太郎さんと花子さんが数字の書かれたカードをそれぞれ何枚かもっているので、一枚交換してカードに書かれた数の和が一致するようにしましょう、という問題。

解答はこちら。

#include <cstdio>
#include <iostream>
#include <cmath>
#include <ctype.h>
#include <string> 
#include <sstream>
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <map>
#include <queue>
#include <utility>
#include <vector>
#include <set>
  
using namespace std;
 
int main()
{
    int n, m;
    while(1){
        cin >> n >> m;
        if(n == 0 && m == 0) break;
        int taro[100], hanako[100];
        int taro_sum = 0, hanako_sum = 0;
        for(int i = 0; i < n; i++){
            cin >> taro[i];
            taro_sum += taro[i];
        }
        for(int i = 0; i < m; i++){
            cin >> hanako[i];
            hanako_sum += hanako[i];
        }
        if((taro_sum + hanako_sum) % 2 == 1) cout << -1 << endl;
        else{
            int new_taro_sum, new_hanako_sum;
            for(int i = 0; i < n; i++){
                for(int j = 0; j < m; j++){
                    new_taro_sum = taro_sum + hanako[j] - taro[i];
                    new_hanako_sum = hanako_sum + taro[i] - hanako[j];
                    if(new_hanako_sum == new_taro_sum){
                        cout << taro[i] << ' ' << hanako[j] << endl;
                        i = 101;
                        break;
                    }
                }
                if(i == n - 1) cout << -1 << endl;
            }
        }
    }
   return 0;
}

一次元配列taroとhanakoにそれぞれのカードを記録していきます。あとそれぞれの和も計算しておきます。
二人がもつすべてのカードの和が奇数のときは一致させることは不可能なので-1を表示して終了。
それ以外は0番目のカードから一つずつ交換して一致するかチェックして、一致したとき交換するカードの値を表示して終了します。
これでとりあえずacceptedしました。

…で、問題はここから。
これを解いたあと、知人がこの問題の解答と解説をブログにまとめていたので見てみたんですね。
そこに書かれていたのが、「一致するときに交換するカードの候補に追加する」。

…ん？私そんなこと全然気にせずに書いたぞ？？？？

そう思って問題文をもう一度見てみると" If there is more than one way to exchange a pair of cards that makes the total scores equal, output a pair of scores whose sum is the smallest."の文字が。つまり和が最小になるような組み合わせにしろと。

一方の私、候補をあげたりせず見つかったら即答えとして表示…。
しかしacceptedされちゃいましたね…。

なんだかモヤモヤした感じ。
今回はたまたまうまく通りましたが、今度から気をつけないといけませんね。