Hatena::Grouptopcoder

TopCoderの学習のお時間 RSSフィード

戦績(topcoder.com) / 戦績(competitiveprogramming.info) / 過去記事 / 日記

 | 

2010-12-26

[]hos' Xmas Contest 2010 00:41 はてなブックマーク - hos' Xmas Contest 2010 - TopCoderの学習のお時間

2010-12-25 14:00-18:00

http://judge.imoz.jp/?cid=12

http://hos.gozaru.jp/contest/xmas2010/

熱いクリスマスでした。


  • A
    • まあやるだけ。最初2つの家が常に同じ方向にあると思い込んでハマってしまった。サンプルはよく読みましょう
    • 60点…
    • 整数オーバーフローかと思ったけどそうではない
    • 問題文を読み直すと、家は異なる場所にある、と書いてある。これが未考慮だった
    • 100点
  • B
    • 2分くらい構文解析をマジメに書こうとしたが
    • 結果が偶奇だけで良いことと演算子が+-しかないことから、出現する数値のうち奇数が何個あるかだけを見ればよい
    • 奇数が偶数個→"EVEN"、奇数が奇数個→"ODD"
    • 100点
    • 提出者のうちちゃんと構文解析した人と上みたいに手抜きした人の割合はどんなもんだったのだろう
  • C
    • グラフの特定の頂点集合をカバーする部分グラフの中でコスト最小のものを求めるんですね
    • 計算量的にはN回最小全域木を求めるというようなくらいか
    • Σsi<=10がキーポイントになってbitDPでもやるのかと思ったが全然わからない
    • コンテスト終了後に検索してみる→最小シュタイナー木問題てのがあるのか。初めて知った
    • でもそれじゃこんなに多くの人が解かないはず
    • 他の人の参加記を読む→"とてもお気に入り"とそうじゃないのを逆に考えてた…
    • 100個中90個以上が"とてもお気に入り"ってお気に入りインフレしすぎだろw
    • これって意図的なトラップだったのだろうか?
  • D
    • まずDP解法が浮かぶが
    • プレゼント買う個数が最大でQまであり得るから、そのままでは計算量O(NQ)でTLEしてしまう
    • とりあえず部分点狙いで書く
    • 30点
    • 最後の店から家までの距離をdとすると、あり得る最大の購入個数はmax(P,Q/d)になることを利用して定数倍最適化
    • 50点
  • 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

vector<string> input;

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;
  }
}
 |