ACMの過去問解いてみた！！(2)

programming java acm

前回に引き続き、ACMの過去問を、、、。もちろんJavaです。

2008年の国内予選の問題です。

ProblemA 等しい合計点
太郎と花子がカードを交換する問題です。

とりあえず入力の処理から。

public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(Q.class
				.getResourceAsStream("input.txt")));

		String line = null;
		while ((line = br.readLine()) != null) {

ここまでで、ファイルの入ったインプットをとりあえず一行ずつ読み込みます。

			String[] str = line.split(" ");

			int n = Integer.parseInt(str[0]); // 太郎のカードの枚数
			int m = Integer.parseInt(str[1]); // 花子のカードの枚数
			int numTaro[] = new int[n]; // 太郎の持っているカードの点数
			int numHanako[] = new int[m]; // 花子の持っているカードの点数
			int cNum[] = { 100, 100 }; //交換が等しくなるカードの組み合わせ

line.splitでそれぞれのカードの枚数を読み込みます。
それから点数を入れる用の変数を作り，出力用の答えを入れる変数を作ります。これには，問題文に”合計を等しくするようなカードの交換の方法が複数ある場合は， 交換するカードの点数の和が最小となるものを出力すること．”とあるので、とりあえず一番大きい100を入れておきます。

			for (int i = 0; i < n + m; i++) {
				line = br.readLine();
				if (i < n) {
					numTaro[i] = Integer.parseInt(line);
				} else {
					numHanako[i - n] = Integer.parseInt(line);
				}
			}

			if (n == 0 && m == 0) {//終了条件
				break;
			}

カードの枚数の分だけそれぞれの配列に入れていきます。
終了条件もここに記述しておきます。

                        for (int i = 0; i < n; i++) {
				for (int j = 0; j < m; j++) {
					int changeCard = 0; //カード交換用の変数
					changeCard = numTaro[i];
					numTaro[i] = numHanako[j];
					numHanako[j] = changeCard;

いよいよ本題です。
一つづつカードを交換します。

					if (sumArray(numTaro) == sumArray(numHanako)) { //sumArray:合計用のメソッド
						if (numHanako[j] + numTaro[i] < cNum[0] + cNum[1]) {
							cNum[0] = numHanako[j];
							cNum[1] = numTaro[i];
						}
					}
					numHanako[j] = numTaro[i];
					numTaro[i] = changeCard;
				}
			}

それから合計用のメソッドを呼び出し、もし"合計が等しい"かつ"今までの組み合わせの和より小さい"ならば答えを入れ替えます。
それから次の交換のためにカードをもとに戻します。この処理を全ての組み合わせで行います。

			if (cNum[0] == 100 && cNum[1] == 100) {
				System.out.println(-1);
			} else {
				System.out.println(cNum[0] + " " + cNum[1]);
				cNum[0] = 100;
				cNum[1] = 100;
			}

		}
	}

最後に出力部分です。
もし100,100のままなら、交換されていないので-1を、それ以外ならカードの組み合わせを出力します。

	private static int sumArray(int x[]) {
		int sum = 0;
		for (int s : x) {
			sum = sum + s;
		}
		return sum;
	}
}

一応、合計用のメソッドです。


今日はこんな感じで。このくらいの問題は慣れてきた...。