Hatena::Grouptopcoder

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

 | 

2013-06-24

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

A. Malek Dance Club

  • ぱっと見でさっぱりわからない・・・orz
  • とりあえず実験してみようか
  • 小さいケースで試してみる
  • ・・・
  • 文字列の長さ-1で左シフトするだけ・・・?
  • 書いてみる
  • Accepted
  • 証明まったく思いつかない・・・orz
const ll MOD = 1000000007;

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

  string line;
  cin >> line;
  int n = line.size();
  //int x = 0;
  //REP(i, line.size()) {
  //  x <<= 1;
  //  if (line[i] == '1') {
  //    x |= 1;
  //  }
  //}

  //int answer = 0;
  //REP(a, (1 << n)) {
  //  int b = a ^ x;
  //  REP(c, (1 << n)) {
  //    int d = c ^ x;
  //    if (a < c && b > d) {
  //      ++answer;
  //    }
  //  }
  //}
  //cout << answer << endl;
  ll answer = 0;
  REP(i, n) {
    answer <<= 1;
    answer %= MOD;
    if (line[i] == '1') {
      ++answer;
      answer %= MOD;
    }
  }

  REP(i, n - 1) {
    answer <<= 1;
    answer %= MOD;
  }

  cout << answer << endl;
}

B. Psychos in a Line

  • パッと見これもわからない・・・orz
  • なんかすごいデータ構造でもあるのかな・・・?
  • ・・・
  • とりあえず自分の知っているデータ構造から使えそうなものを考えてみよう
  • 途中の要素の削除が高速なデータ構造って行ったら連結リストくらいしか知らない・・・
  • 次のターンで右のサイコを殺すサイコは、一つ前のターンでも必ず右のサイコを殺しているはず
  • 次のターンで右のやつを殺す可能性のあるサイコのリストを保持して、そいつらだけ調べれば枝刈りできる・・・?
  • ということは・・・
  • vector<list<int>::iterator> とかサイコなデータ構造を使うのか・・・
  • ・・・
  • とりあえず書いてみよう
  • Accepted
  • リストのイテレーターの配列操作とかよくバグらずにかけたなぁ・・・
int main() {
	std::ios::sync_with_stdio(false);

  int n;
  cin >> n;
  list<int> psychos;
  REP(i, n) {
    int psycho;
    cin >> psycho;
    psychos.push_back(psycho);
  }

  vector<list<int>::iterator> marked;
  for (list<int>::iterator it = psychos.begin(), itEnd = psychos.end(); it != itEnd; ++it) {
    marked.push_back(it);
  }

  int answer = -1;
  do {
    ++answer;
    vector<list<int>::iterator> nextMarked;
    for (vector<list<int>::iterator>::reverse_iterator rit = marked.rbegin(), ritEnd = marked.rend(); rit != ritEnd; ++rit) {
      list<int>::iterator psycho = *rit;
      if (*psycho == psychos.back()) {
        continue;
      }
      list<int>::iterator rightPsycho = psycho;
      ++rightPsycho;
      if (*psycho > *rightPsycho) {
        if (!nextMarked.empty() && nextMarked.back() == rightPsycho) {
          nextMarked.pop_back();
        }
        psychos.erase(rightPsycho);
        nextMarked.push_back(psycho);
      }
    }
    reverse(ALL(nextMarked));
    swap(marked, nextMarked);
  } while (!marked.empty());

  cout << answer << endl;
}

C. Kalila and Dimna in the Logging Industry

  • 問題文を読むのに一苦労
  • O(N^2)の自明なDPTLE
  • どうしよう・・・
  • ビームサーチでもしてみようか
  • ・・・
  • TLE <-> WA
  • だめだこりゃorz

D. Have You Ever Heard About the Word?

  • 分かりませんでした

E. Ping-Pong

  • 読んでいません

Hack

  • 珍しく何もしませんでした

System Test

#Who= * A 500B 1000C 1500D 2500E 2500
151nodchip1256 460 00:20796 00:51-11

1978 -> 2006 可もなく不可もなくという成績でした。この成績でレーティングが微増したのが謎です・・・。

ゲスト



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