2017/10/23の精進

AtCoder400点埋め

いまさら編集距離のDPを知った。1文字挿入・1文字削除・1文字書き換えの操作を何回すれば文字列sからtにできるかを「編集距離」と呼ぶ。

これはdp[i][j]=sの先頭i文字とtの先頭j文字の編集距離とすると、dp[i][j]=min(dp[i-1][j]+1,dp[i][j-1]+1,dp[i-1][j-1]+x)で求まる。(ただしxはsのi文字目とtのj文字目が等しいとき0、等しくないとき1)

原理はここに書いてある。追加・削除・書き換えを「sのまだ消費されていない文字」と「tのまだ生成されていない文字」を指すポインタを1進める操作だと思うと納得できる。

・みんなのプロコン本選 A YahooYahooYahoo

編集距離の問題。この問題では編集先tは固定された文字列ではなく(yahooを0回以上繰り返した文字列)となっている。

dp[i][j]=sの先頭i文字を(yahooを0回以上繰り返した文字列)+(yahooの先頭j文字)にするのに必要な最小の操作回数とすればできるが、(yahooの繰り返し)+(yahooの先頭4文字)にoを加えると(yahooの繰り返し)+(yahooの先頭0文字)になるというように循環することに注意。またjとしては0->1->2->3->4->0というように0を2回辿る必要がある。(挿入してsの先頭i文字を(yahooの繰り返し)+yahoにしたあとさらにoを加えて(yahooの繰り返し)にした方がいいこともあるので)

・天下一プログラマコンテスト2016予選B B 天下一魔力発電

対応のとれた文字列とは、左カッコの数を右カッコの数が上回る所がなく、全体で左カッコの数と右カッコの数が同じ文字列のことである。またカーソルを右に動かしてから左に戻すのは無駄なので、最適な操作はカーソルを右に動かす操作と文字を変更する操作からなる。あまっている左カッコの数とカーソルが指している文字が同じならば具体的にどのような文字列になっているかと関係なく同じ状態と見なせるので

dp[i][j][k]=Sの先頭i文字までで左カッコがj個あまっていてカーソルはk文字目を指しているときの操作回数の最小値

というDPができる。

・第3回ドワンゴからの挑戦状予選 C

待ち行列を無視してグループわけしても、グループで一番前に並んでいる人を代表として前に並んでいる代表からとっていけばいい。あとは上手くグループわけしてやる。

 

これでAtCoderの400点埋めは終了した。(自分にとって)簡単なものと難しいものの差が激しく、ぱっとわからないのもいくつかあったので頑張りたい。ABC/ARCの400点は典型という感じで簡単、AGCの400点はアドホックなかんじがあって苦手、企業コンはいろいろあるというイメージ。それでも基本的には多くの人が時間内にACしていてちゃんと出来るべき難易度帯ではある。