cf_2015_morning_easy_d
考えたこと
文字列を二回の部分文字列の繰り返しにしたい問題
二回目の開始点がどこかわからない
食い違った時にどちらを読み飛ばすかで2通りあるよな
うーむ
理論上は二回目の開始点が2文字目からにもなり得るが、その時には最良でもコストがN-2なのだな
二回目の開始点n, 注目点i, jの三つ組を考える
(n, 0, n)からスタートして(n, n, N)にたどり着けばゴール
Si=Sjならゼロコストでi,jをインクリメントできる
違うならコスト1で片方をインクリメントできる
Nが100なので頂点数は5×10^5程度。余裕。
公式解説なし
Related Pages
- →最適輸送×微分可能×勾配法×正則化項×シンクホーンアルゴリズム×自動微分×ランキング問題×ランキング学習×クロスエントロピー×passive-aggressive×ランキング問題は一次元の最適輸送問題×ランキング×ソート×ビームサーチ×線形計画問題×ブレグマン法×最短経路問題×adam×end-to-end最適化×joisino→
- →chokudai×貪欲法の証明パターン×選択肢が少ない方から貪欲×マトロイド×クラスカル法×区間スケジューリング×交換しても悪化しない×アルゴリズムとデータ構造×区間はマトロイドではない×abc076b×現在が良いほど未来も良い×poj3617×poj3069×ダイクストラ法×agc009a×arc111×abc187×arc110c×一回り小さい同じ形の問題×agc049b×abc103d×abc023d×和の比率の最大化×単位時間ジョブスケジューリング問題×乱択＋貪欲×abc171_f×離散凸性→
- →past5×past202012×アルゴリズム実技検定×past過去問練習202012×past5e×past5f×past5g×past5h×PAST5I×past5j×past5k×past5l×past5m×past5n×past5o×番兵×地図読み込み時に番兵をつける×ゴールをスタートにする×ゴールを一つにする×ダイクストラ法×bit_dp×期待値dp×二次元の片方を時間軸にする×past2n→
"Engineer's way of creating knowledge" the English version of my book is now available on [Engineer's way of creating knowledge]
(C)NISHIO Hirokazu / Converted from [Scrapbox] at [Edit]