「AOJ2261 ［［iwi］］」の編集履歴（バックアップ）一覧に戻る

AOJ2261 ［［iwi］］ - (2013/10/20 (日) 12:17:30) の編集履歴(バックアップ)

---

AOJ2261 ［［iwi］］

サイト

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2261

解説

15文字以下の制限があるのでO(2^n)で全探索できるがDPも可能

ただし全探索の場合、iwiを軸として対称であることに注意する

iwiの左右の文字列をs, tとして、以下に2つの解法を述べる

1. ビットを用いて全探索
2. s と rev(t)に対し、最長共通部分列問題を適用する

2つ目の解法の説明はする内容がない上、UVa11151 Longest Palindromeとほぼ同じであるので省略

ここでは1つ目の解法のみについて考える

解法

s, tのそれぞれの文字列に対し、1文字ずつ「削る」「削らない」の2択でビットを使いfor文を回し文字列の集合をつくる

for( int S=0; S < (1<<s.size()); S++ ) {
  for( int T=0; T< (1<<t.size()); T++ ) {
    ss = sからビットの集合Sを用いて文字列を作成
    tt = tからビットの集合Tを用いて文字列を作成
  }
}

上のコードは例えば文字列ABCDに対し、

A B C D ( _ を空文字列として表記)
------------------------
_ _ _ _ 0000 (全て削る)
_ _ _ D 0001
_ _ C _ 0010
_ _ C D 0011
_ B _ _ 0100
_ B _ D 0101
_ B C D 0111
A _ _ _ 1000
A _ _ D 1001
A _ C _ 1010
A _ C D 1011
A B _ _ 1100
A B _ D 1101
A B C _ 1110
A B C D 1111 (1つも削らない)

となるような文字列を作るものである。上の ビット集合S から各の文字 A, B, C, D の存在を確認するにはどうすればよいだろうか。これは例えば以下のように、存在の有無を調べたい文字に当たるビットを最下位に落として1と論理積を見れば良い。s = "ABCD"として、

for( int i=0; i< s.size(); i++) {
  if( S >> i & 1 ) {
    // 存在
    ss = s[str.size()-1-i] + ss;
  }
}

上のビット集合と文字列の関係を逆にして（つまり 0001 は A _ _ _ を意味する）考えれば、ssを作る部分は

ss += s[i];

とも書ける