ABC329 勉強メモ

先日開催されたABC329の、C～E問題のふりかえりメモです。
まじめな解説は一切ありませんが、性質上問題のネタバレを含みますのでご了承ください。
使用言語はPython・提出はPyPy3です。

公式解説
---

https://atcoder.jp/contests/abc329/editorial?editorial

# C Count xxx

[問題文はこちら](https://atcoder.jp/contests/abc329/tasks/abc329_c)

### ランレングス圧縮
尺取法で$O(N)$ですが、尺取法は書くたびにバグります。[提出例](https://atcoder.jp/contests/abc329/submissions/47785313)

~~~python:RLE: S = 'aaabaa', N = 6
RLE = []; Lt = 0
for Rt in range(N-1):
  if S[Rt] != S[Rt+1]:
    RLE.append((S[Rt], Rt+1-Lt))
    Lt = Rt+1
RLE.append((S[N-1],N-Lt))

print(RLE)  #[('a', 3), ('b', 1), ('a', 2)]
~~~

<details><summary>旧版: 番兵を置く</summary>

[コンテスト中](https://atcoder.jp/contests/abc329/submissions/47684326)はSの末尾に番兵を置く実装をしていました。
この要領で、文字列に一時的に番兵を置く方法でもよさそうに思います。

~~~python:RLE: S = 'aaabaa', N = 6
S += '#'  #Sの末尾に番兵を置く  体感これもO(N)
RLE = []; Lt = 0
for Rt in range(N):
    if S[Rt] != S[Rt+1]:
        RLE.append((S[Rt], Rt+1-Lt))
        Lt = Rt+1
S = S.rstrip('#')  #番兵を取り除く O(N)

print(RLE)  #[('a', 3), ('b', 1), ('a', 2)]
~~~

ですが、str型でやると番兵除去に$O(N)$かかります。なんなら番兵を置く部分も$O(N)$かかってそうです。
高級すぎるのでlist型に限って使いましょう。(終)

</details>

対策ですが、hyouchunさんのABC解説記事に`itertools.groupby`でのランレングス圧縮法が紹介されています。
実装が簡便でバグらず、計算速度も尺取法と大差ない優れものです。おすすめです。

https://qiita.com/hyouchun/items/ac21f5c32bdfe86c385b

### Z-algorithm
最長共通接頭辞(LCP)の判定が$O(N)$でできます。すごいです。
アルゴリズムの詳細はPro_ktmrさんの解説記事をご覧ください。

https://qiita.com/Pro_ktmr/items/16904c9570aa0953bf05

応用として、`aaa ... a`とSの連続部分列のLCPを取ると、Sの連続`a`長が調べられます。
~~~python: 例: S = 'aaabaa' の 'a' の連続長を調べる
Z_algorithm('aaaaaa' + '#' + 'aaabaa')
#[13, 5, 4, 3, 2, 1, 0, 3, 2, 1, 0, 2, 1]
#'aaaaaa#' を無視すると [3, 2, 1, 0, 2, 1]
~~~
これを`bbb ... b`, `ccc ... c`, ... , `zzz ... z`で行いましょう。
計算量は$O(wN)$(w: wordsize = 26)と悪化しますが、実装が楽です。[提出例](https://atcoder.jp/contests/abc329/submissions/47769310)

<details><summary>英小文字の列挙法</summary>

キーボードをがーっとやればよいです。
~~~python: ｑあｗせｄｒｆｔｇｙふじこｌｐ
X = list('qawsedrftgyhujikolpzxcvbnm')  #5秒
Y = [chr(x + ord('a')) for x in range(26)]  #15秒
len(X)==len(Y)  #True たまにFalse
~~~
必要に応じてソートしましょう。(終)

</details>

# D Election Quick Report

[問題文はこちら](https://atcoder.jp/contests/abc329/tasks/abc329_d)
$O(N)$で解けますが、思いつけなかったので別解を考えます。

### SortedList
先日の言語アップデートで追加された、sortedcontainersを用いる解法です。
詳細はShirotsumeさんの解説記事をご覧ください。

https://qiita.com/Shirotsume/items/706742162db68c481c3c

本問を解くステップは3段階に大別できます。
1. 候補者ごとの現在の得票数は？
2. 現在の最高得票数は？
3. 最高得票数のうち、最も番号が小さい候補者は？

このうち3.の着想が難しいですが、SortedListがあれば強引に解決できます。
`SL[x] : 現在の得票数がxの候補者の一覧`
として、SortedListをM+1本生やしましょう。$M = 2 × 10^5$ のときは20万本も生えますが、耐えます。
計算量は$O(MlogN)$です。SortedSetでも解けますが、SortedListより遅いので注意してください。
提出例: [SortedList(640ms, 160MB)](https://atcoder.jp/contests/abc329/submissions/47787237) , [SortedSet(860ms, 290MB)](https://atcoder.jp/contests/abc329/submissions/47787288)
~~~python:SortedList20万本 主要部
SL = [SortedList() for _ in range(M+1)]  #M+1本建てる
for i in range(1,N+1): SL[0].add(i)  #初期化: 全員0票

for p in A:  #順に開票する
    before = Score[p]; Score[p] += 1  #得票数の更新
    SL[before].discard(p)
    SL[before+1].add(p)  #現在の得票数ごとの人を更新
    top=max(top,before+1)  #最高得点を更新
    print(SL[top][0])  #答えを出力
~~~

<details><summary>sortedcontainers 速度比較</summary>

SortedListよりもSortedSetのほうが遅いのおかしくないですか？
いくらか比較してみましょう。

#### ABC329D Election Quick Report
当然ですが、SortedListを20万本も生やす必要はありません。
たとえば`(-現在の得票数, 候補者)`を格納すればSortedList1本で解けます。
~~~python: SortedList1本 主要部
SL = SortedList([ (0,i) for i in range(1,N+1) ])  #(-得票数, 人)
~~~
･･･が、なんとどちらも400ms以上遅くなります。
そのぶん省メモリですが、実行時間が不安なときは20万本生やしましょう。
提出例: [SortedList(1100ms,130MB)](https://atcoder.jp/contests/abc329/submissions/47799355), [SortedSet(1350ms,170MB)](https://atcoder.jp/contests/abc329/submissions/47799378)

ほかの問題でも比較してみましたが、どうやらSortedSetは値の出し入れが遅いようです。
擁護すると値の検索 `X in SortedSet,SortedList` は3倍近くSortedSetのほうが高速ですが、特に理由がなければSortedList安定な気がします。(終)

<details><summary>ほかの問題 結果詳細</summary>

#### ARC155B Abs Abs Function
[問題文はこちら](https://atcoder.jp/contests/arc155/tasks/arc155_b)
数直線上の点の探索を行う問題です。
SortedSetでもSortedListでも解けますが、両者に速度差はみられませんでした。
提出例: [座圧セグ木(840ms)](https://atcoder.jp/contests/arc155/submissions/47799152) << [SortedList(1350ms)](https://atcoder.jp/contests/arc155/submissions/47798544) < [SortedSet(1380ms)](https://atcoder.jp/contests/arc155/submissions/47798402) <  [SortedList 重複を除去(1470ms)](https://atcoder.jp/contests/arc155/submissions/47798507)

#### ABC320E Somen Nagashi
[問題文はこちら](https://atcoder.jp/contests/abc320/tasks/abc320_e)
ダイクストラ法の問題です。ストレステストその1です。
SortedListは[機嫌次第でACします](https://atcoder.jp/contests/abc320/submissions/47783171)が、SortedSetでは険しいです。
提出例: [セグ木(380ms)](https://atcoder.jp/contests/abc320/submissions/47783430) << [heapq(1330ms)](https://atcoder.jp/contests/abc320/submissions/47783130) << [SortedList(2020ms)](https://atcoder.jp/contests/abc320/submissions/47802520) < [SortedSet(TLE)](https://atcoder.jp/contests/abc320/submissions/47802517)

#### ABC164E Two Currencies
[問題文はこちら](https://atcoder.jp/contests/abc164/tasks/abc164_e)
ダイクストラ法を工夫する問題です。ストレステストその2です。
やはりheapqは早いですね。ダイクストラ法はheapqでやりましょう。
提出例: [セグ木(350ms)](https://atcoder.jp/contests/abc164/submissions/47801736) << [heapq(560ms)](https://atcoder.jp/contests/abc164/submissions/47799874) << [SortedList(960ms)](https://atcoder.jp/contests/abc164/submissions/47799956) < [SortedSet(1010ms)](https://atcoder.jp/contests/abc164/submissions/47799948)

面白い問題がみつかれば追記します。(終)

</details>

</details>


### セグメント木上の二分探索
一点更新・区間最大値のセグメント木を使用します。[PAST上級本](https://book.mynavi.jp/ec/products/detail/id=135840)の6章に載っています。
`SegTree[i]: 候補者iの現在の得票数`
と定義すると、得票数の更新と最大得票数の取得は簡単に行えます。
3.の「最高得票者のうち、最小の得票者の取得」が難しいですが、これはセグメント木上の二分探索を行えば$(logN$)で可能です。
総計算量は$O(MlogN)$です。[提出例](https://atcoder.jp/contests/abc329/submissions/47785976)
<details><summary>実装方針</summary>

node値を読み取って、どちらの葉に降りれば条件を満たすか考えながら降りるイメージで実装してみました。
なお、この探索方針だと$N=1$がコーナーケースになります。セグメント木の初期サイズを1から2に上げて対策しましょう。

~~~python: セグ木の二分探索 主要部
class SegmentTree:
    def bisect(self, X):  #[0:Lt+1)の作用値がX以上となる最小のLt
        now = 1; cnt = self._identity_e  #now: 現在のnode位置
        while now < self._size:
            Lt,Rt = self._node[now<<1|0], self._node[now<<1|1]
            if self._combine_f(cnt,Lt) >= X:     now = now<<1|0
            else: cnt = self._combine_f(cnt,Lt); now = now<<1|1
        return now - self._size
~~~

なお、セグ木の二分探索はライブラリ化したばかりでAC確認数が不十分です。
バグが見つかり次第修正します。(終)

</details>

# E Stamp
[問題文はこちら](https://atcoder.jp/contests/abc329/tasks/abc329_e)
公式解説の通り、操作を逆から見てスタンプを剥がす方針が最も楽です。
しかし思いつけなかったので、問題設定通りにスタンプを押す解法を考えます。

注意点は3つです。たぶん図にしたほうがわかりやすいです。
1. スタンプの裏押しが可能
1. スタンプの上書きが可能
1. 裏押ししたスタンプの端を上書き可能
~~~:スタンプの押し方いろいろ  T: 'ABCD'
1. スタンプの裏押し
__ABCD   あらかじめ右側に打ったスタンプにかぶせることで
ABCDCD   接尾辞(CD)だけが飛び出る

2. スタンプの上書き
ABCD__   あらかじめ左側に打ったスタンプにかぶせることで
ABABCD   接頭辞(AB)だけが飛び出る

3. 組み合わせ
___ABCD___   1.と2.の組み合わせ。
ABCDBCD___   接尾辞(BCD)が飛び出る状態にしてから
ABCDBCABCD   スタンプをかぶせると、接尾辞がBCに削れる
~~~

### 動的計画法
$O(NM^2)$や$O(NM)$や$O(NM!)$で解けます。1番目か2番目で解きましょう。

__$O(NM^2)$解__
`DP[i][j]: S[:i]まで文字を合致させて、S[i]をT[j]の部分で塗れたらTrue`
と定義します。`DP[i][j]`がTrueであるには、`S[i]==T[j]`であることが必須です。
他の遷移条件を、スタンプの挙動ごとに考えましょう。
~~~: スタンプの裏押し S : 'ABCDCD', T : 'ABCD'
__ABCD   S[2:6]を起点にスタンプを打ってから
ABCDCD   S[0:4]にスタンプを打つことで、接尾辞だけが飛び出ます。

T\S 0 1 2 3 4 5   たとえばS[2]を左端にしてスタンプを裏押しした場合、
0   A _ x _ _ _   S[2:4]はS[0:4]に打ったスタンプで隠されており、
1   _ B _ x _ _   S[4:6]でスタンプが表に出てくればよいです。
2   _ _ C _ C _   DP[2][2] == DP[3][3] == True なら、
3   _ _ _ D _ D   DP[4][2]以降を押せるかの判定に移れます。
~~~
~~~: スタンプの上書き S : 'ABABCD', T : 'ABCD'
T\S 0 1 2 3 4 5   S[i]のどれかがTrueなら、
0   A _ A _ _ _   S[i+1]を起点にスタンプを打ってよいです。
1   _ B _ B _ _
2   _ _ _ _ C _
3   _ _ _ _ _ D 
~~~
まとめましょう。
1. S[i]を起点に、スタンプを裏押しする場合
kをS[i]から新しく打ち出したスタンプの位置とします。
`if j+k <M: DP[i+k][j+k]がTrueなら、スタンプを隠せるので続行`
`if j+k>=M: DP[i+k][k]を判定`
1. S[i+1]から新しくスタンプを打つ場合
`S[i]のどれかがTrueなら、DP[i+1][0]を判定`

最終的にDP[N-1][M-1]がTrueにできるかを見ればよいです。
計算量は1. の部分が重く、$O(NM^2)$となります。[提出例](https://atcoder.jp/contests/abc329/submissions/47753465)


__$O(NM)$解__
$O(NM^2)$解の重い部分を高速化します。
スタンプの裏打ちを行い、Tの接尾辞がはみ出した状態の処理に$O(M^2)$かかっています。
少し考えると、Tの接尾辞がはみ出してよい条件は直前にTの末尾がある場面に限ると気づきます。
~~~: 接尾辞の連続の例　  S : 'ABCDCDBCD', T : 'ABCD'
ABCD_____   S[0:4]に'ABCD'をあてはめる。　S[3]==T[3]となる。
ABCDCD___   S[4:6]に'CD'と接尾辞をつなぎ、S[5]==T[3]となる。
ABCDCDBCD   S[6:9]に'BCD'と接尾辞をつなぎ完成。
~~~
なので T[M-1]に到達したもののみ、接尾辞をつなげられないか考えることにしましょう。
~~~: スタンプの裏押し S : 'ABCDCD', T : 'ABCD'
T\S 0 1 2 3 4 5   DP[3][3]から接尾辞をつなげることを考えます。
0   A _ _ _ _ _   DP[4][j]の遷移先を考えると、S[4]==T[2]=='C'
1   _ B _ _ _ _   なので、DP[4][2]=True と遷移できます。
2   _ _ C _ C _
3   _ _ _ D _ _   ← DP[5][3] はDP[4][2]を考えるタイミングで埋めます。
~~~
これにより、DP[i+1]以降の部分の状態を事前に決める必要もなくなります。
`DP[i][j] → DP[i+1][j+1]` の遷移がM-1回
`DP[i][M-1] → DP[i+1][k]` の遷移がM回
`DP[i] → DP[i+1][0]` の遷移が1回
なので、各iごとに遷移が$O(M)$、合計で$O(NM)$となります。[提出例](https://atcoder.jp/contests/abc329/submissions/47754605)

__$O(NM!)$解__
破滅する方針なのでやめましょう。[提出例(960ms)](https://atcoder.jp/contests/abc329/submissions/47751847)
<details><summary>実装の要点</summary>

M-1文字前から0文字前のスタンプの打ち順を定めれば、S[i]が一意に定まる性質を利用します。
`DP[i][X]: i文字目を塗る直前であって、直前1個～M-1個の塗り順をXにできるか`
というDPを定義します。

DPを計算する前に、各状態ごとに遷移先を前計算しましょう。
まず直前M-1個～直前1個の塗り順としてvalidなものを列挙し、連想配列で管理します。
遷移は、i個目の塗り順を全探索して(S[i]がどの文字になるか、この場合の塗り順はどうなるか)を遷移情報として持てば良いです。
i文字目の塗り順全探索は0.5刻みに行うとうまくいきます。
~~~: 遷移
0は塗らない、1以上は数字の昇順にスタンプを打つものとします。
(1,2,0) だと 3文字前にスタンプしてから、2文字前にスタンプします。

S[0]のスタンプ順を全探索し、座標圧縮して遷移先とします。
(1,2,0),0   : スタンプを打たない  → (S[i]=T[2], 遷移先=(1,0,0))
(1,2,0),0.5 : 1番目にスタンプする → (S[i]=T[2], 遷移先=(2,0,1))
(1,2,0),1.5 : 2番目にスタンプする → (S[i]=T[2], 遷移先=(2,0,1))
(1,2,0),2.5 : 3番目にスタンプする → (S[i]=T[0], 遷移先=(1,0,2))
~~~
実装諸注意:
1. S[i]のスタンプ番号は小数点を使いましょう。
整数だと同率タイになってしまい破滅します。
1. 遷移決定後の座標圧縮で0を潰さないようにしましょう。
たとえば塗り順が`(3,2,1),2.5`のとき、`(S[i]=T[0], 遷移先=(1,0,2))` のように座標圧縮すると、塗っていた場所が塗らない場所に変わってしまいWAします。
正しく`(S[i]=T[0], 遷移先=(2,1,3))`となるよう座標圧縮しましょう。
1. 最後のS[N-M:]の部分はスタンプが打てません(はみ出ます)。
なので遷移先の末尾が0(スタンプしない)しか遷移条件を満たしません。
うまく場合分けしましょう。

全ステップも罠だらけなうえ、実装も計算量も重く大変です。
コンテスト中の私はこれで破滅しました。破滅方針は避けましょう。(終)
</details>

### Z-algorithm
計算量のオーダーが落ちるようですが、原理や実装があまり理解できていないので原理の解説はしません。
ACコードだけ張っておきます。[提出例](https://atcoder.jp/contests/abc329/submissions/47768714)
<details><summary>実装の要点</summary>

実装方針のメモです。T = `ABCD` として説明を行います。

1. `AB ABC ABCD` のような、接頭辞が連続してTで終わる列を取りのぞく。
1. `ABCD CD BCD` のような、Tで始まり接尾辞が連続する列を取りのぞく。
1. `ABCD CD` + `BC` + `AB ABCD`の`BC`はスタンプの押し方が存在する。
「除去した部分」 +「Tの連続部分列」+「除去した部分」の形に限りスタンプが打てるので、残った部分がこの形になっているか確認する。

1.と2.はZ-algorithmと尺取法、3.は尺取法で消し残った部分を探してZ-algorithmを行います。
このうち、3.がコーナーケースになりやすいです。
たとえば S = `ABCB`,  T = `ABC` でTrueと誤判定してしまいがちなので注意しましょう。(終)

</details>

おわりに
---

おわりです。
たくさんかくとにぎやかになっていいなとおもいました。