2019-01-10 AtCoder Educational DP Contest / DP まとめコンテスト F - LCS atcoder F 動的計画法 dp_f 蟻本の最長共通部分列問題の類題? 最後に共通部分文字列を出力する必要があり、それに手間取った。 共通文字が存在するときはその要素の右下が1大きくなるので、逆に辿れば共通部分文字列の反転を得られる。それを反転して出力すればいい。 計算量がO(|s||t)で 9 * 106 のため、pythonでは制限時間内に間に合わせるのが難しかったので、c++で提出した。 一応pythonコード c++コード