Hatena::Grouptopcoder

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

 | 

2012-09-01

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

問題がまともに解けず、残念な結果となってしまいました。

A. Little Elephant and Problem

  • 貪欲・・・?
  • まず左から見ていって一番初めに減少する直前の値は入れ替えなければならないはず (<-間違い)
  • 次に右側を見て行って一番小さい数と交換すれば良いはず (<-違うっぽい)
    • 何故ならばそれ以外と交換すると、それより小さい数との順序が不正になってしまうため
  • 複数ある場合は一番右側のものと交換すればいいはず (<-???)
  • Wrong answer on pretest 8
  • うむむ・・・?
  • 右側から見ていく時は初めて増加する直前の値と交換するのかな?
  • Wrong answer on pretest 8
  • よくわからない・・・
  • WA連発
  • 左右から見るときに同じ値が続いている場合は最も手前の物を選ぶようにしてみる
  • Accepted
bool solve(vector<int> a) {
  int N = a.size();
  bool ok = true;
  REP(i, N - 1) {
    if (a[i] > a[i + 1]) {
      ok = false;
      break;
    }
  }

  if (ok) {
    return true;
  }

  int left = 0;
  for (; left + 1 < N; ++left) {
    if (a[left] > a[left + 1]) {
      break;
    }
  }

  for (; 0 < left; --left) {
    if (a[left - 1] != a[left]) {
      break;
    }
  }

  int right = N - 1;
  for (; right > 0; --right) {
    if (a[right - 1] > a[right]) {
      break;
    }
  }

  for (; right + 1 < N; ++right) {
    if (a[right] != a[right + 1]) {
      break;
    }
  }

  swap(a[left], a[right]);

  REP(i, N - 1) {
    if (a[i] > a[i + 1]) {
      return false;
    }
  }

  return true;
}

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

  int N;
  cin >> N;
  vector<int> a;
  REP(n, N) {
    int value;
    cin >> value;
    a.push_back(value);
  }

  cout << (solve(a) ? "YES" : "NO") << endl;
}

B. Little Elephant and Array

  • クエリ問題苦手・・・
  • どうするか全くわからない
  • 平方分割・・・?
  • 違うっぽい
  • 包除原理・・・?
  • 使いドコロがわからない
  • ・・・
  • orz
  • 以下はPracticeで通したソースです
  • xの候補について出現累積回数を求め全クエリについてまとめて処理すると通るようです
  • クエリ問題は前処理が命ということを忘れていました
int main() {
	std::ios::sync_with_stdio(false);

  int N, M;
  cin >> N >> M;
  
  vector<int> as;
  map<int, int> numberToCount;
  REP(n, N) {
    int a;
    cin >> a;
    as.push_back(a);
    ++numberToCount[a];
  }
  
  vector<int> ls, rs;
  REP(m, M) {
    int l, r;
    cin >> l >> r;
    --l;
    --r;
    ls.push_back(l);
    rs.push_back(r);
  }

  vector<int> candidates;
  for (map<int, int>::iterator it = numberToCount.begin(), itEnd = numberToCount.end(); it != itEnd; ++it) {
    if (it->first <= it->second) {
      candidates.push_back(it->first);
    }
  }

  vector<int> answer(M);
  for (vector<int>::iterator it = candidates.begin(), itEnd = candidates.end(); it != itEnd; ++it) {
    int candidate = *it;
    vector<int> acc;
    acc.push_back(as[0] == candidate);
    for (int n = 1; n < N; ++n) {
      acc.push_back(acc.back() + (as[n] == candidate));
    }

    REP(m, M) {
      int x = acc[rs[m]];
      if (ls[m]) {
        x -= acc[ls[m] - 1];
      }
      answer[m] += x == candidate;
    }
  }

  REP(m, M) {
    cout << answer[m] << endl;
  }
}

Hack

  • A問題を見てみる
  • 中位以上の人はみんなソートしてdiff取ってる
  • 頭いいなぁ・・・
  • orz

System Test

# Who = * A 500 B 1000C 1500D 2000E 2500
434nodchip150 150 01:25

1982->1889 非常に残念な成績になってしまいました。今夜のSRMで汚名返上出来ればと思います。

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