zehnpaard https://blog.hatena.ne.jp/zehnpaard/ Arantium Maestum https://zehnpaard.hatenablog.com/ Python 蟻本 POJ/蟻本から： 3617 -- Best Cow Line ある文字列の左右どちらかの端から文字を1個ずつ取って、lexical orderが最小になる文字列を作成する、という問題。 最初は舐めていたのだが、bacbなどを正しく処理するためには先読みが必要になる。 しかしbbbbbacbbbbbやabcabcabcdecbacbacbaなど、ナイーブに先読みすると簡単にO(N^2)になってしまう。個別には対処できるのだが、すべてのケースを網羅してO(N^2)を避けるうまい書き方が思い浮かばず、思わず蟻本の回答を見たら何事もなくO(N^2)だった。でもN<2000だから1000msで4*10… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fzehnpaard.hatenablog.com%2Fentry%2F2018%2F03%2F11%2F104548" title="Best Cow Line問題 - Arantium Maestum" 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 2018-03-11 10:45:48 rich https://zehnpaard.hatenablog.com/entry/2018/03/11/104548 1.0 100%