2014年04月13日03時15分54秒に更新されたバージョンを表示しています．
最新のページはこちらをご覧ください．
$N$ 文字のアルファベット大文字からなる文字列 $S$ と，正整数 $L$ が与えられる．
以下の手順を何回でも繰り返すことができる．
最終的に得られる文字列として，辞書順最小のものを求める問題．
後ろの方から操作を適用していくと，できるかぎり，小さい文字を前に持ってくることができるので，後ろのほうから操作を順番に適応していく．
もしくは，最初の文字は絶対使わなくてはいけないが，後は，頑張れば持ってこれる，とかやっても良いと思う．
$N$ 文字のアルファベット大文字からなる文字列 $S$ と，正整数 $D$ が与えられる．
$S$ を並び替えるのだが，各文字は元々文字があった場所から，距離 $D$ 以下しか移動してはいけない．
（もともと $i$ 文字目の文字は，並び替えた後に $i-D$ 文字目から $i+D$ 文字目のどこかになければいけない）
並び替えた後の文字列として考えうるものの中で辞書順最小のものを求める問題．
Greedy．
$1$ 文字目から順番に決めていく．
$k$ 文字目を決めるとき，$k-D$ 文字目から $k+D$ 文字目の中で，まだ使っていない文字のうち最小のものを割り当てる．
複数あるなら，その中で，最も左の文字を割り当てる．
ただし，$k-D$ 文字目を割り当ててないなら，問題無用で割り当てる．
$N$ 個の電球と，$N$ 個のスイッチがある．
最初各電球が付いている（$\verb|Y|$）か付いていない（$\verb|N|$）かが与えられる．
スイッチ $k$ を押すと，以下の $4$ つのどれかが起こる．（何回押しても同じことが起こる）
電球をできるだけ消したいが，スイッチが最悪の場合，どうやっても最低でいくつかの電球が付いていることがある．
そのような電球の数を求める問題．
消せないパターンその1は，$\verb|YN|$ または $\verb|NY|$ で，それぞれのスイッチが，$2$ つの電球を同時に切り替える場合．
消せないパターンその2は，$\verb|YYY|$ で，真ん中のスイッチは $3$ つの電球全てと，左右のスイッチは真ん中の電球とも連動しているという場合も，1つは電球がついたままになる．
パターン2は $\verb|NNY|$ とかもそうだが，パターン1に帰着させた場合のほうが，最終的な付いている電球の数が多くなるので考えない．
どうように，橋のスイッチが範囲外の電球と連動している場合も，考えなくて良い．
上に挙げた2パターンが最大いくつ含まれるかをDPで数えた．Greedyに数えても良い．
Current time: 2024年05月03日19時16分12秒
Last modified: 2014年04月13日03時15分54秒 (by laycrs)
Tags: no_tags
トップページに戻る
Logged in as: unknown user (not login)