読者です 読者をやめる 読者になる 読者になる

UAPC2011 Summer

途中から私用があったので、制限時間は2時間でした。
1完
テンプレートは省略。

  • A.Popularity Estimation

どうしてmapを使ってカウントしようとしたのか謎。(普通に配列使えばいいのに)
入力のループとカウントのループが別な理由も謎。(TLEになったらどうするつもりだ)
デバッグ用コードをC++11仕様で書いてるのはCodeforcesのせい。

int main() {
	for(int N; cin >> N && N;) {
		vector<string> names(N);
		vector<vector<int> > times(N);
		map<int, int> cnt;
		vector<int> pts(N);
		rep(k, N) {
			string name; cin >> name;
			names[k] = name;
			int m; cin >> m;
			rep(i, m) {
				int t; cin >> t;
				times[k].pb(t);
			}
		}
		rep(k, N) {
			int n = times[k].size();
			rep(i, n) {
				cnt[times[k][i]]++;
			}
		}
#if 0
		for(auto it = cnt.begin(); it != cnt.end(); ++it) {
			cout << it->first << ":" << it->second << endl;
		}
#endif

		rep(k, N) {
			int n = times[k].size();
			rep(i, n) {
				int t = N - cnt[times[k][i]] + 1;
				pts[k] += t;
			}
		}
#if 0
		for(auto it = pts.begin(); it != pts.end(); ++it) {
			cout << *it << endl;
		}
#endif
		int pt_min = *min_element(all(pts));
		vector<string> sel;
		for(int i = 0; i < N; i++) {
			if(pts[i] == pt_min) {
				sel.pb(names[i]);
			}
		}
#if 0
		for(auto it = sel.begin(); it != sel.end(); ++it) {
			cout << *it << endl;
		}
#endif
		cout << pt_min << " " << *min_element(all(sel)) << endl;
	}
	return 0;
}
  • B.High and Low Cube

行列の1次変換使ったら90°回転とか楽だよねー、ということまでは気づく。
上下反転や左右反転のコードも書かないといけないらしく、諦めた。

  • C.Time Manipulation

1.P(0),...,P(m-1)の最小公倍数まで調べればいいよねー
2.でも1から20までの最小公倍数って20億超えるよねー(Project Euler Problem 5
結果:TLEして、外出しないといけない時間になる。