cafelier@SRM

SRM488

SRM | 01:12 |

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から重ならない＆空でない部分文字列を２つ切り出します。文字列Bからも同じように２つ切り出します。Jからとったのの後ろにBからとったの、と結合して２つ文字列が作れます。これが同じ文字列になるようにします。このやり方で一番長い文字列を作って下さい。』
  • 引き分けの場合は辞書順最小のものを。
  • 無い場合は空文字列を。

• ※という問題文が最初から読めていれば苦労はなかった…
• どう勘違いしたのかもう忘れてしまったのですけど、
  • 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を右に伸ばすループを入れて４重ループ
  • で J[j1,j2) と J[j3,j4) の候補を全部作る。
  • その差分（J[j1,j2) + diff == J[j3,j4) となるような diff）を求める
  • B の側からは、「diff+hoge」と「hoge」の形の文字列ペアをできるだけ長いのを切り出せばよい。
• ４重ループのなかでそういうの求めるルーチンを呼び出す。

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

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

• これも同じように、適当に書いてメモ化で分離、でいけるんじゃ？
• 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人のリア充さんがいます。
  • この中から２人ランダムに選びます。
  • 選ばれた人は全員ヒマ人になります。
  • これを繰り返して全員ヒマ人になってしまうまでの回数の期待値。

• やるだけ
• 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システムテスト通っちゃった…
• 反省