hos' Xmas Contest 2010
夜の部に参加したので、参加記的なものを。
取り組んだ問題順がカオスだったので、最終提出の時間順で書きます。
- -
B. Simple Parsing
- Aが60%で止まってしまったので先にBへ。
- 偶奇だけ分かれば良いので適当な事しても良いんだろうなと思いつつ…
- 某国のアレを最近解いたばかりだったのでマジメに構文解析してみた。
#include <iostream> #include <string> #include <stdio.h> using namespace std; int parseTerm(string&, int&); int parseExpr(string &str, int &idx){ int res = parseTerm(str, idx); while(idx<str.size() && (str[idx] == '+' || str[idx] == '-')){ idx++; int a = parseTerm(str, idx); res = (res+a)%2; } return res; } int parseTerm(string &str, int &idx){ if(isdigit(str[idx])){ int res = 0; while(idx<str.size() && isdigit(str[idx])){ res = (str[idx]-'0')%2; idx++; } return res; } if(str[idx]=='-'){ idx++; return parseTerm(str, idx); } if(str[idx]=='('){ idx++; int res = parseExpr(str, idx); idx++; return res; } } int main(){ string str; while(cin >> str){ if(str == "#") break; int idx = 0; if(parseExpr(str, idx) == 0) printf("EVEN\n"); else printf("ODD\n"); } }
C. Connect The Decoration
#include <iostream> #include <vector> #include <algorithm> #include <cstring> #include <stdio.h> using namespace std; int root[100]; int getRoot(int v){ return root[v]==-1 ? v : root[v] = getRoot(root[v]); } int main(){ int N, M; bool invalid[100]; while(scanf("%d %d", &N, &M), N){ vector<int> no; int a, b, c; for(int i=0;i<N;i++){ scanf("%d", &a); if(a==1) no.push_back(i); } vector< pair<int, pair<int, int> > > vp; for(int i=0;i<M;i++){ scanf("%d %d %d", &a, &b, &c); vp.push_back(make_pair(c, make_pair(a-1,b-1))); } int res = 1000000000; sort(vp.begin(), vp.end()); for(int i=0;i<(1<<no.size());i++){ memset(invalid, false, sizeof(invalid)); memset(root, -1, sizeof(root)); int size = N-1; for(int j=0;j<no.size();j++) if(i&(1<<j)){ size--; invalid[no[j]] = true; } int sum = 0; for(int j=0;j<vp.size();j++){ if(invalid[vp[j].second.first] ||invalid[vp[j].second.second]) continue; int p = getRoot(vp[j].second.first); int q = getRoot(vp[j].second.second); if(p!=q){ root[q] = p; sum += vp[j].first; size--; } if(size == 0) res = min(res, sum); } } printf("%d\n", res); } }
A. Christmas Trees
- 最大：どっちかの家の前にツリーがある最適解が存在する
- 最小：どっちかの家の前+ちょっとの位置にツリーがある最適解が存在する
- ので、境界条件に気をつけつつ調べるだけ
- だったのに、c=dを見落としたり境界条件ミスったりしてgdgdに…
#include <iostream> #include <stdio.h> using namespace std; int main(){ int a, b, c, d; while(scanf("%d %d %d %d", &a, &b, &c, &d), a){ int M = c+d; int m = abs(c-d); if(m == 0) m = M; int Mans = M/(a+b)*2+1; if(M%(a+b) >= min(a,b)) Mans++; int mans = m/(a+b)*2; if(m%(a+b) >= max(a,b)) mans++; printf("%d %d\n", mans, Mans); } }
D. Presents
- とりあえず、プレゼントの個数ごとに(値段+疲れ度)の最小値を求めるDPを組む。
- 最後にP個以上買った場合についてQ*買った個数を引いた物の最小値をとれば良い。
- この時点で、プレゼントを買う個数の上限をLとしてO(LN)。
- このLってどれくらい大きくなりうるんだろう…？
- とりあえずL=1000で出す→30%
- 仕方ないのでL=10000で出す→60%
- WAがあるのでもっと増やす必要はあるけど、TLEもあるので増やせない…。
- てか冷静に考えたらQ個くらい買わなきゃいけない場合がありそう。
- O(QN)とかどう考えても終わらないぞ…。
- そんな訳で枝刈りゲーを開始。
- 最終的に使ったのは、P個以上買う場合は疲れ度の増加に見合うかを見る枝刈り。
- ゴールまで残り距離dの場所で，プレゼントをp個持っているとき、
- 1個買い足すことで、最終的に-Qだけ小さくなる
- 一方で、疲れ度はd*(p+1)^2-d*p^2 = d*(2p+1)だけ増加する
- なので、d*(2p+1) >= Q だったらP個より多く買い足すのは損
- Qをゴールまでの距離で割れるので、O(PN+α)くらいで行ける気がしてくる。
- なんだかんだで計9WAを重ね、最終的にAC。やったぜ！
- 提出コードでは配列を10万まで用意してますが、Q/2でよかったです。
#include <iostream> #include <stdio.h> using namespace std; const long long INF = 1000000000000000LL; int main(){ int N, P, Q, D; int d[1000], a[1000], b[1000]; static long long dp[2][100001]; while(scanf("%d %d %d %d", &N, &P, &Q, &D), N){ for(int i=0;i<N;i++) scanf("%d %d %d", &d[i], &a[i], &b[i]); for(int j=0;j<=100000;j++) dp[0][j] = dp[1][j] = INF; dp[0][0] = 0; for(int i=0;i<N;i++){ int cur = i%2, next = 1-cur; long long dist = (i==0 ? d[i] : d[i]-d[i-1]); long long low = INF; for(int j=0;j<=100000;j++){ long long tmp = dp[cur][j]+dist*j*j; dp[next][j] = min(tmp, low); if(j>P && ((long long)D-d[i])*(2*j+1) >= Q) break; low = min(low, tmp+b[i])+a[i]; } } long long res = INF; for(int i=P;i<=100000;i++) res = min(res, dp[N%2][i]+((long long)D-d[N-1])*i*i-(long long)i*Q); cout << res << endl; } }
H. Read Me
- 「簡単なお仕事」というのが罠に見えて仕方ない。
- とりあえず、横着して入力の最後だけ見る。
- "#"ならB確定
- "0"ならE確定
- "0 0"ならC確定
- "0 0 0"ならF確定
- "0 0 0 0"ならA, D, Gどれか
- で、Dなら2行目に数字が3つ来るのでそれで判別できる。
- あとは、AよりもGの方が入力の制約が厳しいので、それを調べるだけ。
- 最初、テストケースの数を見落としてて50%どまりでした。
#include <iostream> #include <vector> #include <string> #include <sstream> #include <stdio.h> using namespace std; int main(){ while(true){ vector<string> vs; string str; getline(cin, str); if(str==string(20,'@')) break; vs.push_back(str); while(getline(cin, str)){ if(str == string(10, '@')) break; vs.push_back(str); } if(vs.back() == "#") { puts("B"); continue; } if(vs.back() == "0") { puts("E"); continue; } if(vs.back() == "0 0") { puts("C"); continue; } if(vs.back() == "0 0 0") { puts("F"); continue; } if(vs.size() < 2) { puts("?"); continue; } int sp = 0; for(int i=0;i<vs[1].size();i++) if(vs[1][i] == ' ') sp++; if(sp == 2) { puts("D"); continue; } bool ok = (vs.size() > 21); for(int i=0;(!ok)&&i<vs.size();i++){ int a, b, c, d; sscanf(vs[i].c_str(), "%d %d %d %d", &a, &b, &c, &d); if(a > 100000 || b > 100000 || c > a || d > a) ok = true; } if(ok) puts("A"); else puts("?"); } }
F. Christmas Magic
- タイトルにMagicと入ってたので、部分点だけでも欲しい…。
- というわけで、MN≦16の場合に着目。
- MN個のマスについて、切り上げるかどうかを全探索
- 整合性が取れるもののうち、誤差が最も小さいものが答え
- 整合性が取れるものがなければ"Merry Christmas!"
- 無駄にコードが長いので、提出コードは略。
- -
A:100/4, B:100/1, C:100/1, D:100/10, E:---/-, F:10/1, G:---/-, H:100/3
計:510/1321
と、奇跡的にDが通り全体で2位という奇跡的な結果となりました。
提出回数の多さは反省すべき点ですが、これは素直に嬉しい結果です。
今までこんなに充実したクリスマスがあっただろうかと。
そんなわけで、とても楽しかったです。
関係者の皆様お疲れさまでした。そして、ありがとうございました。
