Misspelling 解説
ynymxiaolongbao（米山 瑛士）

問題概要
𝑆=acccbba

英小文字からなる文字列𝑆について考える

問題概要
𝑆=
𝑇1 =
𝑇2 =
𝑇3 =
𝑇4 =
𝑇5 =
𝑇6 =
𝑇7 =acccbba
cccbbaa ccbbaac cbba
acc bbaaccc baacccb aacccbb𝑇𝑖 を𝑆の𝑖文字目を削除して詰めた文字列とする

問題概要
𝑆=
𝑇1 =
𝑇2 =
𝑇3 =
𝑇4 =
𝑇5 =
𝑇6 =
𝑇7 =acccbba
cccbbaaccbbaaccbbaaccbbaacccbaacccbaacccbb𝑇𝑖 を𝑆の𝑖文字目を削除して詰めた文字列とする

問題概要
𝑆=
𝑇1 =
𝑇2 =
𝑇3 =
𝑇4 =
𝑇5 =
𝑇6 =
𝑇7 =

acccbba
cccbbaaccbba
accbbaaccbbaacccbaacccbaacccbb𝑇𝑖 ≤ 𝑇𝑗 （辞書順）の形の条件が𝑀個与えられる
それらを満たす𝑆を数え上げる

小課題１（𝑁 ≤ 10）
𝑆=
𝑇1 =
𝑇2 =
𝑇3 =
𝑇4 =
𝑇5 =
𝑇6 =
𝑇7 =

acccbba
cccbbaaccbbaaccbbaaccbbaacccbaacccbaacccbb𝑇𝑖 ≤ 𝑇𝑗 とは？(𝑖 < 𝑗)

小課題１（𝑁 ≤ 10）
𝑆=
𝑇1 =
𝑇2 =
𝑇3 =
𝑇4 =
𝑇5 =
𝑇6 =
𝑇7 =

acccbba
cccbbaaccbbaaccbbaaccbbaacccbaacccbaacccbb𝑇𝑖 ≤ 𝑇𝑗 とは？
例として、𝑇2 とT6の大小を考える小課題１（𝑁 ≤ 10）
𝑆=
𝑇1 =
𝑇2 =
𝑇3 =
𝑇4 =
𝑇5 =
𝑇6 =
𝑇7 =acccbba
cccbbaa ccbbaac cbba
acc bbaaccc baacccb aacccbb

𝑇𝑖 ≤ 𝑇𝑗 とは？
例として、𝑇2 とT6の大小を考える小課題１（𝑁 ≤ 10）
𝑆 = acccbba
𝑇2 = a ccbba
𝑇6 = acccb a

𝑇𝑖 ≤ 𝑇𝑗 とは？
例として、𝑇2 とT6の大小を考える小課題１（𝑁 ≤ 10）𝑆=
𝑇2 =𝑇6 =acccbba
a ccbbaacccb a𝑇𝑖 ≤ 𝑇𝑗 とは？
例として、𝑇2 とT6の大小を考える

・はじめと終わりは同じなので𝑆の[𝑖, 𝑗]だけ見る

小課題１（𝑁 ≤ 10）𝑆=
𝑇2 =𝑇6 =acccbba
a ccbbaacccb a𝑇𝑖 ≤ 𝑇𝑗 とは？
例として、𝑇2 とT6の大小を考える

・はじめと終わりは同じなので𝑆の[𝑖, 𝑗]だけ見る

小課題１（𝑁 ≤ 10）𝑆=
𝑇2 =𝑇6 =acccbba
a ccbbaacccb a𝑇𝑖 ≤ 𝑇𝑗 とは？
例として、𝑇2 とT6の大小を考える

・はじめと終わりは同じなので𝑆の[𝑖, 𝑗]だけ見る
・𝑆の𝒊以降で初めて文字の種類が変わる所で初めて𝑇𝑖 と𝑇𝑗 に違いが出る（𝑇𝑖 で𝑆𝑘+1 、𝑇𝑗 で𝑆𝑘 )小課題１（𝑁 ≤ 10）𝑆=
𝑇2 =𝑇6 =accccca
a ccccaacccc a𝑇𝑖 ≤ 𝑇𝑗 とは？
例として、𝑇2 とT6の大小を考える

・はじめと終わりは同じなので𝑆の[𝑖, 𝑗]だけ見る
・𝑆の𝑖以降で初めて文字の種類が変わる所で初めて𝑇𝑖 と𝑇𝑗 に違いが出る（𝑇𝑖 で𝑆𝑘+1 、𝑇𝑗 で𝑆𝑘 )・もし𝒋までに文字の種類が変わらないなら𝑇𝑖 = 𝑇𝑗

小課題１（𝑁 ≤ 10）• 𝑇𝑖 と𝑇𝑗 の大小関係は、 各kについての𝑆𝑘 と𝑆𝑘+1 の大小関係のみから判断できる• 各kについて𝑆𝑘 < 𝑆𝑘+1 、 𝑆𝑘 = 𝑆𝑘+1 、 𝑆𝑘 > 𝑆𝑘+1 の𝑁−1
どれが成り立つか決め打つ（3通り）• これを満たす𝑆の個数を𝑑𝑝で求め、𝑇の大小関係の条件を満たしているか確認し、足し合わせる• 𝐾 = 26 として計算量は𝑂(3𝑁 𝑝𝑜𝑙𝑦(𝑁)𝑝𝑜𝑙𝑦(𝐾))小課題２（𝑁 ≤ 200）
• 𝑆を後ろから決めていくことを考える

𝑆2 = 𝑆3 < 𝑆4 = 𝑆5 > 𝑆6 < 𝑆7
𝑇2 と𝑇6 の大小関係が知りたいとする

隣合う文字の大小関係も書いていく

小課題２（𝑁 ≤ 200）
• 𝑇2 と𝑇6 の大小関係が知りたい

𝑆2 = 𝑆3 < 𝑆4 = 𝑆5 > 𝑆6 < 𝑆7

小課題２（𝑁 ≤ 200）
• 𝑇2 と𝑇6 の大小関係が知りたい

𝑆2 = 𝑆3 < 𝑆4 = 𝑆5 > 𝑆6 < 𝑆7𝑖 = 2 以降で初めて文字の種類が変わる所が𝑗 = 6までにあるか、あるなら 𝑆𝑘 < 𝑆𝑘+1 か𝑆𝑘 > 𝑆𝑘+1 かが分かればよい小課題２（𝑁 ≤ 200）
• 𝑇2 と𝑇6 の大小関係が知りたい

𝑆2 = 𝑆3 < 𝑆4 = 𝑆5 > 𝑆6 < 𝑆7
一番左（＝一番最後に書いた） < や > の場所と種類をメモしておけばよい→𝑑𝑝のキーにする小課題２（𝑁 ≤ 200）
• 𝑆を後ろから決めていく• 𝑑𝑝 𝑝𝑜𝑠, 𝑥, 𝑐, 𝑜𝑝 ≔ 以下を満たす決め方の個数
・𝑆𝑝𝑜𝑠 まで決めて、𝑆𝑝𝑜𝑠 = 𝑐・𝑥は𝑝𝑜𝑠 ≤ 𝑥かつ𝑆𝑥 ≠ 𝑆𝑥+1 を満たす最小の値
・𝑜𝑝は < か > であり、 𝑆𝑥 𝑜𝑝 𝑆𝑥+12• 計算量は𝑂(𝑁 𝑝𝑜𝑙𝑦(𝐾))小課題３（𝑇をソートした順が定まってる）• 𝑇をソートしたときの順番について考える• 𝑆𝑘 ≠ 𝑆𝑘+1 のとき、𝑇𝑘+1 , 𝑇𝑘+2, … , 𝑇𝑁 は一つの連続した区間になる

𝑆1 < 𝑆2 = 𝑆3 > 𝑆4 = 𝑆5 < 𝑆6 = 𝑆7 = 𝑆8

小課題３（𝑇をソートした順が定まってる）• 𝑇をソートしたときの順番について考える• 𝑆𝑘 ≠ 𝑆𝑘+1 のとき、𝑇𝑘+1 , 𝑇𝑘+2, … , 𝑇𝑁 は一つの連続した区間になる

𝑆1 < 𝑆2 = 𝑆3 > 𝑆4 = 𝑆5 < 𝑆6 = 𝑆7 = 𝑆8

小課題３（𝑇をソートした順が定まってる）• 𝑇をソートしたときの順番について考える• 𝑆𝑘 ≠ 𝑆𝑘+1 のとき、𝑇𝑘+1 , 𝑇𝑘+2, … , 𝑇𝑁 は一つの連続した区間になる

𝑆1 < 𝑆2 = 𝑆3 > 𝑆4 = 𝑆5 < 𝑆6 = 𝑆7 = 𝑆8
↑𝑇3 は𝑇4 , 𝑇5 , … , 𝑇8 よりも小さい↑𝑇2 は𝑇4 , 𝑇5 , … , 𝑇8 よりも小さい↑𝑇1 は𝑇4 , 𝑇5 , … , 𝑇8 よりも大きい小課題３（𝑇をソートした順が定まってる）• 𝑇をソートしたときの順番について考える• 𝑆𝑘 ≠ 𝑆𝑘+1 のとき、𝑇𝑘+1 , 𝑇𝑘+2, … , 𝑇𝑁 は一つの連続した区間になる

𝑆1 < 𝑆2 = 𝑆3 > 𝑆4 = 𝑆5 < 𝑆6 = 𝑆7 = 𝑆8
↑𝑇3 は𝑇4 , 𝑇5 , … , 𝑇8 よりも小さい↑𝑇2 は𝑇4 , 𝑇5 , … , 𝑇8 よりも小さい• 𝑆𝑘 = 𝑆𝑘+1 のとき𝑇𝑘 と𝑇𝑘+1 は同じ側にある

小課題３（𝑇をソートした順が定まってる）• 𝑇をソートしたときの順番について考える• 𝑆𝑘 ≠ 𝑆𝑘+1 のとき、𝑇𝑘+1 , 𝑇𝑘+2, … , 𝑇𝑁 は一つの連続した区間になる• 𝑆𝑘 = 𝑆𝑘+1 のとき𝑇𝑘 と𝑇𝑘+1 は同じ側にある

小課題３（𝑇をソートした順が定まってる）• 𝑇をソートしたときの順番について考える• 𝑆𝑘 ≠ 𝑆𝑘+1 のとき、𝑇𝑘+1 , 𝑇𝑘+2, … , 𝑇𝑁 は一つの連続した区間になる• 𝑆𝑘 = 𝑆𝑘+1 のとき𝑇𝑘 と𝑇𝑘+1 は同じ側にある• これが満たされていれば十分→必要十分

小課題３（𝑇をソートした順が定まってる）• 𝑆を後ろから決めていく• 小課題２の𝑑𝑝から𝑥（最後に見た不等号の位置）を抜いて𝑑𝑝 𝑝𝑜𝑠, 𝑐, 𝑜𝑝 とする• 𝑇𝑝𝑜𝑠 , 𝑇𝑝𝑜𝑠+1, … , 𝑇𝑁 が𝑇をソートしたとき一つの連続した区間になるときだけ𝑆𝑝𝑜𝑠−1 ≠ 𝑆𝑝𝑜𝑠 の遷移をする• 計算量は𝑂(𝑁𝑝𝑜𝑙𝑦 𝐾 )45
小課題４,５（𝑁 ≤ 2 × 10 , 5 × 10 ）• 小課題２の𝑑𝑝をデータ構造で高速化する• 𝑑𝑝 𝑝𝑜𝑠, 𝑥, 𝑐, 𝑜𝑝 → 𝑑𝑝 𝑝𝑜𝑠 − 1, 𝑥, 𝑐, 𝑜𝑝という遷移がある（前と同じ文字にする操作）• (𝑥, 𝑐, 𝑜𝑝)ごとに値を使いまわすことにすると、𝑝𝑜𝑠が変わったとき、何もしなければこの遷移ができる45
小課題４,５（𝑁 ≤ 2 × 10 , 5 × 10 ）• 他の遷移は以下ようになる
・特定の 𝑐, 𝑜𝑝 の組に対して、𝑑𝑝 𝑥, 𝑐, 𝑜𝑝 の𝑥 <𝑟の部分を0にする（𝑇の大小関係の条件）
・特定の 𝑐, 𝑐 ′ , 𝑜𝑝, 𝑜𝑝′ の組に対して、𝑑𝑝 𝑝𝑜𝑠, 𝑐 ′ , 𝑜𝑝′ に𝑑𝑝 𝑥, 𝑐, 𝑜𝑝 の和を足す（前と別の文字にする操作）45
小課題４,５（𝑁 ≤ 2 × 10 , 5 × 10 ）• (𝑐, 𝑜𝑝)ごとに遅延セグ木を持つ→𝑂(𝑁𝑙𝑜𝑔𝑁𝑝𝑜𝑙𝑦 𝐾 )・特定の 𝑐, 𝑜𝑝 の組に対して、𝑑𝑝 𝑥, 𝑐, 𝑜𝑝 の𝑥 <𝑟の部分を0にする（𝑇の大小関係の条件）→区間に0を代入
・特定の 𝑐, 𝑐 ′ , 𝑜𝑝, 𝑜𝑝′ の組に対して、
𝑑𝑝 𝑝𝑜𝑠, 𝑐 ′ , 𝑜𝑝′ に𝑑𝑝 𝑥, 𝑐, 𝑜𝑝 の和を足す（前と別の文字にする操作）→全体の和を求める、一点更新

45
小課題４,５（𝑁 ≤ 2 × 10 , 5 × 10 ）• (𝑐, 𝑜𝑝)ごとにスタックを持つ→𝑂(𝑁𝑝𝑜𝑙𝑦 𝐾 )・特定の 𝑐, 𝑜𝑝 の組に対して、𝑑𝑝 𝑥, 𝑐, 𝑜𝑝 の𝑥 <𝑟の部分を0にする（𝑇の大小関係の条件）→左からいくつかの要素を削除
・特定の 𝑐, 𝑐 ′ , 𝑜𝑝, 𝑜𝑝′ の組に対して、
𝑑𝑝 𝑝𝑜𝑠, 𝑐 ′ , 𝑜𝑝′ に𝑑𝑝 𝑥, 𝑐, 𝑜𝑝 の和を足す（前と別の文字にする操作）→全体の和を求める、左に要素を追加

別解？
• setやpriority_queueを使う（やってることは同じ）• 二次元累積和を使って頑張る

得点分布

得点分布

1210864200828
得点分布100