2022-04-02 PAST #9 H - 最長非共通部分列 を解いた
PAST #9: 第九回 アルゴリズム実技検定 H - 最長非共通部分列 を解いた。
問題: https://atcoder.jp/contests/past202112-open/tasks/past202112_h
最長共通部分列の解法から考えておそらく DP だろうと予想した。 S の先頭 n 文字と T の先頭 m 文字を使ってできる最長非共通部分列を考える。 n = |S| かつ m = |T| まで進めたときの最長非共通部分列の長さが答え。その一つ前の状態から遷移できそう。 DP になりそうと考えた。
S の 1 文字目を使うとする。 T の m 文字目を使う場合は m - 1 文字目までの最長非共通部分列の長さ +1 になる。 S の各文字について T の各文字を走査すれば良さそう。だいたい O(|S||T|) になりそう。そしてこれなら間に合いそう。
「 m - 1 文字目までの最長非共通部分列の長さ (の最大値) 」を高速に得られるか考えたのだけど数値は小さいのでセグ木でいいやと考えた (後で考えるとおかしい) 。
|S||T| に log がついているはずだけどなんとか間に合った。たぶん間違っている。
提出: https://atcoder.jp/contests/past202112-open/submissions/30615983 解説: https://atcoder.jp/contests/past202112-open/editorial/3129
解説を読んだ。 m - 1 文字目までの最長非共通部分列の長さの最大値は一つ前 ( n - 1 や m - 1 ) の要素を参照すればいいだけだった。……というかそうしないとほとんど DP になっていない。
花見に行った。妻の実家の繋がりで。
ABC246 に参加した。 A, B, C, E を解いた。 C までをつまらないミスで WA だらけにしてしまい E がギリギリで解けたので良かったもののまたレートを下げるところだった。
まだ緑だけど次回もうまくいけば水色に戻せる。
https://atcoder.jp/users/bouzuya/history/share/abc246?lang=ja
今日のコミット。