Hatena::Grouptopcoder

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

 | 

2012-12-08

第2回早稲田大学プログラミングコンテスト2012 18:37 第2回早稲田大学プログラミングコンテスト2012 - nodchipのTopCoder日記 を含むブックマーク はてなブックマーク - 第2回早稲田大学プログラミングコンテスト2012 - nodchipのTopCoder日記 第2回早稲田大学プログラミングコンテスト2012 - nodchipのTopCoder日記 のブックマークコメント

A - 団子とうさぎ

  • やるだけ
  • Accepted
int main() {
  std::ios::sync_with_stdio(false);

  int N, M;
  cin >> N >> M;
  int dango = 0;
  for (int n = 1; n <= N; ++n) {
    dango += n * n;
  }
  cout << dango % M << endl;
}

B - 雨上がり

  • DP
  • やるだけ
  • Accepted
int main() {
  std::ios::sync_with_stdio(false);
  int N;
  string S;
  cin >> N >> S;
  int dp[128];
  fill_n(dp, 128, INT_MAX);
  dp[0] = 0;

  for (int n = 0; n < N; ++n) {
    for (int i = 1; i <= 3 && n + i < N; ++i) {
      MIN_UPDATE(dp[n + i], dp[n] + (S[n + i] == 'X' ? 1 : 0));
    }
  }
  cout << dp[N - 1] << endl;
}

C - 至高のケーキ

  • 全探索
  • ループがちょっと面倒
  • 配列の90度回転は斜め反転+左右反転で代用
  • Accepted
int search(const vector<vector<char> >& cake, int left, int top) {
  int X = cake[0].size();
  int Y = cake.size();
  int sum = 0;
  for (int size = 1; size + top <= Y && size + left <= X; ++size) {
    int partialSum = 0;
    for (int i = 0; i < size; ++i) {
      char ch = cake[top + size - 1][left + i];
      if (ch == 'X') {
        return sum;
      }
      partialSum += ch - '0';
    }
    sum += partialSum;
  }
  return sum;
}

int search(const vector<vector<char> >& cake) {
  int X = cake[0].size();
  int Y = cake.size();
  int best = 0;
  REP(left, X) {
    REP(top, Y) {
      MAX_UPDATE(best, search(cake, left, top));
    }
  }
  return best;
}

vector<vector<char> > rot(const vector<vector<char> >& cake) {
  int X = cake[0].size();
  int Y = cake.size();
  vector<vector<char> > r(X, vector<char>(Y));
  REP(x, X) {
    REP(y, Y) {
      r[x][y] = cake[y][x];
    }
  }
  REP(x, X) {
    reverse(ALL(r[x]));
  }

  return r;
}

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

  int Y, X;
  cin >> Y >> X;
  vector<vector<char> > cake;
  REP(y, Y) {
    string line;
    cin >> line;
    cake.push_back(vector<char>(ALL(line)));
  }

  int best = 0;
  REP(i, 4) {
    MAX_UPDATE(best, search(cake));
    cake = rot(cake);
  }

  cout << best << endl;
}

D - 5キューブ

  • 昔考えた問題
  • ・・・
  • Wrong Answerがとれないorz
  • ・・・
  • 解けませんでした

E - 独立記念日

  • 分かりませんでした
  • Twitterによると嘘解法が存在するらしい

F - 僕は宇宙人

  • [r][c][l][dir]でダイクストラ
  • Accepted
const int dr[] = {0, -1, 0, 1};
const int dc[] = {1, 0, -1, 0};

struct State {
  int r, c, lastDirection, l, cost;
  bool operator < (const State& rh) const {
    return cost != rh.cost ? cost < rh.cost :
      r != rh.r ? r < rh.r :
      c != rh.c ? c < rh.c :
      l != rh.l ? l < rh.l :
      lastDirection < rh.lastDirection;
  }
};

bool in(int r, int c, int R, int C) {
  return 0 <= r && r < R && 0 <= c && c < C;
}

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

  int R, C, L;
  cin >> R >> C >> L;
  string S;
  char table[128][128];
  cin >> S;
  REP(r, R) REP(c, C) {
    cin >> table[r][c];
  }

  // r, c, l, lastDirection
  static int dp[128][128][128][4];
  fill_n((int*)dp, sizeof(dp) / sizeof(int), INT_MAX);
  set<State> states;
  REP(r, R) REP(c, C) REP(dir, 4) {
    dp[r][c][0][dir] = 0;

    State s;
    s.r = r;
    s.c = c;
    s.l = 0;
    s.lastDirection = dir;
    s.cost = 0;
    states.insert(s);
  }

  while (!states.empty()) {
    //REP(l, L) {
    //  cout << endl;
    //  REP(r, R) {
    //    REP(c, C) {
    //      REP(dir, 4) {
    //        int cost = dp[r][c][l][dir];
    //        if (cost != INT_MAX) {
    //          cout << cost;
    //        } else {
    //          cout << "-";
    //        }
    //      }
    //      cout << " ";
    //    }
    //    cout << endl;
    //  }
    //}

    State current = *states.begin();
    states.erase(states.begin());

    if (dp[current.r][current.c][current.l][current.lastDirection] != current.cost) {
      continue;
    }

    REP(dir, 4) {
      if (current.lastDirection == dir) {
        continue;
      }

      int r = current.r;
      int c = current.c;
      while (true) {
        r += dr[dir];
        c += dc[dir];

        if (!in(r, c, R, C)) {
          break;
        }

        if (table[r][c] == S[current.l]) {
          break;
        }
      }

      if (!in(r, c, R, C)) {
        continue;
      }

      // r, c, l, lastDirection
      int nextCost = current.cost + abs(current.r - r) + abs(current.c - c);
      if (dp[r][c][current.l + 1][dir] < nextCost) {
        continue;
      }

      dp[r][c][current.l + 1][dir] = nextCost;

      if (current.l + 1 == L) {
        continue;
      }

      State next;
      next.r = r;
      next.c = c;
      next.l = current.l + 1;
      next.lastDirection = dir;
      next.cost = nextCost;
      states.insert(next);
    }
  }

  int answer = INT_MAX;
  REP(r, R) REP(c, C) REP(dir, 4) {
    MIN_UPDATE(answer, dp[r][c][L][dir]);
  }
  if (answer == INT_MAX) {
    answer = -1;
  }
  cout << answer << endl;
}

G - だるま落とし

  • うげ・・・データ構造系orz
  • 部分木の総和が求められる二分探索木があれば行けそう
  • Spaghetti Source のAVL木にlower()とend()なる関数を追加してみる
  • Accepted
template <class T>
struct avl_tree {
  struct node {
    // ブロックindex
    T key;
    int size, height;
    node *child[2];

    // ブロックの高さ
    ll h;
    // ここ以下の高さの和
    ll sum;
    node(const T &key, ll h) : key(key), size(1), height(1), h(h), sum(h) {
      child[0] = child[1] = 0; }
  } *root;
  typedef node *pointer;
  avl_tree() { root = NULL; }

  pointer find(const T &key) { return find(root, key); }
  node *find(node *t, const T &key) {
    if (t == NULL) return NULL;
    if (key == t->key) return t;
    else if (key < t->key) return find(t->child[0], key);
    else                   return find(t->child[1], key);
  }
  void insert(const T &key, ll h) { root = insert(root, new node(key, h)); }
  node *insert(node *t, node *x) {
    if (t == NULL) return x;
    if (x->key <= t->key) t->child[0] = insert(t->child[0], x);
    else                  t->child[1] = insert(t->child[1], x);
    t->size += 1;
    return balance(t);
  }
  void erase(const T &key) { root = erase(root, key); }
  node *erase(node *t, const T &x) {
    if (t == NULL) return NULL;
    if (x == t->key) {
      return move_down(t->child[0], t->child[1]);
    } else {
      if (x < t->key) t->child[0] = erase(t->child[0], x);
      else            t->child[1] = erase(t->child[1], x);
      t->size -= 1;
      return balance(t);
    }
  }
  node *move_down(node *t, node *rhs) {
    if (t == NULL) return rhs;
    t->child[1] = move_down(t->child[1], rhs);
    return balance(t);
  }
#define sz(t) (t ? t->size : 0)
#define ht(t) (t ? t->height : 0)
#define sm(t) (t ? t->sum : 0)
  node *rotate(node *t, int l, int r) {
    node *s = t->child[r];
    t->child[r] = s->child[l];
    s->child[l] = balance(t);
    if (t) t->size = sz(t->child[0]) + sz(t->child[1]) + 1;
    if (s) s->size = sz(s->child[0]) + sz(s->child[1]) + 1;
    return balance(s);
  }
  node *balance(node *t) {
    for (int i = 0; i < 2; ++i) {
      if (ht(t->child[!i]) - ht(t->child[i]) < -1) {
        if (ht(t->child[i]->child[!i]) - ht(t->child[i]->child[i]) > 0)
          t->child[i] = rotate(t->child[i], i, !i);
        return rotate(t, !i, i);
      }
    }
    if (t) t->height = max(ht(t->child[0]), ht(t->child[1])) + 1;
    if (t) t->size = sz(t->child[0]) + sz(t->child[1]) + 1;
    if (t) t->sum = sm(t->child[0]) + sm(t->child[1]) + t->h;
    return t;
  }
  pointer rank(int k) const { return rank(root, k); }
  pointer rank(node *t, int k) const {
    if (!t) return NULL;
    int m = sz(t->child[0]);
    if (k  < m) return rank(t->child[0], k);
    if (k == m) return t;
    if (k  > m) return rank(t->child[1], k - m - 1);
  }
  pair<pointer, ll> lower(ll target) const { return lower(root, target); }
  pair<pointer, ll> lower(node* t, ll target) const {
    if (!t) return MP((pointer)NULL, 0);
    ll m = sm(t->child[0]);
    if (target < m) return lower(t->child[0], target);
    if (m <= target && target < m + t->h) return MP(t, target - m);
    return lower(t->child[1], target - m - t->h);
  }
  pointer last() const { return last(root); }
  pointer last(node* t) const {
    if (!t) return NULL;
    if (!t->child[1]) return t;
    return last(t->child[1]);
  }
};

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

  int N, M;
  ll H;
  cin >> N >> M >> H;

  avl_tree<int> tree;
  int blockIndex = 0;

  REP(n, N) {
    ll a;
    cin >> a;
    tree.insert(blockIndex++, a);
  }

  string operation;
  ll arg;
  REP(m, M) {
    cin >> operation >> arg;

    if (operation == "add") {
      tree.insert(blockIndex++, arg);
    } else {

      ll lower = arg - H;

      pair<avl_tree<int>::node*, ll> t = tree.lower(lower);

      if (t.first == NULL) {
        cout << "miss" <<endl;
      } else if (t.second + 2 * H <= t.first->h || tree.last() == t.first) {
        cout << "go" << endl;
        tree.erase(t.first->key);
      } else {
        cout << "stop" << endl;
      }
    }
  }
}

H - ダイヤグラム

  • ものすごくDP
  • 電車を始発駅、終着駅の順にソート
  • 座標圧縮してから[1本しか走っていない駅の左端][1本しか走っていない駅の右端]
  • で行ける・・・?
  • Wrong Answer
  • とりあえずナイーブ解答で部分点を確認してみる
  • Wrong Answer
  • ・・・
  • ・・・え?
  • ・・・
  • 座標圧縮間違えた?
  • 座標圧縮せず、範囲をマップに持たせてみる
  • Accepted
  • ひどいorz
static const int MOD = 1000000007;

typedef long long ll;
template<ll M> struct G {
  ll x;
  G() : x(0) { }
  G(ll x) : x(x % M) { }
  G& operator += (const G& rh) { x = (x + rh.x) % M; return *this; }
  G& operator -= (const G& rh) { x = (x + M - rh.x) % M; return *this; }
  G& operator *= (const G& rh) { x = (x * rh.x) % M; return *this; }
  G& operator /= (const G& rh) { return *this *= rh.pow(M - 2); }
  G operator + (const G& rh) const { return G(*this) += rh; }
  G operator - (const G& rh) const { return G(*this) -= rh; }
  G operator * (const G& rh) const { return G(*this) *= rh; }
  G operator / (const G& rh) const { return G(*this) /= rh; }
  bool operator == (const G& rh) const { return x == rh.x; }
  bool operator != (const G& rh) const { return x != rh.x; }
  G& operator ++ () { return *this += 1; }
  G pow(ll e) const {
    G y(*this), v(1);
    for (; e; y *= y, e >>= 1)
      if (e & 1)
        v *= y;
    return v;
  }
  G C(ll k) {
    G v = 1;
    for (ll i = 1; i <= k; ++i) {
      v *= *this - i + 1;
      v /= i;
    }
    return v;
  }
};


struct State {
  int startInclusive;
  int endExclusive;
  //int numberOfTrains;
  State() {}
  State(int startInclusive, int endExclusive) : startInclusive(startInclusive), endExclusive(endExclusive) { }
  //State(int startInclusive, int endExclusive, int numberOfTrains) : startInclusive(startInclusive), endExclusive(endExclusive), numberOfTrains(numberOfTrains) { }
  bool operator < (const State& rh) const {
    //return startInclusive != rh.startInclusive ? startInclusive < rh.startInclusive :
    //  endExclusive != rh.endExclusive ? endExclusive < rh.endExclusive :
    //  numberOfTrains < rh.numberOfTrains;
    return startInclusive != rh.startInclusive ? startInclusive < rh.startInclusive : endExclusive < rh.endExclusive;
  }
};

typedef G<1000000007> GG;

int visit(const vector<pair<int, int> >& trains, int counter[16], int trainIndex, int maxIndex) {
  bool ok = true;
  for (int i = 1; ok && i <= maxIndex; ++i) {
    ok = counter[i] >= 2;
  }

  if (ok) {
    return 1 << (trains.size() - trainIndex);
  }

  if (trainIndex == trains.size()) {
    return 0;
  }

  int answer = 0;
  for (int i = trains[trainIndex].first; i <= trains[trainIndex].second; ++i) {
    ++counter[i];
  }
  answer += visit(trains, counter, trainIndex + 1, maxIndex);
  for (int i = trains[trainIndex].first; i <= trains[trainIndex].second; ++i) {
    --counter[i];
  }
  answer += visit(trains, counter, trainIndex + 1, maxIndex);
  answer %= MOD;
  return answer;
}

map<pair<pair<int, int>, int>, GG> memo;

GG visit(const vector<pair<int, int> >& trains, int maxIndex, int trainIndex, int prevStartInclusive, int prevEndExclusive) {
  if (prevStartInclusive == maxIndex && prevEndExclusive == maxIndex) {
    return GG(2).pow(trains.size() - trainIndex);
  }

  if (trains.size() == trainIndex) {
    return 0;
  }

  int startInclusive = trains[trainIndex].first;
  int endExclusive = trains[trainIndex].second + 1;
  if (prevStartInclusive < startInclusive) {
    return 0;
  }

  if (memo.count(MP(MP(prevStartInclusive, prevEndExclusive), trainIndex))) {
    return memo[MP(MP(prevStartInclusive, prevEndExclusive), trainIndex)];
  }

  GG answer = visit(trains, maxIndex, trainIndex + 1, prevStartInclusive, prevEndExclusive);
  
  State s;
  if (prevStartInclusive == startInclusive) {
    if (endExclusive <= prevEndExclusive) {
      // 1, 2
      s = State(endExclusive, prevEndExclusive);
    } else {
      // 3
      s = State(prevEndExclusive, endExclusive);
    }
  } else {
    if (endExclusive <= prevStartInclusive) {
      // 4, 5
      s = State(prevStartInclusive, prevEndExclusive);
    } else if (endExclusive <= prevEndExclusive) {
      // 6, 7
      s = State(endExclusive, prevEndExclusive);
    } else {
      // 8
      s = State(prevEndExclusive, endExclusive);
    }
  }
  answer += visit(trains, maxIndex, trainIndex + 1, s.startInclusive, s.endExclusive);

  return memo[MP(MP(prevStartInclusive, prevEndExclusive), trainIndex)] = answer;
}

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

  int maxIndex = 0;
  int N, M;
  cin >> N >> M;
  vector<pair<int, int> > trains;
  map<int, int> stationToIndex;
  REP(m, M) {
    int start, end;
    cin >> start >> end;
    stationToIndex[start] = 0;
    stationToIndex[end] = 0;
    trains.push_back(MP(start, end));
  }

  int index = 0;
  for (map<int, int>::iterator it = stationToIndex.begin(), itEnd = stationToIndex.end(); it != itEnd; ++it) {
    it->second = index++;
  }

  //REP(i, trains.size()) {
  //  trains[i].first = stationToIndex[trains[i].first];
  //  trains[i].second = stationToIndex[trains[i].second];
  //}

  sort(ALL(trains));

  //int counter[16];
  //CLEAR(counter);
  //cout << visit(trains, counter, 0, N) << endl;

  cout << visit(trains, N + 1, 0, 1, 1).x << endl;

  //// [start, end) -> count % M;
  //map<State, int> prev;
  //prev[State(0, 0)] = 1;

  //REP(i, trains.size()) {
  //  int startInclusive = trains[i].first;
  //  int endExclusive = trains[i].second + 1;
  //  map<State, int> next;

  //  for (map<State, int>::iterator it = prev.begin(), itEnd = prev.end(); it != itEnd; ++it) {
  //    int prevStartInclusive = it->first.startInclusive;
  //    int prevEndExclusive = it->first.endExclusive;
  //    if (prevStartInclusive < startInclusive) {
  //      continue;
  //    }

  //    State s;
  //    if (prevStartInclusive == startInclusive) {
  //      if (endExclusive <= prevEndExclusive) {
  //        // 1, 2
  //        s = State(endExclusive, prevEndExclusive);
  //      } else {
  //        // 3
  //        s = State(prevEndExclusive, endExclusive);
  //      }
  //    } else {
  //      if (endExclusive <= prevStartInclusive) {
  //        // 4, 5
  //        s = State(prevStartInclusive, prevEndExclusive);
  //      } else if (endExclusive <= prevEndExclusive) {
  //        // 6, 7
  //        s = State(endExclusive, prevEndExclusive);
  //      } else {
  //        // 8
  //        s = State(prevEndExclusive, endExclusive);
  //      }
  //    }

  //    next[s] += it->second;
  //    next[s] %= MOD;

  //    next[it->first] += it->second;
  //    next[it->first] %= MOD;
  //  }
  //  swap(prev, next);
  //}

  //int answer = 0;
  //for (map<State, int>::iterator it = prev.begin(), itEnd = prev.end(); it != itEnd; ++it) {
  //  if (it->first.startInclusive == index && it->first.endExclusive == index) {
  //    answer += it->second;
  //    answer %= MOD;
  //  }
  //}
  //cout << answer << endl;
}

I - その味は甘くて

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

結果

順位ユーザ名団子とうさぎ雨上がり至高のケーキ5キューブ独立記念日僕は宇宙人だるま落としダイヤグラムその味は甘くて得点 / Total
31nodchip50 02:1650 05:2375 20:15(18)-100 80:52100 121:39100 (4) 218:19-475 (4) 238:19

東京大学プログラミングコンテスト2012 18:36 東京大学プログラミングコンテスト2012 - nodchipのTopCoder日記 を含むブックマーク はてなブックマーク - 東京大学プログラミングコンテスト2012 - nodchipのTopCoder日記 東京大学プログラミングコンテスト2012 - nodchipのTopCoder日記 のブックマークコメント

A - 2012年12月02日

  • やるだけ
  • Accepted
int main() {
  std::ios::sync_with_stdio(false);

  string line;
  cin >> line;
  string year = line.substr(0, 4);
  string date = line.substr(5, 2) + line.substr(8, 2);
  sort(ALL(year));
  sort(ALL(date));
  cout << (year == date ? "yes" : "no") << endl;
}

B - 残像に口紅を

  • 最後のサンプル入出力が怪しい
  • もしかして後ろから貪欲?
  • Accepted
int main() {
  std::ios::sync_with_stdio(false);

  string line;
  cin >> line;
  set<char> rest;
  for (char ch = 'A'; ch <= 'H'; ++ch) {
    rest.insert(ch);
  }
  string answer;
  for (int i = line.size() - 1; i >= 0; --i) {
    if (!rest.count(line[i])) {
      continue;
    }
    answer += line[i];
    rest.erase(line[i]);
  }
  answer.insert(answer.end(), ALL(rest));
  reverse(ALL(answer));
  cout << answer << endl;
}

C - 森ですか?

  • 全く見当がつかないorz

D - 地図が2枚

  • アフィン変換行列を解いて・・・
  • ・・・って行列手書きするのしんどいorz
  • 複素数で計算すると一つの座標から4変数2式出てくるので、2つの座標で4変数4式で連立して計算すれば良さそう
  • 連立方程式はライブラリに任せる
  • Accepted
typedef complex<double> P;

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

  int N;
  cin >> N;
  vector<P> big, small;
  REP(n, N) {
    double x, y;
    cin >> x >> y;
    big.push_back(P(x, y));
  }
  REP(n, N) {
    double x, y;
    cin >> x >> y;
    small.push_back(P(x, y));
  }

  //REP(permutation, N) {
  //  rotate(small.begin(), small.begin() + 1, small.end());
  //  if (!isSimilar(big, small)) {
  //    continue;
  //  }

    matrix m(4, array(4));
    m[0][0] = 0.5 * big[0].real();
    m[0][1] = -0.5 * big[0].imag();
    m[0][2] = 1.0;

    m[1][0] = 0.5 * big[0].imag();
    m[1][1] = 0.5 * big[0].real();
    m[1][3] = 1.0;

    m[2][0] = 0.5 * big[1].real();
    m[2][1] = -0.5 * big[1].imag();
    m[2][2] = 1.0;

    m[3][0] = 0.5 * big[1].imag();
    m[3][1] = 0.5 * big[1].real();
    m[3][3] = 1.0;

    array a(4);
    a[0] = small[0].real();
    a[1] = small[0].imag();
    a[2] = small[1].real();
    a[3] = small[1].imag();

    LUinfo lu = LU_decomposition(m);
    array x = LU_backsubstitution(lu, a);

    assert(equal(hypot(x[0], x[1]), 1.0));

    P tra(x[2], x[3]);
    P rot(x[0], x[1]);
    P answer = -tra / (0.5 * rot - 1.0);

    printf("%.20f %.20f\n", answer.real(), answer.imag());
  //  break;
  //}


}

E - 選挙

  • これ二分探索だよね? (<-間違い)
  • Wrong Answer
  • ・・・なんぞこれ
  • 一部あってる
  • ううむ
  • ・・・
  • もしかして: Sheep
    • SRM 483 Div1 Hard Sheep
  • ・・・
  • 確か時間いっぱいまで下方向に調べていけば解けたはず
  • clock()関数で時間を測って1.9秒までめいいっぱい回す
  • Accepted
struct Remain {
  ll remain;
  int index;
  Remain() { }
  Remain(ll remain, int index) : remain(remain), index(index) { }
  bool operator < (const Remain& rh) const {
    return remain != rh.remain ? remain > rh.remain : index < rh.index;
  }
};

bool check(int N, const ll a[128], const ll b[128], ll sumA, ll m) {
  static ll seats[128];
  static Remain remains[128];
  ll rest = m;

  REP(n, N) {
    ll seat = a[n] * m / sumA;
    seats[n] = seat;
    rest -= seat;

    remains[n].index = n;
    remains[n].remain = a[n] * m % sumA;
  }

  sort(remains, remains + N);

  REP(i, rest) {
    ++seats[remains[i].index];
  }

  REP(n, N) {
    if (seats[n] < b[n]) {
      return false;
    }
  }

  return true;
}

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

  int N;
  cin >> N;
  ll a[128];
  ll b[128];
  ll sumA = 0;
  REP(n, N) {
    cin >> a[n] >> b[n];
    sumA += a[n];
  }

  // 整数用二分探索
  ll L = 0;
  ll R = 1000000000000000LL;
  //ll R = 0;
  while (L + 1 < R){
    ll M = (L + R) / 2;
    if (check(N, a, b, sumA, M)){
      R = M;
    } else {
      L = M;
    }
  }

  int counter = 0;
  ll bestAnswer = 0;
  ll answer = L + 1;
  while (clock() / double(CLOCKS_PER_SEC) < 1.9 && answer >= 0) {
    REP(loop, 100) {
      if (check(N, a, b, sumA, answer)) {
        bestAnswer = answer;
      }
      --answer;
    }
    ++counter;
  }
  cout << bestAnswer << endl;
  //cout << counter << endl;

}

F - Uinny

  • 元ネタはわかるけど・・・
  • ・・・
  • どうやるんだろう?
  • ・・・orz
  • 後ほど聞いた話ではハッシュの衝突という有名な話なのだそうです
  • ハッシュが衝突する短い単語を乱択で選んで、2つくっつけるのだそうです

G - k番目の文字列

  • DPっぽい
  • 無理

H - 区間スケジューリングクエリ

  • 区間クエリ・・・?
  • 分かりませんでした

I - 最短路クエリ

  • 部分点は上に戻らないことが保証されるけど・・・
  • 分かりませんでした

J - きたまさの逆襲

  • 見た感じフロー
  • 分かりませんでした

K - ラッピング

  • 分かりませんでした

L - じょうしょうツリー

  • 無理ですorz

結果

順位ユーザ名2012年12月02日残像に口紅を森ですか?地図が2枚選挙Uinnyk番目の文字列区間スケジューリングクエリ最短路クエリきたまさの逆襲ラッピングじょうしょうツリー得点 / Total
36nodchip100 03:05100 10:1450 22:42100 69:30200 (6) 220:493.98 (1) 153:47-(1)----553.98 (7) 620:07

微妙な結果となってしまいました。聞いた話によると、一人で出場するコンテストではなかったとのことです。

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