yosupo https://blog.hatena.ne.jp/yosupo/ よすぽの日記 https://yosupo.hatenablog.com/ 嘘解法かも。 まず考察する。 とにかく2パターンの使い方ができるIが面倒。 仮に、IOIが爆破されたら(使用できるのがJOIだけだったら)ハジから貪欲にほいほいつくればいい。 なので、文字列中のIを何文字かJに変換し、貪欲に取るという事を考える。 Iの何文字かの選び方が2^n通りなので、O(n2^n)で解ける。 だが、すべてのIの選び方について考えなくても、左側から何文字かIを選ぶという選び方だけ考えれば良い。 最適解において、(3文字目としてつかうI)が(1文字目としてつかうI)より左側に来ることがないようにできるから。(そのようなIのペアがあったらswapすればいい) だからその何文字かを… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fyosupo.hatenablog.com%2Fentry%2F2015%2F01%2F31%2F041540" title="JOIOIの塔 - よすぽの日記" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2015-01-31 04:15:40 rich https://yosupo.hatenablog.com/entry/2015/01/31/041540 1.0 100%