「AOJ2261 ［［iwi］］」の編集履歴（バックアップ）一覧はこちら

「AOJ2261 ［［iwi］］」(2013/10/20 (日) 12:25:34) の最新版変更点

追加された行は緑色になります。

削除された行は赤色になります。

*AOJ2261 ［［iwi］］
**サイト
[http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2261]
**解説
15文字以下の制限があるのでO(2^n)で全探索できるがDPも可能
ただし全探索の場合、iwiを軸として対称であることに注意する

iwiの左右の文字列をs, tとして、以下に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;
  }
}
||<
と書ける。またここで、上のビット集合と文字の存在の関係表において
>||
_ _ _ _ 0000
A _ _ _ 0001
_ B _ _ 0010
A B _ _ 0011
_ _ C _ 0100
・・・
||<
と充てるように考えれば、ssを作る部分は
>||
ss += s[i];
||<
と簡単に書ける

*AOJ2261 ［［iwi］］
**サイト
[http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2261]
**解説
15文字以下の制限があるのでO(2^n)で全探索できるがDPも可能
ただし全探索の場合、iwiを軸として対称であることに注意する

iwiの左右の文字列をs, tとして、以下に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;
  }
}
||<
と書ける。またここで、上のビット集合と文字の存在の関係表において
>||
_ _ _ _ 0000
A _ _ _ 0001
_ B _ _ 0010
A B _ _ 0011
_ _ C _ 0100
・・・
||<
と充てるように考えれば、ssを作る部分は
>||
ss += s[i];
||<
と簡単に書ける