Hatena::Grouptopcoder

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

 | 

2014-08-02

AtCoder Regular Contest 027 22:42 AtCoder Regular Contest 027 - nodchipのTopCoder日記 を含むブックマーク はてなブックマーク - AtCoder Regular Contest 027 - nodchipのTopCoder日記 AtCoder Regular Contest 027 - nodchipのTopCoder日記 のブックマークコメント

A - 門限

  • 掛けて引く
  • AC
int main() {
	std::ios::sync_with_stdio(false);

  int h, m;
  cin >> h >> m;
  cout << 18 * 60 - h * 60 - m << endl;
}

B - 大事な数なのでZ回書きまLた。

  • あれ・・・、二問目にしては難しい・・・。
  • これどうやるんだろう・・・
  • 数字が確定するアルファベットはおいといて
  • 先頭のアルファベットまたはそれと等価なものが出たら9倍
  • それ以外なら10倍とかそんな感じ?
  • ・・・
  • UnionFind使って管理するのが楽かなぁ?
  • AC
bool isNumber(UnionFind& uf, int ch) {
  for (int number = '0'; number <= '9'; ++number) {
    if (uf.findSet(ch, number)) {
      return true;
    }
  }
  return false;
}

bool isLeading(UnionFind& uf, const string& s1, const string& s2, int ch) {
  return uf.findSet(s1[0], ch) || uf.findSet(s2[0], ch);
}

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

  int N;
  string s1, s2;
  cin >> N >> s1 >> s2;

  UnionFind uf(128);
  REP(i, N) {
    uf.unionSet(s1[i], s2[i]);
  }

  ll answer = 1;
  set<int> roots;
  REP(i, N) {
    char ch = s1[i];
    if (isNumber(uf, ch)) {
      continue;
    }
    
    if (roots.count(uf.root(ch))) {
      continue;
    }

    if (isLeading(uf, s1, s2, ch)) {
      answer *= 9;
    }
    else {
      answer *= 10;
    }
    roots.insert(uf.root(ch));
  }

  cout << answer << endl;
}

C - 最高のトッピングにしような

  • あれ?部分点があるってことは dp[N][X][Y] じゃないの・・・?
  • スペシャルチケットを使用する枚数って少ないほうが有利だから O(NXY) だと思うのだけれど・・・
  • とりあえず書いてみる
  • AC
  • あれ?部分点はスペシャルチケットの使い方を全部試した時だったのかなぁ?
int main() {
	std::ios::sync_with_stdio(false);

  int X, Y, N;
  cin >> X >> Y >> N;
  map<pair<int, int>, int> dp;
  dp[MP(X, Y)] = 0;
  REP(n, N) {
    int t, h;
    cin >> t >> h;

    map<pair<int, int>, int> next;
    for (const auto& from : dp) {
      next.insert(from);

      if (from.first.first + from.first.second < t || from.first.first <= 0) {
        continue;
      }

      int x = max(1, t - from.first.second);
      MAX_UPDATE(next[MP(from.first.first - x, from.first.second - t + x)], from.second + h);
    }

    swap(dp, next);
  }

  int answer = 0;
  for (const auto& a : dp) {
    MAX_UPDATE(answer, a.second);
  }

  cout << answer << endl;
}

D - ぴょんぴょんトレーニング

  • この問題作ったの旧とざんげざんさんかなぁ?
  • とりあえず部分点はDPするだけ。
  • TLE 30
  • 満点解法はどうやるんだろう・・・。
  • なんかスキップリスト的な何かが作れると嬉しい気がする
  • ジャンプ先が10までなので、これをうまくつかえないかなぁ?
  • DP表の中で連続する10個から、1個スライドして連続する10個を計算するには、行列を掛けてやれば良さそう
  • ならば前処理として行列を分割統治で2^p個くらい掛けたやつを作っておけば行けそう・・・?
  • ・・・?
  • 保存するためのメモリが足りない気がする・・・。
  • 256以下個くらいしかかけていない行列を削除すればメモリ足りる・・・?
  • ・・・
  • だめだ・・・、実装力が足りなすぎて実装できない。
const int MOD = 1000000007;
int main() {
	std::ios::sync_with_stdio(false);

  int N;
  cin >> N;
  vector<int> hs;
  hs.push_back(0);
  REP(n, N) {
    int h;
    cin >> h;
    hs.push_back(h);
  }

  int D;
  cin >> D;
  REP(d, D) {
    int s, t;
    cin >> s >> t;
    vector<int> dp(N + 16);
    dp[s] = 1;

    for (int from = s; from < t; ++from) {
      for (int h = 1; h <= hs[from]; ++h) {
        dp[from + h] += dp[from];
        dp[from + h] %= MOD;
      }
    }

    cout << dp[t] << endl;
  }
}

結果

順位ユーザ名門限大事な数なのでZ回書きまLた。最高のトッピングにしようなぴょんぴょんトレーニング得点 / Total
15nodchip 100 00:44100 16:08100 28:4730 42:12330 42:12

実力相応の成績だと思います。Dの満点解法を実装できる方はすごいと思います。

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