2010-06-17

ACMの過去問解いてみた！！（３）〜2007年国内予選ProblemB

programming java acm

PCの利用時間を出す問題。
重複の判定がなかなかできなくて、時間かかりました。

package acm2007.b;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;

public class Q {

	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]); // PCの数
			int m = Integer.parseInt(str[1]); // 学生数

			if (n == 0 && m == 0) {
				break;
			}

PCの数、学生の数を変数に代入。
終了条件を記述。

			int r = Integer.parseInt(br.readLine()); // 利用記録数
			int rSet[][] = new int[r / 2 + 1][4]; // 利用記録セット
			int p = 0;

			HashMap<String, Integer> map = new HashMap<String, Integer>();

			for (int i = 0; i < r; i++) {
				line = br.readLine();
				str = line.split(" ");
				if (map.get(str[1] + "-" + str[2]) != null) {
					rSet[p][0] = Integer.parseInt(str[1]); // PC番号
					rSet[p][1] = Integer.parseInt(str[2]); // 学生番号
					rSet[p][2] = map.get(str[1] + "-" + str[2]); // ログイン時間
					rSet[p][3] = Integer.parseInt(str[0]); // ログアウト時間
					p++;
					map.remove(str[1] + "-" + str[2]);		//次のPC−学生の同じ組が入るときのために削除
				} else {
					map.put(str[1] + "-" + str[2], Integer.parseInt(str[0]));
				}
			}

利用記録を配列に代入します。
HashMapを使って、PC番号-学生番号をキーにしてログイン、ログアウトの時間を一緒に記録する。

			int q = Integer.parseInt(br.readLine()); // 質問数
			int qSet[][] = new int[q][3]; // 質問セット

			for (int i = 0; i < q; i++) {
				line = br.readLine();
				str = line.split(" ");
				for (int j = 0; j < 3; j++) {
					qSet[i][j] = Integer.parseInt(str[j]);
				}
			}

質問を配列に代入します。

			for (int i = 0; i < q; i++) {
				int fill[] = new int[1260]; // 塗りつぶし用
				int sum = 0; // カウント用
				for (int j = 0; j < p; j++) {
					if (qSet[i][2] == rSet[j][1]) { // 学生番号が同じ
						for (int k = rSet[j][2]; k < rSet[j][3]; k++) {		//利用している時間を塗りつぶす
							fill[k] += 1;							
						}
					}
				}

”540 ≤ t ≤ 1260”とあるので1260の配列を宣言します。利用している”分”を1ずつインクリメントしていきます。こうすることで、PCの重複の利用を無視出来ます。

				for (int l = qSet[i][0]; l < qSet[i][1]; l++) {		//クエスチョンの時間の範囲を指定
					if (fill[l] != 0) {                       //0じゃなかったら利用時間に加算
						sum += 1;
					}
				}
				System.out.println(sum);
			}
		}
	}
}

配列を走査し、中身が0じゃないものを数えていきます。

この1問にかなり時間をかけていしまったのですが、結局かなり奇妙なプログラムになってしまいました。
Javaでの別のやり方を見てみたいんだが、、、

2010-06-16

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;
	}
}

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

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

2010-06-11

ACMの過去問解いてみた！(1) 〜2009年国内予選ProblemA

programming java acm

来月のACMに向けてJava で去年の過去問解いてみた。
2009年度東京大会国内予選問題

ProblemA
素直に解いただけ…。
次期町長を決める問題です。

package acm2009.a;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Q {

	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 p = Integer.parseInt(str[1]);　　　//最初に碗に入れる小石の総数

			if (n == 0 && p == 0) {
				break;
			}
			System.out.println(game(n, p));
		}
	}

候補者の人数と小石の人数を入れる変数を作り、終了条件を記述します。
あとはメソッドに渡して返り値を出力します。

	private static int game(int n, int p) {
		int wan = p;　　　　　　　　　　　　　　//碗に入っている小石の数
		int[] numstorn = new int[n];                    //候補者が持っている小石の数

		while (true) {
			for (int i = 0; i < n; i++) {
				if (wan == 0) {
					wan = numstorn[i];
					numstorn[i] = 0;
				} else {
					wan--;
					numstorn[i]++;
					if (p == numstorn[i]) {    //小石の総数と候補者が持っている小石の数が等しければ終了。
						return i;
					}
				}
			}
		}
	}
}

問題通りに書いていけば、いけます。

2010-06-11

Hello World!!

はろーはてな。ブログはじめます。