drken1215 https://blog.hatena.ne.jp/drken1215/ けんちょんの競プロ精進記録 https://drken1215.hatenablog.com/ AtCoder AtCoder600点 ABC-F Dijkstra法 最小コスト 文字列 DP値:文字列 見積り大事 最適化の考察：探索候補を絞る 制約:複数系列の長さの合計が10^5以下 操作を好きな回数だけ行える 回文 応用的な探索 文字列のconcatを考える問題 prefixとsuffix 橙色diff N個の文字列の問題 最適化問題 こういう重たい実装を確実にこなせるように...なりたい！ 問題へのリンク 問題概要 個の文字列 が与えられる。これらを好きな順序で好きな回数だけ concat して回文を作りたい。ただし 番目の文字列を使用するコストは 1 回あたり である。 回文を作れるかどうかを判定し、作れるならば最小コストを求めよ。 制約 考えたこと 最初なんもわからんかった。ただちょっと気になっていたのは 回文の真ん中にある文字列は切断されているはず その両端で上手に半分全列挙的なことができないか...？ といったことを考えていた。ただ とかいう制約は半分全列挙するのは現実的じゃないし、そもそも同じ文字列を何度でも使っ… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fdrken1215.hatenablog.com%2Fentry%2F2020%2F08%2F16%2F032500" title="AtCoder ABC 175 F - Making Palindrome (橙色, 600 点) - けんちょんの競プロ精進記録" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://cdn.user.blog.st-hatena.com/default_entry_og_image/80936665/1516148889515660 Hatena Blog https://hatena.blog 2020-08-16 03:25:00 rich https://drken1215.hatenablog.com/entry/2020/08/16/032500 1.0 100%