Hatena::Grouptopcoder

Wrong Answer -- japlj このページをアンテナに追加 RSSフィード

2013-04-07

Codeforces 83E -- Two Subsequences

| 14:26 | Codeforces 83E -- Two Subsequences - Wrong Answer -- japlj を含むブックマーク はてなブックマーク - Codeforces 83E -- Two Subsequences - Wrong Answer -- japlj Codeforces 83E -- Two Subsequences - Wrong Answer -- japlj のブックマークコメント

http://codeforces.com/problemset/problem/83/E

面白い問題だったので思考過程をメモ.

(当然ですが解法バレがありますので自分で考えて解きたい人は注意)


  • 問題内容自体は前に読んで知っていたので,まずは細部を思い出すために軽く読む.
  • 愚直に考えれば a の i 番目まで見ていて,b の最後のパターンと c の最後のパターンをもっておくとして状態数は n * 420 ぐらい必要そうだとわかる.
  • でもよく考えると a の i 番目まで見ているということは b, c どちらかの最後のパターンは ai なのだから,そうでないほうだけ覚えておけばよくて,そうすると n * 220 ぐらいにはなるけどまだ大きい.
  • b, c は対称だから,状態は (i, ai を入れてない方の最後のパターン) で表現できる.
  • i を小さい方から回すとすれば ai を入れてない方の最後のパターン,という 220 通りの状態に大して各 i ごとに答を更新していけばよいことになる → これでようやく持つべき状態がメモリに乗りそうな大きさになった.
  • とはいえまだ n * 220 であることに変わりはないが,ここで状態の更新について考えてみる.
  • ai+1 を入れる時,ai を入れた方に入れるかそうでない方に入れるかの 2 通りがある.
    • ai を入れた方に入れる時,状態はどう変わるか考えると,かかるコストは ai と ai+1 をつなげるときを考えれば良いのですぐわかる.で,このとき ai を入れてない方のパターンはもちろん変わらないままなので,すべてのパターン p について dp[i + 1][p] = dp[i][p] + cost とすればよいことがわかる.
    • そうでない方に入れる時,状態の変化は単純になる.というのは,この場合次の状態としてありうるのは (i + 1, ai) だけだから(aiが入ってない方に ai+1 を入れるので,次に ai+1 が入ってない方というのは ai になる).で,かかるコストというのを考えると,パターン p の下 k 桁と ai+1 の上 k 桁が一致しているときにコストは (各パターンの長さ) - k となる.それぞれの k (k ≧ 0)ごとに状態を更新することにして,ai+1 の上 k 桁が,その下 k 桁と一致しているようなパターン p すべてについて dp[i + 1][ai] = min{dp[i][p] + (パターンの長さ) - k} とすればよい.
  • さてもちろん,これを愚直にやれば n * 220 のままだが,この更新について考えると dp配列に必要なのは次の操作を備えることだとわかる.
    • すべての p に対し dp[p] += 一定値 を処理する.
    • ある p に対し dp[p] = 一定値 を処理する.
    • 長さ k と,長さ k のパターン x に対し,下 k 桁が x であるようなすべてのパターン p に大して dp[p] の最小値を求める.
  • 以上の操作を爆速で行えればよいが,これ自体は特に難しいデータ構造というわけではない(全体に対して足されている値というのを別にもっておけば一個目はできる,二個目はそもそもO(1)である,三個目は各 k, x についてクエリへの答となる配列 min[k][x] を用意しておけばよい).
  • 計算量は O(2^(パターン長) + n * パターン長) となった.これで解ける.

ゲスト



トラックバック - http://topcoder.g.hatena.ne.jp/JAPLJ/20130407