🤪

ABC229D "Longest X"をrubyで解く

2021/11/29に公開

お久しぶりです。あれだけイキリ散らかした末に二回も茶落ちした恥ずかしい男です。

今回解くのはこの問題。
https://atcoder.jp/contests/abc229/tasks/abc229_d

考察

「. を X に置き換える操作後に、X を最大で何個連続させることができますか?」とありますが、置き換える操作なんていちいちやっていたらTLEします。
これは「.を一定数以下しか含まない文字列のうち最も長いもの」と読み替える事ができます。
入力例1なら.は二個までなので「X.X.X」が答えになっているわけです。

ところで、この条件から「両端の一個外側がXではない」ことが導けます。
日本語にするとわかりにくいですが、「.が一個まで」の条件の時に「XX.XXX」から真ん中の「X.X」だけを抜き出すというパターンはありません。「X.X」の左の外側(元の文字列の1文字目)がXなのだから「XX.X」でいいはずだし、右の外側もXが連続しているので「XX.XXX」でOKのはずです。「.にぶつかるか、もしくは元の文字列の終わりに到達するまで広げる事ができる」のです。

ここから、入力例1は以下のように解ける事がわかります。

  1. 「XX...X.X.X.」の3文字目と4文字目の「..」に注目する。
  2. 左方向に広げられるのは二文字(三文字先で元文字列が終わっている)
  3. 右方向に広げられるのは0文字(いきなり.が来る)
  4. よって暫定最長は4文字。
  5. 1に戻る。ただし注目するのは4,5文字目の「..」
  6. 一番右の「.X.」まで考え、そこまでで最長の文字列が回答

以上のループを高速で回すことを考えます。

アルゴリズム

今回使うアルゴリズムは尺取法です。しかしこれは「一個入れて、一個出す」という手法で計算量を減らすアルゴリズムなので、プッシュ、シフトされる値の個数がわからない場合は苦手です。
じゃあ今回の場合使えないじゃん、と考えるのはXの個数を計算に入れているからです。実は今回、選択文字列に含まれる「.」の数は常に一定(「.」を含められる最大の個数まで含んだ方が有利に決まっている)です。
なので「.のインデックス」に注目すれば配列の長さは常に同じ。これで尺取法を使えます。
「.の個数制限」が例えば二個までの場合、「選択文字列の左の切れ目になる.のインデックス」「選択文字列内に含む二個のインデックス」「選択文字列の右の切れ目になる.のインデックス」
の4つの数字がわかれば「選択文字列内にこの二個のインデックスを含む場合、文字列の長さはいくらになるか」という値を計算できます。計算が終わってしまえば、左の切れ目を覚えておく必要はもうありません。残りの長さ3の配列を持って次のループに行きます。

ただし選択文字列の切れ目が「.」ではなく、元文字列の左端や右端の場合には特殊な処理が必要です。私は左端のさらに一個前に架空の「.」を置いて左端に対処、ループが終了してからもう一回長さ計算することで右端に対処しました。

提出コード

https://atcoder.jp/contests/abc229/submissions/27567233
コードの一番上にURL貼ってますが、今回はnogさんのコードを参考にしました。

別解

「.」の数の累積和配列を作って解くことも一応できます。ただし今回は+0か+1かしかないのでそんなことする必要ありません。
どうしても累積和でときたい人はこのコードを頑張って読んでください。
https://atcoder.jp/contests/abc229/submissions/27551415

Discussion