先日開催されたABC329の、C～E問題のふりかえりメモです。
まじめな解説は一切ありませんが、性質上問題のネタバレを含みますのでご了承ください。
使用言語はPython・提出はPyPy3です。
公式解説
C Count xxx
ランレングス圧縮
尺取法で$O(N)$ですが、尺取法は書くたびにバグります。提出例
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)]
旧版: 番兵を置く
コンテスト中はSの末尾に番兵を置く実装をしていました。
この要領で、文字列に一時的に番兵を置く方法でもよさそうに思います。
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型に限って使いましょう。(終)
対策ですが、hyouchunさんのABC解説記事にitertools.groupbyでのランレングス圧縮法が紹介されています。
実装が簡便でバグらず、計算速度も尺取法と大差ない優れものです。おすすめです。
Z-algorithm
最長共通接頭辞(LCP)の判定が$O(N)$でできます。すごいです。
アルゴリズムの詳細はPro_ktmrさんの解説記事をご覧ください。
応用として、aaa ... aとSの連続部分列のLCPを取ると、Sの連続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)と悪化しますが、実装が楽です。提出例
英小文字の列挙法
キーボードをがーっとやればよいです。
X = list('qawsedrftgyhujikolpzxcvbnm') #5秒
Y = [chr(x + ord('a')) for x in range(26)] #15秒
len(X)==len(Y) #True たまにFalse
必要に応じてソートしましょう。(終)
D Election Quick Report
問題文はこちら
$O(N)$で解けますが、思いつけなかったので別解を考えます。
SortedList
先日の言語アップデートで追加された、sortedcontainersを用いる解法です。
詳細はShirotsumeさんの解説記事をご覧ください。
本問を解くステップは3段階に大別できます。
- 候補者ごとの現在の得票数は？
- 現在の最高得票数は？
- 最高得票数のうち、最も番号が小さい候補者は？
このうち3.の着想が難しいですが、SortedListがあれば強引に解決できます。
SL[x] : 現在の得票数がxの候補者の一覧
として、SortedListをM+1本生やしましょう。$M = 2 × 10^5$ のときは20万本も生えますが、耐えます。
計算量は$O(MlogN)$です。SortedSetでも解けますが、SortedListより遅いので注意してください。
提出例: SortedList(640ms, 160MB) , SortedSet(860ms, 290MB)
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]) #答えを出力
sortedcontainers 速度比較
SortedListよりもSortedSetのほうが遅いのおかしくないですか？
いくらか比較してみましょう。
ABC329D Election Quick Report
当然ですが、SortedListを20万本も生やす必要はありません。
たとえば(-現在の得票数, 候補者)を格納すればSortedList1本で解けます。
SL = SortedList([ (0,i) for i in range(1,N+1) ]) #(-得票数, 人)
･･･が、なんとどちらも400ms以上遅くなります。
そのぶん省メモリですが、実行時間が不安なときは20万本生やしましょう。
提出例: SortedList(1100ms,130MB), SortedSet(1350ms,170MB)
ほかの問題でも比較してみましたが、どうやらSortedSetは値の出し入れが遅いようです。
擁護すると値の検索 X in SortedSet,SortedList は3倍近くSortedSetのほうが高速ですが、特に理由がなければSortedList安定な気がします。(終)
ほかの問題 結果詳細
ARC155B Abs Abs Function
問題文はこちら
数直線上の点の探索を行う問題です。
SortedSetでもSortedListでも解けますが、両者に速度差はみられませんでした。
提出例: 座圧セグ木(840ms) << SortedList(1350ms) < SortedSet(1380ms) < SortedList 重複を除去(1470ms)
ABC320E Somen Nagashi
問題文はこちら
ダイクストラ法の問題です。ストレステストその1です。
SortedListは機嫌次第でACしますが、SortedSetでは険しいです。
提出例: セグ木(380ms) << heapq(1330ms) << SortedList(2020ms) < SortedSet(TLE)
ABC164E Two Currencies
問題文はこちら
ダイクストラ法を工夫する問題です。ストレステストその2です。
やはりheapqは早いですね。ダイクストラ法はheapqでやりましょう。
提出例: セグ木(350ms) << heapq(560ms) << SortedList(960ms) < SortedSet(1010ms)
面白い問題がみつかれば追記します。(終)
セグメント木上の二分探索
一点更新・区間最大値のセグメント木を使用します。PAST上級本の6章に載っています。
SegTree[i]: 候補者iの現在の得票数
と定義すると、得票数の更新と最大得票数の取得は簡単に行えます。
3.の「最高得票者のうち、最小の得票者の取得」が難しいですが、これはセグメント木上の二分探索を行えば$(logN$)で可能です。
総計算量は$O(MlogN)$です。提出例
実装方針
node値を読み取って、どちらの葉に降りれば条件を満たすか考えながら降りるイメージで実装してみました。
なお、この探索方針だと$N=1$がコーナーケースになります。セグメント木の初期サイズを1から2に上げて対策しましょう。
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確認数が不十分です。
バグが見つかり次第修正します。(終)
E Stamp
問題文はこちら
公式解説の通り、操作を逆から見てスタンプを剥がす方針が最も楽です。
しかし思いつけなかったので、問題設定通りにスタンプを押す解法を考えます。
注意点は3つです。たぶん図にしたほうがわかりやすいです。
- スタンプの裏押しが可能
- スタンプの上書きが可能
- 裏押ししたスタンプの端を上書き可能
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]であることが必須です。
他の遷移条件を、スタンプの挙動ごとに考えましょう。
__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]以降を押せるかの判定に移れます。
T\S 0 1 2 3 4 5 S[i]のどれかがTrueなら、
0 A _ A _ _ _ S[i+1]を起点にスタンプを打ってよいです。
1 _ B _ B _ _
2 _ _ _ _ C _
3 _ _ _ _ _ D
まとめましょう。
- S[i]を起点に、スタンプを裏押しする場合
kをS[i]から新しく打ち出したスタンプの位置とします。
if j+k <M: DP[i+k][j+k]がTrueなら、スタンプを隠せるので続行
if j+k>=M: DP[i+k][k]を判定 - S[i+1]から新しくスタンプを打つ場合
S[i]のどれかがTrueなら、DP[i+1][0]を判定
最終的にDP[N-1][M-1]がTrueにできるかを見ればよいです。
計算量は1. の部分が重く、$O(NM^2)$となります。提出例
$O(NM)$解
$O(NM^2)$解の重い部分を高速化します。
スタンプの裏打ちを行い、Tの接尾辞がはみ出した状態の処理に$O(M^2)$かかっています。
少し考えると、Tの接尾辞がはみ出してよい条件は直前にTの末尾がある場面に限ると気づきます。
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]に到達したもののみ、接尾辞をつなげられないか考えることにしましょう。
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)$となります。提出例
$O(NM!)$解
破滅する方針なのでやめましょう。提出例(960ms)
実装の要点
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))
実装諸注意:
- S[i]のスタンプ番号は小数点を使いましょう。
整数だと同率タイになってしまい破滅します。 - 遷移決定後の座標圧縮で0を潰さないようにしましょう。
たとえば塗り順が(3,2,1),2.5のとき、(S[i]=T[0], 遷移先=(1,0,2))のように座標圧縮すると、塗っていた場所が塗らない場所に変わってしまいWAします。
正しく(S[i]=T[0], 遷移先=(2,1,3))となるよう座標圧縮しましょう。 - 最後のS[N-M:]の部分はスタンプが打てません(はみ出ます)。
なので遷移先の末尾が0(スタンプしない)しか遷移条件を満たしません。
うまく場合分けしましょう。
全ステップも罠だらけなうえ、実装も計算量も重く大変です。
コンテスト中の私はこれで破滅しました。破滅方針は避けましょう。(終)
Z-algorithm
計算量のオーダーが落ちるようですが、原理や実装があまり理解できていないので原理の解説はしません。
ACコードだけ張っておきます。提出例
実装の要点
実装方針のメモです。T = ABCD として説明を行います。
-
AB ABC ABCDのような、接頭辞が連続してTで終わる列を取りのぞく。 -
ABCD CD BCDのような、Tで始まり接尾辞が連続する列を取りのぞく。 -
ABCD CD+BC+AB ABCDのBCはスタンプの押し方が存在する。
「除去した部分」 +「Tの連続部分列」+「除去した部分」の形に限りスタンプが打てるので、残った部分がこの形になっているか確認する。
1.と2.はZ-algorithmと尺取法、3.は尺取法で消し残った部分を探してZ-algorithmを行います。
このうち、3.がコーナーケースになりやすいです。
たとえば S = ABCB, T = ABC でTrueと誤判定してしまいがちなので注意しましょう。(終)
おわりに
おわりです。
たくさんかくとにぎやかになっていいなとおもいました。