Hatena::Grouptopcoder

nodchipのTopCoder日記 このページをアンテナに追加 RSSフィード

 | 

2013-06-29

Codeforces Round #190 (Div. 1) 11:49 Codeforces Round #190 (Div. 1) - nodchipのTopCoder日記 を含むブックマーク はてなブックマーク - Codeforces Round #190 (Div. 1) - nodchipのTopCoder日記 Codeforces Round #190 (Div. 1) - nodchipのTopCoder日記 のブックマークコメント

Cielだからir5さん・・・?

A. Ciel and Robot

  • naive解法はTLE
  • 対象となっている点の近くまで処理をすっ飛ばして、点の近くでnaiveに処理すれば良さそう
  • どうやってすっ飛ばすか・・・
  • 周期を使うのは明白・・・
  • 二分探索で点の近くまで近づけてみる?
  • 書いてみた
  • Submit
  • Hacked
  • あれ・・・

以下はPracticeで通したコードです。同じ所をぐるぐる回る場合の処理が一部抜けていたor処理をせずともそもそも二分探索のコードが勝手に処理してくれたっぽいです

double square(double a, double b) {
  return a * a + b * b;
}

int main() {
	std::ios::sync_with_stdio(false);

  int dx[256];
  int dy[256];
  dx['U'] = 0;
  dy['U'] = 1;
  dx['D'] = 0;
  dy['D'] = -1;
  dx['L'] = -1;
  dy['L'] = 0;
  dx['R'] = 1;
  dy['R'] = 0;

  int a, b;
  cin >> a >> b;
  string s;
  cin >> s;

  ll stepX = 0;
  ll stepY = 0;
  REP(i, s.size()) {
    stepX += dx[s[i]];
    stepY += dy[s[i]];
  }

  // 整数用二分探索
  ll L = 0;
  ll R = 1LL << 32;
  while (L + 3 < R){
    ll LL = (L * 2 + R) / 3;
    ll RR = (L + R * 2) / 3;
    double LLcost = square(stepX * LL - a, stepY * LL - b);
    double RRcost = square(stepX * RR - a, stepY * RR - b);
	  if (LLcost > RRcost){
		  L = LL;
	  } else {
		  R = RR;
	  }
  }

  ll begin = MAX(0LL, (L + R) / 2 - 10000);
  ll x = stepX * begin;
  ll y = stepY * begin;
  REP(loop, 20000) {
    REP(i, s.size()) {
      if (x == a && y == b) {
        cout << "Yes" << endl;
        return 0;
      }
      x += dx[s[i]];
      y += dy[s[i]];
    }

    if (x == a && y == b) {
      cout << "Yes" << endl;
      return 0;
    }
  }

  cout << "No" << endl;
}

B. Ciel and Duel

  • 日本的な問題だなぁ・・・
  • とりあえず場合分けを考えてみる
  • 多分DEF全員倒す場合と一人も倒さない場合に分けられる・・・?
  • DEF全員倒す場合はATK全員倒すか倒さないかに分けられる・・・? (<- 間違い)
  • DEF倒さない場合はATKと二部マッチング? (<- 少し間違い)
  • 書いてみる
  • サンプル合った
  • Submit
  • Wrong answer on pretest 5
  • 分からないorz

以下はPracticeで通したコードです。実際の場合分けは総力戦かATKを何人か倒す場合の2パターンに分かれ、二部マッチングは貪欲で行けるようです。

int solveAllOutBattle(vector<int> my, vector<int> atk, vector<int> def) {
  assert(my.size() >= atk.size() + def.size());
  REP(i, def.size()) {
    vector<int>::iterator it = upper_bound(ALL(my), def[i]);
    if (it == my.end()) {
      return 0;
    }
    my.erase(it);
  }
  reverse(ALL(my));
  reverse(ALL(atk));
  REP(i, atk.size()) {
    if (my[i] < atk[i]) {
      return 0;
    }
  }
  return accumulate(ALL(my), 0) - accumulate(ALL(atk), 0);
}

int solveLocalizedBattles(vector<int> my, vector<int> atk) {
  reverse(ALL(my));
  int N = MIN(my.size(), atk.size());
  int answer = 0;
  REP(i, N) {
    if (my[i] < atk[i]) {
      break;
    }
    answer += my[i] - atk[i];
  }
  return answer;
}

int main() {
  std::ios::sync_with_stdio(false);

  int n, m;
  cin >> n >> m;
  vector<int> my, atk, def;
  REP(i, n) {
    string position;
    int strength;
    cin >> position >> strength;
    if (position == "ATK") {
      atk.push_back(strength);
    } else {
      def.push_back(strength);
    }
  }

  REP(i, m) {
    int strength;
    cin >> strength;
    my.push_back(strength);
  }

  sort(ALL(my));
  sort(ALL(atk));
  sort(ALL(def));

  int answer = 0;
  if (n <= m) {
    MAX_UPDATE(answer, solveAllOutBattle(my, atk, def));
  }
  MAX_UPDATE(answer, solveLocalizedBattles(my, atk));
  cout << answer << endl;
}

C. Ciel the Commander

  • とりあえず一直線の場合を考えてみる
  • 多分グレイコードが一番効率が良いと思う (<- ???)
  • 木の場合もグレイコードっぽく行けるかどうか考えてみる
  • ダメっぽい
  • さっぱりわからない

D. Ciel and Flipboard

  • ネタ回答として焼きなましを送ってみる
  • Wrong answer on pretest 9
  • 思ったより解けた
  • orz

E. Ciel and Gondolas

  • ちゃんと読んでいません

System Test

#Who=A 500B 1000C 1500D 2000E 2500
377nodchip0 -2 -2 -1 -1

2006->1916 一気に落ちてしまいました。紫まで一直線です・・・orz

トラックバック - http://topcoder.g.hatena.ne.jp/nodchip/20130629
 |