一応全部通ってた。
10. Boomerang Constellations
問題概要
二次元平面上に N 個の星がそれぞれ異なる位置に存在する。 それぞれの星は、座標(X_i, Y_i) で表される。 ブーメラン星座を以下のように定義する。
- 星a-b間の距離 = 星b-c間の距離 (a ≠ b ≠ c) を満たす3つの星の組
このとき、ブーメラン星座の組み合わせの個数を答えよ。ただし他のブーメラン星座と星を共有してもよい。
解法
星 b を中心の星とすることを考え、星 b をすべての星に当てはめて総当りする。
星 b からの距離が等しい任意の 2 星間の組はブーメラン星座を成す。
一般化すると, 距離が等しい星が N 個あったときは、1 から N - 1 までの総和の組の個数を作れる。
等しい距離の星の個数を数えるのは map(連想配列) で簡単にできるので、O(N^2 log N) で解くことができ, だいたい間に合う。(O(N^2 log N)は前の CF で落ちた気が)
ソース
#include<bits/stdc++.h> using namespace std; typedef long long int64; int64 Solve() { int N, X[2000], Y[2000]; int64 ret = 0; cin >> N; for(int i = 0; i < N; i++) { cin >> X[i] >> Y[i]; } for(int i = 0; i < N; i++) { map< int, int > C; for(int j = 0; j < N; j++) { C[(X[i] - X[j]) * (X[i] - X[j]) + (Y[i] - Y[j]) * (Y[i] - Y[j])]++; } for(auto& v : C) { ret += (v.second - 1) * v.second / 2; } } return(ret); } int main() { int T; cin >> T; for(int i = 0; i < T; i++) { cout << "Case #" << i + 1 << ": " << Solve() << endl; } }
25. High Security
問題概要
格子状の高さ 2, 幅 N の地図 G が与えられる。
= '.' のとき (i,j) に何もないマスを示し, = '#' のとき (i, j) に建物があることを示す。
警備員は何もないマス('.') に駐在することができ, 自分のマスだけでなく, 上下左右の連続した何もないマスも見渡すことができる。
例えば, 警備員を 'G' で表すとき,以下のように 見渡せる範囲は 'G' と '*' の部分となる。
.*.X.X.. *G*****X
全ての何もないマスを警備員が見渡せるようにしたいとき, 配置する警備員の最小の人数を求めよ。
解法
こういう問題ちょっと反例がありそうで怖い。
何もないマス(x, y) において, 隣接する左右のマス (x - 1, j),(x + 1, j) に建物があるとき, 左右方向に警備できない (x, y) に置くよりは, 左右方向に警備できる可能性がある (x, y + 1) あるいは, (x, y - 1) に置いたほうが良いのは直感的に分かる。
なので, それに該当するマス全てに最初に警備員を配置する。
あとはGrundyに左方向から, まだ警備されていない何もないマスがあれば 警備員を配置していく。Grundy怖いけど。
ソース
#include<bits/stdc++.h> using namespace std; struct UnionFindTree { vector< int > data; UnionFindTree(int sz) { data.assign(sz, -1); } inline void Unite(int x, int y) { x = Find(x), y = Find(y); if(x == y) return; if(data[x] > data[y]) swap(x, y); data[x] += data[y]; data[y] = x; } inline int Find(int k) { return(data[k] < 0 ? k : data[k] = Find(data[k])); } inline bool Same(int x, int y) { return(Find(x) == Find(y)); } }; int Solve() { int N; string G[2]; cin >> N; N += 2; cin >> G[0]; cin >> G[1]; G[0] = "X" + G[0] + "X"; G[1] = "X" + G[1] + "X"; bool Root[10000] = {}; UnionFindTree uf1(N), uf2(N); for(int i = 1; i < N; i++) { if(G[0][i - 1] == '.' && G[0][i] == '.') uf1.Unite(i - 1, i); if(G[1][i - 1] == '.' && G[1][i] == '.') uf2.Unite(i - 1, i); } int Count = 0; for(int i = 1; i < N - 1; i++) { if(G[0][i - 1] == 'X' && G[0][i] == '.' && G[0][i + 1] == 'X') { ++Count; Root[uf1.Find(i)] = true; if(G[1][i] == '.') Root[uf2.Find(i) + 5000] = true; } } for(int i = 1; i < N - 1; i++) { if(G[1][i - 1] == 'X' && G[1][i] == '.' && G[1][i + 1] == 'X') { if(Root[uf2.Find(i) + 5000]) continue; ++Count; Root[uf2.Find(i) + 5000] = true; if(G[0][i] == '.') Root[uf1.Find(i)] = true; } } for(int i = 1; i < N - 1; i++) { if(G[0][i] == '.' && !Root[uf1.Find(i)]) { ++Count; Root[uf1.Find(i)] = true; } if(G[1][i] == '.' && !Root[uf2.Find(i) + 5000]) { ++Count; Root[uf2.Find(i) + 5000] = true; } } return(Count); } int main() { int T; cin >> T; for(int i = 0; i < T; i++) { cout << "Case #" << i + 1 << ": " << Solve() << endl; } }
25. The Price is Correct
問題概要
N 個の数値からなる数列 B がある。
数列 B から連続する任意の要素を抜き出し, その要素の和を合計する。
合計した結果が T を上回ると ゲームに負けるので, それ以下に抑えたい。
抜き出し方は何通りあるか求めよ。
解法
圧倒的に尺取り法。
数列 B を左から右に走査することを考える。
B[i] を抜き出す数列の最後の要素とするとき, 和が T 以下を満たす先頭の要素番号 s の最小値を求める。
すると, B[i] ≥ 1 なので s, s+1, ..., i は全て和が T 以下になる。よって, (i - s) を抜き出し方の組み合わせとして足す。
このとき s は単調増加。尺取りすると O(N)。
ソース
#include<bits/stdc++.h> using namespace std; typedef long long int64; int64 Solve() { int64 N, P, B[100000]; cin >> N >> P; for(int i = 0; i < N; i++) { cin >> B[i]; } int64 ret = 0, head = 0, now = 0; for(int i = 0; i < N; i++) { now += B[i]; while(head <= i && now > P) { now -= B[head]; ++head; } ret += i - head + 1; } return(ret); } int main() { int T; cin >> T; for(int i = 0; i < T; i++) { cout << "Case #" << i + 1 << ": " << Solve() << endl; } }
40. Text Editor
問題概要
文字列の末端への 1 文字ずつの追加, 削除, プリントができるテキストエディタがある。
それぞれの操作にはコスト 1 がかかる。
最初, エディタの内容は空文字列である。
N 個の単語のうち任意の K 個を選んでプリントしたい。
また K 個の単語を表示した後, 空文字列にして終わる必要がある。
コストを最小化せよ。
解法
なるべく先頭からの文字列を重複させたいので, 辞書順でソートする。
あとは DP するだけ。次の文字列へ行くまでのコストの計算は, 共通している文字数貪欲に数えれば求まる。
O(N^3)になるがこれでも間に合う(N^3のテストケースが100個は死ぬ気がするけどテストケースが弱いのか1秒未満だった)
- dp[i][j]: 最後に i 番目のワードをプリントし, 計 j 個プリントしたときのコストの最小値
- dp[i][j]: dp[k][j - 1] + dist(S[k], S[i]) (k < i)
ソース
#include<bits/stdc++.h> using namespace std; const int INF = 1 << 30; int Solve() { int N, K; string S[302]; int dp[302][302]; fill_n(*dp, 302 * 302, INF); cin >> N >> K; for(int i = 0; i < N; i++) { cin >> S[i]; } sort(S, S + N); int ret = INF; for(int i = 0; i < N; i++) { dp[i][1] = S[i].size() + 1; for(int j = i - 1; j >= 0; j--) { // 前の要素 int Match = 0; while(Match < S[j].size() && Match < S[i].size() && S[j][Match] == S[i][Match]) ++Match; for(int k = 1; k <= i; k++) { // とった個数 dp[i][k + 1] = min< int >(dp[i][k + 1], dp[j][k] + S[j].size() + S[i].size() - 2 * Match + 1); } } } for(int i = 0; i < N; i++) { ret = min< int >(ret, dp[i][K] + S[i].size()); } return(ret); } int main() { int T; cin >> T; for(int i = 0; i < T; i++) { cout << "Case #" << i + 1 << ": " << Solve() << endl; } }