POJ 2380 - Sales Report

http://poj.org/problem?id=2380

概要

セールスポイントが \(s_i\) の商品 \(q_i\) が \(v_i\) 個売れた、という形式の記録が \(N\) 個与えられる。 それぞれの商品とセールスポイントについて合計でどれだけ売れたかを表の形で答える。

制約

解法

やるだけだが数が多くて TLE しやすい。 Java ルール + HashMap + 出力行を StringBuilder で構築してから println で無理矢理通した。

 1 import java.util.*;
 2 
 3 public class Main {
 4 	public static void main(String[] args) {
 5 		Scanner cin = new Scanner(System.in);
 6 		int N = cin.nextInt();
 7 		HashMap<Pair, Long> m = new HashMap<Pair, Long>();
 8 		TreeSet<Integer> rows = new TreeSet<Integer>(), cols = new TreeSet<Integer>();
 9 		for (int i = 0; i < N; i++) {
10 			int c = cin.nextInt();
11 			int r = cin.nextInt();
12 			int v = cin.nextInt();
13 			cols.add(c);
14 			rows.add(r);
15 			Pair k = new Pair(c, r);
16 			if (m.containsKey(k)) {
17 				long o = m.get(k);
18 				m.put(k, o + v);
19 			} else {
20 				m.put(k, (long)v);
21 			}
22 		}
23 		Integer[] rs = new Integer[rows.size()], cs = new Integer[cols.size()];
24 		rows.toArray(rs);
25 		cols.toArray(cs);
26 
27 		System.out.print("-1");
28 		for (int c : cs) {
29 			System.out.print(" " + c);
30 		}
31 		System.out.println("");
32 		for (int r : rs) {
33 			StringBuilder sb = new StringBuilder();
34 			sb.append("" + r);
35 			for (int c : cs) {
36 				Pair k = new Pair(c, r);
37 				if (m.containsKey(k)) {
38 					sb.append(" " + m.get(k));
39 				} else {
40 					sb.append(" 0");
41 				}
42 			}
43 			System.out.println(sb.toString());
44 		}
45 	}
46 }
47 
48 class Pair {
49 	public int x, y;
50 	public Pair(int a, int b) { x = a;  y = b; }
51 
52 	@Override
53 	public boolean equals(Object o) {
54 		Pair p = (Pair)o;
55 		return x == p.x && y == p.y;
56 	}
57 
58 	@Override
59 	public int hashCode() { return new Long((long)x * y).hashCode(); }
60 }
poj/2380.java