SRM参加記録など雑記です。社会人になってから競技プログラミングを始めました。どこまで行けるか分かりませんが合間を見つけてアルゴリズムの勉強をしています。Statementir5さんの記事を見て、共通パートと残余パートに分ければ解ける気がしたので解いてみた。大まかな方針としては、共通パートの探索を先にして記憶しておき、残余パートの探索時に使用可能な共通パートの最長のものを持ってくるという方法。共通パート1の探索は、Jの中でインデックスk,lの全ての組み合わせに対し、k,lで終わる共通部分文字列の最大長を記憶する。Bは逆にk,lで始まる共通部分文字列の最大長を記憶する。残余パートはJとBの共通部分文字列s全てに対し、Jはsの前にくっつけられる最長の共通パート1を探索、Bはsの後ろにくっつけられる最長の共通パート2を探索して、両方の共通パート長が0より大きい場合のみ有効な解とする。計算量はO(n^4)です。感想としては添え字周りの実装が大変。本番中に思いついても解けなかった可能性大です。システムテストは通ります。→500へ500は色々考えたが分からない。手計算もまた間違えてまた一杯時間浪費したし、だめだめだ・・ソースコード修正しました。システムテスト通ります。OpenTipsDiv1SRM455SRM456SRM457SRM466SRM467SRM468SRM469SRM470SRM471SRM473SRM474SRM475SRM476SRM477SRM478SRM479SRM480SRM481SRM482SRM483SRM484SRM485SRM486SRM487SRM488SRM489SRM490SRM491SRM492SRM493SRM494SRM495SRM496SRM497SRM498SRM499SRM500SRM502SRM503SRM505SRM504.5SRM506SRM507SRM508SRM510SRM511SRM512SRM513SRM514SRM515SRM516SRM517SRM518SRM519SRM520SRM521SRM522SRM523SRM524SRM525SRM526SRM527SRM526.5SRM528SRM529SRM530SRM531SRM532SRM533SRM534SRM535SRM536SRM537SRM538SRM540SRM541SRM543カウンター357949リンク集SigmarのProfile。