■ [others]hos' Xmas Contest 2010 
2010-12-25 14:00-18:00
http://hos.gozaru.jp/contest/xmas2010/
熱いクリスマスでした。
- A
- まあやるだけ。最初2つの家が常に同じ方向にあると思い込んでハマってしまった。サンプルはよく読みましょう
- 60点…
- 整数オーバーフローかと思ったけどそうではない
- 問題文を読み直すと、家は異なる場所にある、と書いてある。これが未考慮だった
- 100点
- B
- C
- グラフの特定の頂点集合をカバーする部分グラフの中でコスト最小のものを求めるんですね
- 計算量的にはN回最小全域木を求めるというようなくらいか
- Σsi<=10がキーポイントになってbitDPでもやるのかと思ったが全然わからない
- コンテスト終了後に検索してみる→最小シュタイナー木問題てのがあるのか。初めて知った
- でもそれじゃこんなに多くの人が解かないはず
- 他の人の参加記を読む→"とてもお気に入り"とそうじゃないのを逆に考えてた…
- 100個中90個以上が"とてもお気に入り"ってお気に入りインフレしすぎだろw
- これって意図的なトラップだったのだろうか？
- D
- E
- さっぱり
- F
- さっぱり
- G
- これは解きたかったが
- さすがに条件を満たす数列の例はいっぱいある
- 「任意の連続する範囲の和の絶対値は1以上M以下」を考慮するのが難しくてギブアップ
- H
- これは…ボーナス問題？
- ここまでの各問題で「神経質なほど入力形式が親切に書いてあるな」と思ってたのはこれへの布石だったのか
- 一番面倒そうなBは最後の行が"#"であることから判定できる
- 行ごとの整数の個数を数えてA、G以外は判別可能
- AとGは値の範囲を見る必要がある。あとテストケースの個数も
- いくつかイージーミスがあって1WAしたあと100点
結果は350点で28位/90人くらいでした。
Cができなかったのがかなり痛い
以下ソース（#include, typedef, using は略）
A
int a,b,c,d; void solve(){ int ma = (d+c) / (a+b) * 2 + 1; if ((d+c) % (a+b) >= a) ++ma; int dis; if (d == c) { dis = d + c; }else { dis = d - c; } int mi = dis / (a+b) * 2 ; if (dis % (a+b) >= b) ++mi; cout << mi << " " << ma << endl; } int main(){ while(true) { cin >> a >> b >> c >> d; if(a == 0) return 0; if(a > b) { swap(a, b); // a <= b; } if (c > d) { swap(c, d); // c <= d; } solve(); } }
B
int main(){ string line; while(true){ cin >> line; if(line == "#") return 0; bool even = true; for(int i = 0; i < line.size(); ++i){ if('0' <= line[i] && line[i] <= '9') { if (i == line.size() - 1 || '9' < line[i+1] || line[i+1] < '0'){ if ( (line[i] - '0') % 2 ) { even = !even; } } } } cout << (even ? "EVEN" : "ODD") << endl; } }
D
int N,P,Q,D; vector<int> d; vector<int> a; vector<int> b; ll dp[100001][2]; ll size; ll solve() { int cur = 0; dp[0][cur] = 0; for(ll i = 1; i <= size; ++i) { dp[i][cur] = a[0]*i+b[0] + i*i*d[0]; } for(int i = 1; i < N; ++i) { cur ^= 1; dp[0][cur] = 0; ll mi = 0; for(ll j = 1; j <= size; ++j) { dp[j][cur] = min(mi+a[i]+b[i], dp[j][cur^1]); dp[j][cur] += j*j*d[i]; mi = min(mi+a[i], dp[j][cur^1]); } } ll ans = 1ll << 62; for(ll i = P; i <= size; ++i) { ans = min(ans, dp[i][cur]-Q*i); } return ans; } int main(){ while(true) { cin >> N >> P >> Q >> D; if(N == 0) return 0; d.clear(); a.clear(); b.clear(); int di,ai,bi; for(int i = 0; i < N; ++i) { cin >> di >> ai >> bi; d.push_back(di); a.push_back(ai); b.push_back(bi); } for(int i = 0; i < N-1; ++i) { d[i] = d[i+1] - d[i]; } d[N-1] = D - d[N-1]; size = max((ll)P, (ll)ceil(Q / d.back())); cout << solve() << endl; } }
H
vectorinput; vector<int> split(string& str){ vector<int> ret; int cur = 0; for(int i = 0; i < str.size(); ++i){ if(str[i] < '0' || '9' < str[i]) { ret.push_back(cur); cur = 0; continue; } cur *= 10; cur += str[i] - '0'; } ret.push_back(cur); return ret; } bool isA(const vector<int>& ints){ return ints[0] > 100000 || ints[1] > 100000 || ints[2] > 100000 || ints[3] > 100000 || ints[2] > ints[0] || ints[3] > ints[0]; } int main(){ string line; while(true){ input.clear(); while(true){ getline(cin, line); if (line == "@@@@@@@@@@@@@@@@@@@@") { return 0; } if(line == "@@@@@@@@@@"){ break; } input.push_back(line); } if (input.back() == "#") { cout << 'B' << endl; continue; } vector<int> ints = split(input[0]); if (ints.size() == 1) { cout << 'E' << endl; continue; }else if (ints.size() == 2){ cout << 'C' << endl; continue; }else if (ints.size() == 3){ cout << 'F' << endl; continue; } vector<int> ints2 = split(input[1]); if(ints2.size() == 3) { cout << 'D' << endl; continue; } bool a = isA(ints) || isA(ints2) || (input.size() > 21); for(int i = 2; !a && i < input.size(); ++i){ a = isA(split(input[i])); } cout << (a ? 'A' : '?') << endl; } }
