ARMERIA

Rubyと競技プログラミングの話 AtCoderやCodeforcesの問題解説記事が多め。

AtCoder Beginner Contest 195 F - Coprime Present

お題箱より。

F - Coprime Present

解法

互いに素であるという条件を扱うときには、素因数だけに注目することで考慮すべき対象の個数を減らせる場合があります。2つの正整数が互いに素であることと共通の素因数を持たないことは同値です。

集合  S = \lbrace A, A+1, ..., B-1, B\rbrace とします。求めるべき答えは、 S の部分集合のうち、どの相異なる2つの要素も共通の素因数を持たないものの個数です。そのため考えるべき素因数は、 S の要素のうち2つ以上のものが持っている素因数だけで十分です。

 S の要素が連続する整数であり、その最大値と最小値の差が  72 以下と小さいことに注目します。 73 以上の素数  d について、 S d の倍数が2つ以上含まれることはありません。相異なる  d の倍数を2つ取ったとき、その差の絶対値は  d 以上であるからです。

つまり考えるべき素因数は  72 以下の素数だけで十分であり、これは実際に数えると  20 個です。ここまで個数を絞れれば解法の見通しが立ちます。

ここからの考察の進め方ですが、まず動的計画法を考えてみるのが堅実で見通しが立ちやすいでしょう。要素を1つずつ見ていって、部分集合に追加する・追加しないの遷移をするDPを考えます。

要素を部分集合に追加して良いかを判定するために、追加前の部分集合の情報として何を覚えておけば良いかを考えます。これは「 72 以下の素因数のうち、集合内の要素が既に持っているのはどれか」だけで十分なので、次のように状態を定義します。

  •  dp\lbrack i\rbrack\lbrack p\rbrack = 集合  S の前から  i 個の要素のうち  0 個以上のものを含む部分集合であって、次の条件を満たすものの個数。
    • どの相異なる2要素も共通の素因数を持たない。
    • 含んでいる要素が持っている  72 以下の素因数からなる集合が  p である。

これは  p 2^{20} 未満の非負整数として表現するビットDPとして実装できます。 dp\lbrack i\rbrack\lbrack p\rbrack からの遷移は次の2通りになります。

  • 次の要素を部分集合に追加しない:そのまま  dp\lbrack i+1\rbrack\lbrack p\rbrack に遷移する。
  • 次の要素を部分集合に追加する:次の要素は  A+i であり、これが持っている  72 以下の素因数からなる集合を  p_{i} と表記する。 p p_{i} が共通要素を持っていればこの遷移を無視し、持っていなければ  dp\lbrack i+1\rbrack\lbrack p\cup p_{i}\rbrack に遷移する。

ACコード

Submission #20980982 - Panasonic Programming Contest (AtCoder Beginner Contest 195)

考察の進め方について

この記事では考慮すべき素因数が少ないという点から考察を進めていきました。考慮すべき素因数が  20 個しかないと分かると、指数時間かかるアルゴリズムも視野に入るので考察の幅が広がります。

先にDPを考えるアプローチもできます。条件を満たす部分集合の個数を求める方法として、要素を1つずつ見ていって部分集合に追加する・追加しないの遷移をするDPは代表的でまず考えるべきものです。このDPで必要な情報を考えると、既に持っている素因数の集合が必要になり、その種類数を見積もろうという考察に進むことができます。

※「ビットDP」はDPで必要な情報を考えた結果出てくるものなので、最初からビットDPを思いつく必要はありません。考察のスタートはあくまで「要素を1つずつ見ていくDP」です

記事リクエストでもコンテスト後のTwitterでも、包除を考えて上手く行かなかったという声がありました。確かに、連続した整数・互いに素・数え上げという問題の断片的な特徴からは、通称「約数系包除」と呼ばれるアプローチを連想します。しかし実際に公式を適用してみると必要な値が求められずに行き詰まります。この問題のように部分集合の個数を数える問題では、約数系包除が上手くいきづらい印象です。

AtCoder Heuristic Contest 001 参加記

A - AtCoder Ad

得点率97.4%で130位でした。

f:id:betrue12:20210320121932p:plain

seed値0の入力に対する解のビジュアライザ出力です。

f:id:betrue12:20210320135516p:plain

考察

スコアの計算式を見ます。各企業が指定する1マス(以下、指定マスと呼びます)を含めないとその企業からの点は貰えないので、まずこれは含める必要があります。

企業ごとの得点は希望面積  r_{i} と実際の面積  s_{i} の単純な比ではなく、 s_{i} r_{i} に近づくにつれて伸びが緩やかになります。例えば面積を希望の50%確保すると75%の点が貰えるので、面積が足りなくても全ての企業からまんべんなく点を得たほうが効率が良さそうです。

そして面積が  r_{i} を超えてしまうと今度は得点が下がるので、面積が  r_{i} を超えることにほとんどメリットはないことが分かります。

最初は希望を叶えるのが難しい企業、つまり希望面積が大きく指定マスが密集地帯にあるような企業は諦めたほうがトータルで良いスコアになるのではと思うこともありました。しかし順位表の上位陣の得点率がコンテスト初期から98%以上と非常に高く、1つの企業の得点が0%になるだけでこの得点率はほぼ絶望的なので、その可能性はないと判断しました。

方針

焼きなまし法です。初期解は指定マスだけからなる  1\times 1 の正方形として、スコアは問題通りに計算しました。

近傍は3種類使い、それぞれ試す頻度を変えています。近傍1を1回実行する単位をイテレーション1回と呼ぶことにします。

近傍1

1つの企業ID  i と4方向のうちの1つをランダムに選び、長方形をその方向にマス1つ分伸ばします。盤外に出る、面積が  r_{i} を超える、他の長方形と被る場合はその近傍を諦めます。

面積を広げてスコアを高めるための基本となる近傍です。イテレーション1回につき1回近傍を取ります。

近傍2

1つの企業ID  i と4方向のうちの1つをランダムに選び、長方形をその方向にマス1つ分伸ばします。盤外に出る、面積が  r_{i} を超える場合はその近傍を諦めます。しかし他の長方形と被っている場合は、押し潰すようにそちらの長方形をマス1つ分縮めます。縮めることで指定マスが含まれなくなってしまう場合は諦めます。

スコアを悪化させる可能性がある近傍です。最初は近傍1に、20%の確率で長方形を縮める方向に近傍を取るという処理を入れていたのですが、縮めたマスを他の企業が使わないと結局スコアが増えないので、こちらの取り方に変更しました。

イテレーション10回につき1回近傍を取ります。

近傍3

1つの企業ID  i と、4方向の優先度を決める  \lbrace 上, 下, 左, 右\rbrace を並び替えた順列をランダムに選びます。その企業の長方形を指定マスのみの1マスに初期化し、優先度の高い方向から順番にその方向に伸ばせるだけ伸ばします。「伸ばせるだけ」とは、盤外に出ず、面積が  r_{i} を超えず、他の長方形と被らないように最大限伸ばすことを指します。

後半に動きづらくなった長方形を大きく動かす目的で導入しました。制限時間の半分が過ぎた以降、イテレーション1000回につき1回近傍を取ります。

高速化など

特にやっていません。スコア計算は近傍を取ったときに変更された企業のものだけを差分計算しました。他の長方形と被っているかの判定は自身以外の  n-1 個全てに対して愚直にやりました。

seed値0の入力( n=52)に対して、コードテストでイテレーション5400万回くらい回っていました。

振り返り

最初に貪欲解法を考えてみたものの良いものが思い浮かばず、 1\times 1 を初期解としてただランダムに伸ばすだけの焼きなまし解法からスタートして、近傍の取り方を考えていきました。

上位陣との得点の離れを見て、焼きなまし以外の解法を色々と考えたものの、シンプルな焼きなましを超えることができませんでした。お約束としてビームサーチも考えてみたけど、遷移先の候補をどう取れば良いか全く分からず撃沈しました。

近傍の取り方のアイデア、逆に言うと改善できそうな悪い所を見つけるためにビジュアライザ出力は非常に有用です。しかし今回は画像を眺めても、ここをこうすれば良くなるというアイデアをあまり思いつけなかったのが厳しい点でした。「この長方形、縦じゃなくて横に伸ばしたほうが面積大きくなるのに」と思うことはあり、その結果として近傍3が追加されました。近傍3を入れたのは最終日で、それでスコアが少し伸びて今の順位に落ち着きました。

変化が大きすぎると思うくらいの近傍も含めたほうが良い、という経験則はありましたが、単純に伸び縮みの長さを増やしたり乱数で決めたりするだけでは逆にスコアが悪くなってしまいました。もっと近傍の取り方そのものを工夫して多様な変化を作るべきだったと思います。

とはいえ最終日の頑張りで得点率が96.2%から97.4%くらいまで上がり、最終順位が想定で100くらい上がっているので、この粘りは今後も大事にしていきたいですね。

f:id:betrue12:20210320164913p:plain

最終提出コード

Submission #20927098 - AtCoder Heuristic Contest 001

AtCoder Regular Contest 047 C - N!÷K番目の単語

お題箱より。

C - N!÷K番目の単語

解法

※この解説の「何番目」という表記は全て1-indexedです。

一般に  n 1 以上  N! 以下の整数として、 N! 個の順列のうち辞書順で  n 番目にあるものを、前の要素から順番に求めていく方法を考えます。

  • 最初の要素は、 N! 個の順列を辞書順に並べて  N 等分したグループに分けたときに、対象の順列が何番目のグループにあるかで決まります。
  • 次の要素は、対象の順列が属していたグループをさらに  (N-1) 等分したグループに分けたときに、対象の順列が何番目のグループにあるかで決まります。

この手順を繰り返すことで対象の順列を求めることができます。 i 段階目の手順で属しているグループが  g_{i} 番目だとすると、対象の順列の  i 番目の要素は、それまで使われていない正の整数のうち小さい方から  g_{i} 番目のものです。

f:id:betrue12:20210221130509p:plain

今回求めたいのは  \frac{N!}{K} 番目の順列です。各段階で何番目のグループに属するかを求めるには割り算の商、そのグループ内で何番目の順列であるかを求めるには割り算の余りとして計算できますが、桁数が非常に大きいので直接計算することは困難です。

ここからの考え方の概要をまず示します。先ほどの図で示した1つ1つの段階において、全体のサイズを  1 とするような相対値として、対象の順列の位置を管理します。そして属しているグループが何番目かを求めて、そのグループのサイズがまた  1 となるように「拡大」して、次に属しているグループが何番目かを求めて…ということを繰り返していきます。

具体的な手順を説明します。まず  N! 個の順列全体のサイズを  1 と見なすと、最初の順列の位置は  \frac{1}{N!} 、最後の順列の位置は  \frac{N!}{N!} すなわち  1 です。そして対象の順列の位置は  \frac{1}{K} だと見なすことができます。

全体を  N 等分してサイズ  \frac{1}{N} のグループ  N 個に分けたときに、対象の順列が何番目のグループに属するかを考えます。これは \frac{1}{K} N 倍した値を整数に切り上げることで計算することができます。この値を  g_{1} とします。

次に、この  g_{1} 番目のグループのサイズが  1 になるように拡大し、そのグループ内における対象の順列の位置を再計算します。これは  \frac{1}{K} N 倍したまま、 (g_{1}-1) を引けば良いです。

この操作を繰り返していくことで、各段階で所属しているグループが何番目なのかを順に求めていくことができます。

 \frac{1}{K} を初期値とする対象の順列の位置は整数ではないですが、これを  K 倍した値は各段階において常に整数となります。 K 倍した値を持っておくことで誤差なく計算することができます。

ここまでの処理で、各段階で所属しているグループが何番目なのかを求めることができました。これを  g_{1}, g_{2}, ..., g_{N} とします。ここから実際の順列を求めるためには次の手順を踏む必要があります。

  1. まず、未使用の整数の集合  S = \lbrace 1, 2, ..., N\rbrace を用意する。
  2. 次の処理を  i=1, ..., N に対して順に行う。
    •  S の中で小さい方から  g_{i} 番目の要素を求め、 S から取り除く。それが対象の順列の  i 番目の要素である。

これはBITやセグメント木の上で二分探索を行うことで処理することができます。

ACコード

Submission #20364664 - AtCoder Regular Contest 047

PAST公式テキストを書きました

このたび、マイナビ出版から発行される「アルゴリズム実技検定 公式テキスト(エントリー~中級編)」の執筆をさせていただきました。kenkooooさんとの共著です。

アルゴリズム実技検定(通称PAST)のための学習参考書です。PASTに限らず、普段のコンテストのための学習教材としても使うことができます。

本記事では私個人の意見も交えつつ、執筆で重視したことや競技プログラミング(競プロ)を既にやっている人が気になっていそうな点などを書いていこうと思います。

本書の特徴

Amazonの商品ページなどにも本書の特徴が書かれていますが、特に次の2点が大きな長所だと考えています。

  • Pythonの文法解説から始まってエントリー→初級→中級と順番に解説していくので、プログラミング自体が初めてという人でも段階を踏んで学習できる
  • PASTとAtCoderの問題を合計で約50問解説し、その多くに図解が付いているので、実際の問題を用いて理解を深められる

競プロの学習に使える書籍は蟻本(通称)を筆頭にいくつか書かれていて、本書の執筆中にもけんちょん本(通称)という素晴らしい本が出版されました。それぞれの書籍では重視している内容や読者の想定レベルが少しずつ異なります。

本書はPAST公式テキストという位置付けなので、PASTの出題範囲や出題傾向に沿って構成を考えています。PASTで出題されにくい内容や、知らなくても問題が解けるような知識は思い切って省き、Pythonの文法解説や出題されやすいアルゴリズムの解説にページ数を使っています。そのため、

時間を掛けて手を動かせば、本書の内容だけでPAST中級が取得できる

とまで言える内容になっていると考えます。(もちろん複数の教材を併用したほうが学習効率が上がるのは言うまでもありませんが)

本書の掲載範囲

普段のコンテストでは出題範囲というものは存在しないも同然ですが、PASTには公式Webサイトに「出題範囲」という記載が存在します。本書の第4章がエントリー、第5章が初級、第6章が中級の出題範囲に対応しています。

本書は中級の出題範囲として記載されているアルゴリズムなどの解説に最も注力しています。Amazonの商品ページに掲載されているサンプルから第6章の目次を引用します。この第6章だけで約200ページ、本書の半分以上を占めています。

f:id:betrue12:20210220100933p:plain

この後に第7章が続きますが、新しい知識やアルゴリズムは登場しません。第6章で解説したアルゴリズムを複数組み合わせる問題や、遷移が少し複雑な動的計画法の問題などを扱います。

扱っている問題について

なるべくPASTの過去問を扱うようにしましたが、該当する問題がない場合はAtCoder Beginner Contest(ABC)や他のコンテストの問題も使っています。特に動的計画法の解説ではEducational DP Contestの問題がとても使いやすくて助かりました。

解説に適した問題がAtCoderにないアルゴリズムについては、アルゴリズムをそのまま適用する問題をいくつかAtCoder上に作成しました。発売までには公開される予定です。Aizu Online Judgeなどには既に適した問題が存在するのですが、書籍で扱う全ての問題をAtCoderでジャッジできるようにしたいという方針からこのような形になりました。

Pythonについて

言語がPythonであることは執筆のお話をいただいた時点で決まっていました。私個人としてもPythonを用いて良かったと考えています。Pythonの文法などを解説する第4章は私が担当しましたが、動かすために間接的に必要となるコードが少ないことは大きなメリットだと書きながら思いました。

私もkenkooooさんも競プロでPythonを使っているわけではないので、結果的に解答例は技巧的でなく平易な実装になったと思います。例えばリスト内包表記や引数の複雑なスライス記法は本編では用いていません。その代わり付録で、これらの応用的な記法や本編で扱っていないPythonの関数などを紹介しています。

PyPyについても少しだけ触れています。解説で扱う問題のいくつかは、素直な実装で通常のPython(CPython)で提出しても通らなかったので、PyPyで提出するように注意書きを付けています。

AtCoderの色について

本書を競プロの学習教材として使いたい人は、「この本の内容でAtCoderの何色まで到達できるのか」という疑問を持つと思います。

一概に言えるものではないので完全に私個人の意見ですが、およそ水色くらいだと思っています。中級レベルの後半で解説しているアルゴリズムを素直に適用できる問題が、最近のABCで出題されたとき、AtCoder ProblemsのDifficulty計算では水色に判定されることが多いからです。

しかし数学的知識を筆頭に、本書でカバーできない内容はABCのB~C問題でも出題されます。また最近は計算誤差の扱いをテーマとする問題がしばしば出題されています。これらは過去問で学習したり、コンテスト中に検索して知識を得ることに慣れたり(実はこっちのほうが重要かも)する必要があります。

アルゴリズムを素直に適用する問題は、知識が広く浸透していて検索にも引っかかりやすいため、コンテストでも正答率が高い傾向があります。そうすると同点の参加者が増え、正答時刻とペナルティの個数がパフォーマンス値に大きく影響します。

本書の内容を網羅して速度と正確さを常に発揮し続ければ青までは届くのではないかと思いますが、それよりは数学的知識やセグメント木などのデータ構造にも触れていったほうが青までの効率は良いと思います。

最後に

IT技術者のスキル評価において、アルゴリズムの知識とそれを実装に落とし込む能力が、これまで競プロのコミュニティで名前が挙がることが少なかった企業からも注目されてきています。そうすると必然的に、これらを学習する手段にも注目が集まります。

私が競プロを始めた3年前と比べると、学習教材は増えていますしこれからも増えていくでしょう。競プロから入った人もPASTから入った人も何を使えばいいのか迷うかもしれませんが、本書はそのどちらにもオススメできる内容となっています。色々見比べて、本書が合いそうだなと思ったら是非ご購入いただければと思います。

以上、真面目な(?)書籍紹介記事でした。私個人の体験談は発売後に別の記事で書くつもりなので、そちらもよろしければどうぞ。

AtCoder Regular Contest 112 B - -- - B

B - -- - B

解法

ある整数  x を作ることが可能か判定するときには、 x を最小のコストで作る操作列だけを考えれば十分です。作りたい整数を最小のコストで作る操作列が、何らかの限定的な特徴を持つことを見つけられると非常に見通しが良くなります。

その特徴を探すために、逆に無駄な部分を持つ操作列としてどのようなものがあるかを考えます。ここで言う無駄な部分とは、操作列の一部であって、そこをある規則で変形することでより小さいコストで同じ整数を作れるものを指します。

まず、 -1 倍する」という操作を連続して2回行うことは無駄で、その2回の操作を除いても同じ整数が得られます。

また、その時点での整数が  0 であるときに「 -1 倍する」という操作を行うことも無駄で、その操作を除いても同じ整数が得られます。

さらに、次の図で表される操作も無駄です。

f:id:betrue12:20210218222152p:plain

これは 1 を引く」→その時点での整数が  0 でないときに「 -1 倍する」→「 1 を引く」という一連の操作で、2回の「 1 を引く」という操作を除いても同じ整数が得られます。

作りたい整数を最小のコストで作る操作列は、これらの無駄な部分を持たないものに限られます。そのような操作列は必ず次の性質を満たします。

  • 操作列の先頭と末尾以外に「 -1 倍する」という操作が存在しない。

もしこの性質を満たさない場合、先に挙げたいずれかの無駄な部分が必ず1つ以上含まれることが場合分け等で証明できるからです。

このことから操作列としては「先頭で  -1 倍する/しない」「末尾で  -1 倍する/しない」の組み合わせ4通りだけを考えれば十分だということが分かります。

それぞれの場合について作ることが可能な整数を調べると、これは区間になります。例えば先頭で  -1 倍を行って末尾では行わない場合を考えます。その間に「 1 を引く」という操作は  0 回から  \lfloor\frac{C-1}{2}\rfloor 回までの好きな回数だけ行うことができるので、作ることが可能なのは閉区間  \lbrack -B-\lfloor\frac{C-1}{2}\rfloor, -B\rbrack に含まれる全ての整数です。

同様の考え方で、4通りの場合について作ることが可能な整数の区間を求めると次のようになります。

  •  \lbrack B-\lfloor\frac{C}{2}\rfloor, B\rbrack
  •  \lbrack B, B+\lfloor\frac{C-2}{2}\rfloor\rbrack
  •  \lbrack -B-\lfloor\frac{C-1}{2}\rfloor, -B\rbrack
  •  \lbrack -B, -B+\lfloor\frac{C-1}{2}\rfloor\rbrack

これらの和集合に含まれる整数の個数が答えになります。一般に複数の区間の和集合のサイズを求めるためには、順序付き集合で区間を管理するライブラリや、座標圧縮+imos法などを用いることができます。または4つの区間 B 周辺と  -B 周辺でそれぞれマージすると2つの区間になるので、それぞれの長さと重なりを考えることで直接計算することもできます。

ACコード

AtCoder Regular Contest 099 E - Independence

お題箱より。

E - Independence

解説

問題文をグラフ理論の言葉で解釈します。 N 個の頂点を2つの集合  X, Y に分け、それぞれの集合内では任意の2頂点間に辺が存在している(すなわち、クリークになっている)必要があります。 X, Y の頂点数をそれぞれ  x, y とすると、最小化したい値は  \frac{x(x-1)}{2} + \frac{y(y-1)}{2} です。そして  y=N-x なので、集合  X のサイズ  x だけを考慮すれば良いことが分かります。

クリークの問題では「補グラフ」、すなわち任意の2頂点間の辺の有無を反転させたグラフを考えるとうまくいくことがあります。補グラフを取るとクリークは独立集合に、すなわち「任意の2頂点間に辺が存在している」は「どの2頂点間にも辺が存在していない」となります。頂点が2つの集合  X, Y に分けられ、それぞれの集合内ではどの2頂点間にも辺が存在していない…これはまさに二部グラフです。

f:id:betrue12:20210202201636p:plain

与えられたグラフの補グラフを取り、これが二部グラフとなるように頂点を2つの独立集合  X, Y に分けることを考えます。このとき頂点の割り振り方は連結成分ごとに決めることができて、

  1. まずその連結成分が二部グラフになっているかを確認する。そうでなければ題意を満たすことは不可能。
  2. 連結な二部グラフであれば2つの独立集合への分け方は一意なので、そのうちどちらを  X に割り振るかを決める。

という手順を全ての連結成分について行うことで頂点を割り振ることができます。

冒頭で確認したように、答えを求めるには割り振った後の集合  X のサイズ  x としてどの値を実現できるかが分かれば十分です。各連結成分における2つの独立集合のサイズのうちどちらか一方を  x に加算していったときの総和としてあり得るものを列挙したいので、これは部分和問題と同様の動的計画法を用いて解くことができます。

ACコード

Submission #19879768 - AtCoder Regular Contest 099

AtCoder Beginner Contest 185 E - Sequence Matching

お題箱より。

E - Sequence Matching

解法

LCSとの類似性

2つの数列や文字列を操作して一致させる問題では、前から1文字ずつ扱いを決めていくという方針のDPがうまくいく場合があります。特に2つの列の長さを  N, M として  O(NM) が間に合う場合はなおさらです。

このような問題の代表例として最長共通部分列(LCS)を求める問題が挙げられます。LCSを求めるDPは、

 dp\lbrack i \rbrack\lbrack j\rbrack =  A の先頭  i 文字と列  B の先頭  j 文字を見終わったときの、そこまでの共通部分列の長さの最大値

と状態を定義し、前から見ていきながら

  1.  A の今見ている文字を削除する
  2.  B の今見ている文字を削除する
  3.  A の今見ている文字と列  B の今見ている文字が一致しているとき、その文字を共通部分列の次の文字として採用する

の3通りの遷移で文字の扱いを決めていくものです。

共通部分列というのは結局のところ2つの列それぞれについて好きな箇所の要素を好きなだけ削除し、一致させたときの列と思うことができるので、今回の問題の前半部分と同じです。

LCSそのものの解説や具体的な遷移についてはこちらの記事などを参考にしてください。

Educational DP Contest の F ~ J 問題の解説と類題集 - Qiita

今回の問題のケースを考える

今回の問題で最小化したい値  x+y をコストと呼ぶことにします。今回の問題を少し言い換えると、

  • 1文字につきコスト  1 A, B の文字を好きなだけ削除する。
  • その後  A, B で一致していない箇所1つにつき、 B の文字をコスト  1 で変更して一致させる。

という2段階の操作によって2つの列を一致させる問題だと考えることができます。しかしこれを2段階の操作と見なさず、2つのコストを同時に処理していったほうがDPの枠組みで考えやすくなります。

LCSを求めるDPと同じように考え、状態を以下のように定義します。

 dp\lbrack i \rbrack\lbrack j\rbrack =  A の先頭  i 文字と列  B の先頭  j 文字を見終わったときの、そこまでの列を一致させるためのコストの最小値

遷移を次のように考えることで2つのコストを同時に処理していくことができます。

  1.  A の今見ている文字を削除する。コストが  1 増える。
  2.  B の今見ている文字を削除する。コストが  1 増える。
  3.  A の今見ている文字と列  B の今見ている文字が一致しているとき、その文字を共通列の次の文字として採用する。
  4.  A の今見ている文字と列  B の今見ている文字が異なっているとき、 B の文字を変更して一致させた上で共通列の次の文字として採用する。コストが1増える。

つまりLCSを求めるDPに4番の遷移を追加すれば良いです。これで  O(NM) で解くことができます。

ACコード

実装では先ほどの遷移パターンのうち3番と4番を1行で記述しています。

Submission #18782223 - AtCoder Beginner Contest 185