Hatena::Grouptopcoder

cafelier@SRM

cafelier のSRM参加記録です。コンテスト中に考えてたことを執拗に全部書き残すとどうなるだろうかという試み本番中にこういうコードが書きたかったなあ、という後で書いた反省コードを書き残す試み

スパムが来たのでしばらくコメント欄をはてなユーザ限定にしています、すみません、

 | 

2010-11-19

SRM488

| 01:12 | はてなブックマーク -  SRM488 - cafelier@SRM

SRM488 の成績・ソース (要ログイン) : AC/AC/- : また酷いコードを書いてしまった

500開く

  • 入力
    • J, B : string where 1≦|J|,|B|≦47
  • 出力
    • min(λa b. (-|a|,a) < (-|b|,b))[
      • { J[j1,j2)+B[b1,b2) | j1<j2≦j3<j4, b1<b2≦b3<b4, J[j1,j2)+B[b1,b2)==J[j3,j4)+B[b3,b4) }</li>
      • ∪ { J[j1,j2)+B[b3,b4) | j1<j2≦j3<j4, b1<b2≦b3<b4, J[j1,j2)+B[b3,b4)==J[j3,j4)+B[b1,b2) }</li>
    • ]
  • 『文字列Jから重ならない&空でない部分文字列を2つ切り出します。文字列Bからも同じように2つ切り出します。Jからとったのの後ろにBからとったの、と結合して2つ文字列が作れます。これが同じ文字列になるようにします。このやり方で一番長い文字列を作って下さい。』
    • 引き分けの場合は辞書順最小のものを。
    • 無い場合は空文字列を。

  • ※という問題文が最初から読めていれば苦労はなかった…
  • どう勘違いしたのかもう忘れてしまったのですけど、
    • J[j1,j2) + J[j3,j4) あるいは J[j3,j4) + J[j1,j2)、 と B[b1,b2) + B[b3,b4) あるいは B[b3,b4) + B[b1,b2) を等しくする
    • J[j1,j2)==B[b1,b2) と J[j3,j4)==B[b3,b4) になるように重ならないように切って結合
  • などを考えてました。サンプル合わないはずなのに…

  • 40分経過。
  • やっと理解した!

  • 焦らずに焦らずに。
  • いずれにせよ、ここまで迷ってたときと基本的な考え方は大差ない。
  • 文字列の長さがN≦47なので、N^4 は行ける。N^5 はダメ。
  • 単純に全探索しようとするとどうなるか。
  • まず J 側の切り出し方を考えよう
    • foreach(j1)
      • foreach(j2)
        • foreach(j3)
  • …で、foreach(j4) と思いきや、ちょっと待とう。
    • 「J[j1,j2) + 何か」と「J[j3,j4) + 何か」が等しくなるようにしないといけない。
    • ということは、J[j1,j2) が J[j3,j4) の prefix になっているか、その逆か、どちらか。
    • 一般性を失わず、 J[j3,j4) の方が prefix としてよい。

  • というわけで、j4 は j3+1 から始めて、J[j1,j2) と違わない限りできるだけ右に伸ばす。
    • 「できるだけ右に伸ば」しちゃっていいのは何故かというと
    • 伸ばさないと残りが foobar だったのが伸ばすと bar になったりするので、
    • そうすると B の側では foobarhoge と hoge みたいな組を作らなければいけない状態が barhoge と hoge を作ればいい
    • と条件が緩和されるので、伸ばしまくって良い
  • というわけで、できるだけj4を右に伸ばすループを入れて4重ループ
    • で J[j1,j2) と J[j3,j4) の候補を全部作る。
    • その差分(J[j1,j2) + diff == J[j3,j4) となるような diff)を求める
    • B の側からは、「diff+hoge」と「hoge」の形の文字列ペアをできるだけ長いのを切り出せばよい。
  • 4重ループのなかでそういうの求めるルーチンを呼び出す。

  • これ、O(N^4) に更になにか掛かることに…
  • …ならない! 「diff」はJの部分文字列なので、可能性は高々N^2通りしかない。
  • なので、これでメモ化すれば
    • O(N^4)*(B側の探索ルーチンの計算量)
  • ではなく
    • O(N^4) + O(N^2)*(B側の探索ルーチンの計算量)
  • くらいで済む!

  • というわけで O(N^2) で
    • 文字列 B のなかから、与えられた文字列diffに対して
      • diff+hogehoge、という2つの部分文字列をできるだけ長く切り出す。

  • これも同じように、適当に書いてメモ化で分離、でいけるんじゃ?
  • B の中の diff の出現を全部探す。
  • 普通に二重ループで書いて O(N^2) 時間で、O(N) 個の出現を見つけられる。
  • O(N) 個の候補それぞれについて、O(N) 時間で、hogeの候補を列挙。
    • 列挙というか、diffの終わりインデックスから右に伸ばすのばし方を全通り試すだけ。
  • すると状況として ... + diff + hoge + ... となるので、
  • あとは、 ... の部分からもう一個 hoge を探してくる。
  • hogeの選び方はN^2 通りで、... は「どっかから左全体」か「右全体」しかないので 2N 通り。
  • なので、この「hogeを探してくる」ルーチンの引数パターンは高々 O(N^3) 通り
  • ※本番中はなぜかO(N^2)通りと勘違いしていた…
  • これで
    • O(N^4) + O(N^2)*O(N^2) + O(N^3)*(hogeを探してくる計算量)
  • となった。
  • あとはhogeを探す部分は適当に書いても問題ないだろ
  • ※適当に書いたらO(N^2)です

  • えいやー
  • サンプル通った!
  • submit

250開く

  • 入力
    • 1≦n,m≦47
  • 出力
    • n人のヒマ人とm人のリア充さんがいます。
    • この中から2人ランダムに選びます。
    • 選ばれた人は全員ヒマ人になります。
    • これを繰り返して全員ヒマ人になってしまうまでの回数の期待値。

  • やるだけ
  • n人がヒマ人のとき
    • p0 = C(n,2) / C(n+m,2) の確率で、ヒマ人はn人のまま
    • p1 = 2nm / C(n+m,2) の確率で、ヒマ人はn+1人になる
    • p2 = C(m,2) / C(n+m,2) の確率で、ヒマ人はn+2人になる
  • ので、求める回数の期待値は
    • e[n] = 1 + (p0*e[n] + p1*e[n+1] + p2*e[n+2])

  • これだと両辺にe[n]がでてきてるので、式変形して、
    • e[n] = (1 + p1*e[n+1] + p2*e[n+2]) / (1-p0)

  • e[n+m] = 0
  • から始めて、DPでこの漸化式を解く。
  • できた。submit。

撃墜フェーズ

  • 落とす物がない…
  • 仕方なく自分の500を眺める。
    • あれ、この J[j1,j2) の prefix になるように J[j3,h4) を右に伸ばす部分、
    • 全然prefixになる制約かかってなくて、J[j3,h4) の方が長くなることが…
    • それどころか、これ普通にバッファオーバーランしてるんじゃ…
    • さらにさらに、これ時間計算量O(N^5)では…
    • ウボァー

感想

  • 500システムテスト通っちゃった…
  • 反省

SRM488 500

| 17:36 | はてなブックマーク -  SRM488 500 - cafelier@SRM

  • 本番中submitした500は
    • stringの実装によっては RE
      • str[str.size()]=='\0' を返してくる実装なら生き延びてしまう
    • それでもたぶんデータセットによっては WA
      • 意図せず s.substr(i, 巨大) になって意図せず s.substr(i, s.size()-i) にクリップされるので、それでまともに動く気が…
    • そもそも O(N^4) のつもりだったけど実は O(N^5) の最悪時間計算量なので TLE
  • という「何が出るかな?」状態だったはずなのに Accept されてしまいました…
  • 書き直し
  • 顧客が本番中に本当に書きたかったもの:
class TheBoringStoreDivOne { public:
   // entry point
   string J, B;
   string find(string J, string B) 
   {
      this->J=J; this->B=B; return solve();
   }

   // just for clarifying types
   typedef int           J_index, B_index;
   typedef pair<int,int> J_sub,   B_sub;
   string jsub(J_index js, J_index je) { return J.substr(js, je-js); }
   string bsub(B_index bs, B_index be) { return B.substr(bs, be-bs); }

   // update if better
   void update(string* a, const string& b)
   {
      if( a->size()<b.size() || (a->size()==b.size() && *a>b) )
         *a = b;
   }

   // O(|J|^4) in total
   string solve()
   {
      string result;
      for(J_index js=0;    js< J.size(); ++js)
      for(J_index je=js+1; je<=J.size(); ++je) // for each J[js, je)
      for(J_index ks=0;    ks< J.size(); ++ks) // try each J[ks, ks+k) which ...
      {
         // ... is a maximal nonempty prefix of J[js, je) not intersecting with it
         int k;
         for(k=0; js+k<je && ks+k<J.size() && (ks+k<js || je<=ks); ++k)
            if( J[js+k] != J[ks+k] )
               break;
         if( k==0 )
            continue;

         // we have J[js, js+k)+J[js+k, je) in J, so we want              m in B
         //         J[ks, ks+k)                              J[js+k,je) + m
         string m = findInB(J_sub(js+k,je));
         if( !m.empty() )
            update(&result, jsub(js,je)+m);
      }
      return result;
   }

   // O(|J|^2 |B|^2) in total
   map<J_sub, string> memo_fib;
   string findInB(J_sub key)
   {
      if( memo_fib.count(key) )
         return memo_fib[key];

      string result;
      for(string::iterator it=B.begin(); it!=B.end(); ++it) // for each B[ks,ke)==key
      {
         it = search(it, B.end(), J.begin()+key.first, J.begin()+key.second);
         if( it == B.end() )
            break;
         B_index ks = it - B.begin();
         B_index ke = ks + (key.second - key.first);

         // try all B[ks, ke)+B[ke, kee), and try to find another B[ke, kee) before ks or after kee
         for(B_index kee=ke+1; kee<=B.size(); ++kee)
            if( canFindBefore(ks, B_sub(ke,kee)) || canFindAfter(kee, B_sub(ke,kee)) )
               update(&result, bsub(ke,kee));
      }
      return memo_fib[key] = result;
   }

   // O(|B|^4) in total : for each substring m of B, the first and last occurence is memoized
   bool canFindBefore(B_index bi, B_sub m) { return firstOccurence(m)+(m.second-m.first) <= bi; }
   bool canFindAfter (B_index bi, B_sub m) { return bi <= lastOccurence(m)-(m.second-m.first); }

   map<B_sub, B_index> memo_fo;
   B_index firstOccurence(B_sub m)
   {
      if( memo_fo.count(m) )
         return memo_fo[m];
      return memo_fo[m] = search(B.begin(), B.end(), B.begin()+m.first, B.begin()+m.second)-B.begin();
   }

   map<B_sub, B_index> memo_lo;
   B_index lastOccurence(B_sub m)
   {
      if( memo_lo.count(m) )
         return memo_lo[m];
      int mrs = B.size() - m.second;
      int mre = B.size() - m.first;
      return memo_lo[m] = B.size() - (search(B.rbegin(), B.rend(), B.rbegin()+mrs, B.rbegin()+mre)-B.rbegin());
   }
};
  • にしても実装結構ヘビーですし
  • 想定解法はもっと綺麗なのがあるんだと思いますが。
トラックバック - http://topcoder.g.hatena.ne.jp/cafelier/20101119
 | 

presented by cafelier/k.inaba under CC0