ABC 430 F — Back and Forth Filling

考察

各整数について、置けるマスの範囲を先に求めよう。必ず先に置く整数と、必ず後に置く整数の個数から両端が決まる。さらに、その間の全マスに置けると証明できれば、一つの整数の寄与を区間への加算にまとめられる。

ここでは整数の値をラベルと呼び、ラベル ii を置くマスの番号を pip_i とする。マスは左から1始まりで数え、この番号を順位とも呼ぶ。求めるのは各マス kk に置けるラベルの個数 CkC_k であり、条件を満たす順列の個数ではない。順列全体を列挙すると、例えば LRLR… のように制約の向きが交互の場合にも候補が膨大になる。そこで「マスごとにラベルを探す」から「ラベルごとに可能な順位を調べる」へ視点を変える。

前後を強制するのはどのラベルか

Sj=RS_j=\text{R} は pj<pj+1p_j<p_{j+1}、Sj=LS_j=\text{L} は pj+1<pjp_{j+1}<p_j を意味する。先に置くラベルから後に置くラベルへ矢印を引くと、ラベル 1,2,…,N1,2,\ldots,N を順につないだ一本のパスの各辺に向きを付けたグラフになる。ラベルが隣り合うのはこのグラフ上であり、実際に置くマスが隣り合う必要はない。

ラベル ii へ矢印をたどって到達するラベルは、すべて ii より先に置かなければならない。左側から到達するには、Si−1S_{i-1} から左へ R が連続している必要がある。右側から到達するには、SiS_i から右へ L が連続している必要がある。途中で向きが変わると、パスには迂回路がないので、それより先からは到達できない。同様に、ii から到達するラベルは必ず後に置く。

四つの長さを次のように定める。同じ文字が連続する部分をrunと呼び、開始位置の文字が指定と違う場合や文字列の外の場合は長さ0とする。

長さ調べるrun強制される位置
aia_iSi−1S_{i-1} から左へ続く Rii より前
bib_iSiS_i から右へ続く Lii より前
cic_iSi−1S_{i-1} から左へ続く Lii より後
did_iSiS_i から右へ続く Rii より後

必ず前に置くラベルが ai+bia_i+b_i 個、必ず後に置くラベルが ci+dic_i+d_i 個あるので、可能な順位の下限と上限の候補は

li=1+ai+bi,ri=N−ci−dil_i=1+a_i+b_i,\qquad r_i=N-c_i-d_i

となる。ただし、これだけでは必要条件しか示していない。両端が実現しても、その間がすべて実現するとは限らないため、残りのラベル同士の制約を保った構成が必要になる。「正当性」で、その順序を一つ固定し、先頭から何個を ii の前に置くかを変える構成を示す。

例えば N=3N=3、S=RL では矢印は 1→2←31\to 2\leftarrow 3 となる。条件を満たす並びは (1,3,2)(1,3,2) と (3,1,2)(3,1,2) だけなので、各ラベルの可能位置は次のとおりである。

ラベル ii可能な順位 pip_i区間 [li,ri][l_i,r_i]
11, 2[1,2][1,2]
23[3,3][3,3]
31, 2[1,2][1,2]

したがって答えは (C1,C2,C3)=(2,2,1)(C_1,C_2,C_3)=(2,2,1) となる。ラベル1と3はそれぞれ2番目に置けるが、同じ順列で両方を2番目に置く必要はない。各ラベルについて、条件を満たす並びが一つでも存在すれば数える。

可能順位の区間を差分で集計する

各ラベルの可能順位がちょうど [li,ri][l_i,r_i] だと分かれば、その区間の各マスへ1を加えればよい。全区間を直接走査せず、差分配列を使う。

  1. 文字位置 jj まで左へ連続する R と L の長さを、配列 leftR[j]、leftL[j] に求める。j=1,…,N−1j=1,\ldots,N-1 の順に走査し、現在の文字と同じ側の長さを直前の値に1を加えて更新し、違う側は0にする。
  2. 文字位置 jj から右へ連続する長さも、rightR[j]、rightL[j] に求める。こちらは j=N−1,…,1j=N-1,\ldots,1 の順に同じ処理をする。各配列の番兵位置0と NN は0で初期化する。
  3. 各ラベル i=1,…,Ni=1,\ldots,N について、ai,bi,ci,dia_i,b_i,c_i,d_i を順に leftR[i-1]、rightL[i]、leftL[i-1]、rightR[i] から読み、li,ril_i,r_i を計算する。0で初期化した差分配列 diff に diff[l_i] += 1、diff[r_i+1] -= 1 を行う。
  4. マス k=1,…,Nk=1,\ldots,N の順に diff を累積し、その値を CkC_k として出力する。

典型の発動条件

連長の前計算

ある位置から同じ種類の制約が続く範囲を、全位置について求めたいときに使う。各位置からたどり直すと、文字がすべて同じ場合に二乗時間になる。左向きは左から、右向きは右から長さを引き継げば、各位置を定数回調べるだけで済む。

区間加算の差分配列

各対象が連続した位置区間のすべてへ同じ量だけ寄与し、更新をまとめた後に答えを取り出すときに使う。本問では「最小・最大の可能順位が分かる」だけでは足りず、間の全順位が実現することまで証明して初めて区間全体へ加算できる。

問題固有の要素

連続する整数間の前後関係を、マスではなくラベルを頂点とする有向パスへ写す。一本のパスには迂回路がないため、固定したラベルの先行・後続要素を四つのrunだけで数えられる。

別の問題へ持ち帰る視点: 各位置で可能な対象を直接探す代わりに、対象を固定して実現可能な位置集合を調べる。その集合を短く表せれば、対象と位置の全組を調べる処理をまとめられる。

正当性

ラベル ii を固定し、ii へ有向パスで到達するラベルの集合を AA、ii から到達するラベルの集合を BB、それ以外のラベル(ii 自身を除く)の集合を UU とする。元のグラフは一本のパスに向きを付けただけなので有向閉路を持たず、これらの集合は互いに素である。前述のrunとの対応から ∣A∣=ai+bi|A|=a_i+b_i、∣B∣=ci+di|B|=c_i+d_i。どの有効な並びでも AA は ii より前、BB は後になるため、1+∣A∣=li≤pi≤ri=N−∣B∣1+|A|=l_i\leq p_i\leq r_i=N-|B| が必要である。

次に、この範囲の任意の順位を実現する。各集合の内部を、矢印の始点が終点より前になる順序に並べる。このような順序をトポロジカル順序という。有向閉路がないので、集合内で入ってくる矢印のない頂点を一つずつ取り除けば必ず作れる。三つの集合をこの順序で並べた列を、それぞれ α,β,υ\alpha,\beta,\upsilon とする。

集合をまたぐ矢印にも注意する。UU から AA への矢印があれば、その始点も ii へ到達するため AA に属するはずであり、矛盾する。BB から UU への矢印も、その終点が ii から到達可能になるため存在しない。BB から AA への矢印は ii を通る有向閉路を作るので存在しない。また、UU と ii の間にはどちら向きの矢印もなく、ii に入る矢印は AA から、ii から出る矢印は BB へ向かう。従って、AA、UU、BB の順に置けば、集合間の矢印もすべて前から後へ向く。

ここで 0≤t≤∣U∣0\leq t\leq |U| を任意に選び、列を次の順でつなぐ。

α,υの先頭 t 個,i,υの残り,β\alpha,\quad \upsilon\text{の先頭 }t\text{ 個},\quad i,\quad \upsilon\text{の残り},\quad \beta

各集合内の順序は変えず、集合間の矢印にも逆らわないので、これは全制約を満たす並びである。UU の要素を独立に左右へ振り分けるのではなく、制約を満たす一つの列の先頭で区切ることが要点になる。このとき pi=∣A∣+t+1p_i=|A|+t+1 だから、t=0t=0 で lil_i、t=∣U∣t=|U| で N−∣B∣=riN-|B|=r_i、その間も1ずつすべて実現する。よって可能順位集合はちょうど [li,ri][l_i,r_i] である。この列の構成は存在を示すためのもので、解を計算するときにラベルごとに実行する必要はない。

ラベル ii の二点更新を累積すると、li≤k≤ril_i\leq k\leq r_i のマスだけに1が残る。全ラベル分を足せば、各マスに置けるラベルを過不足なく一度ずつ数えた CkC_k が得られる。

実装上の注意

  • i=1i=1 では左の二つのrun、i=Ni=N では右の二つのrunの長さを0とする。存在しない S0,SNS_0,S_N を直接参照せず、前計算配列の番兵を使う。
  • 順位は1始まりの閉区間で扱う。ri=Nr_i=N でも減算できるように、diff は少なくとも添字 N+1N+1 まで確保する。テストケースごとに配列と累積値を初期化する。
  • すべて R なら li=ri=il_i=r_i=i、すべて L なら li=ri=N−i+1l_i=r_i=N-i+1 となり、各マスの答えは1になる。N=2N=2 でも同じ式を使える。

復習の核

  • 前後関係はラベル同士の制約であり、隣接するマスの大小条件ではない。矢印を描けば、どのラベルが必ず前・後になるかを追える。
  • 可能位置の最小・最大だけでは区間加算できない。残りの要素の有効な順序を保ち、区切りを一つずつずらして、中間位置の実現まで示す。
  • 「各位置に何が置けるか」を「各対象はどの位置に置けるか」へ反転すると、差分でまとめられる寄与が見える。

計算量と制約

時間

1テストケースにつき O(N)O(N)。四つのrun配列の前計算、全ラベルの区間の計算と二点更新、累積と出力は、いずれも O(N)O(N) 時間である。

空間

O(N)O(N)。入力文字列、四つのrun配列、差分配列を保持する。証明に用いた集合や並びをラベルごとに作る必要はない。

制約との対応

1≤T≤200001\leq T\leq 20000、各テストケースで 2≤N≤3×1052\leq N\leq 3\times 10^5、SS は長さ N−1N-1 の L と R からなる。全テストケースの NN の総和も 3×1053\times 10^5 以下なので、全体の時間は O(∑N)O(\sum N)、ケースごとに配列を使い直したときの空間は O(max⁡N)O(\max N) で収まる。各 CkC_k は高々 NN であり、順列数を保持する必要はない。公式の実行時間制限は2秒、メモリ制限は1024 MiBである。

出典

分類・前提・執筆情報

掲載状態: 収録済み

Back and Forth Filling の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 一次元・二次元累積和と差分で区間情報を線形化する

主題
追加で学ぶ技能
    なし
    既習技能
      なし

      主タグ: 累積和・差分配列

      執筆: abc-explanation-author1.1.1 / revision 2

      学習の位置

      体系上の位置: 一次元・二次元累積和と差分で区間情報を線形化する

      • prefix配列またはprefix変数を置き、区間和を二つのprefix値の差で表現できる。多次元の直方体は2^D隅の包除で取得し、一括加算は端点差分へ変換できる。

      この解説で扱わないこと:

      • オンライン更新を伴うFenwick Tree・Segment Treeの動的区間要約。

      学習記録

      状況更新: 更新記録なし

      復習設定更新: 更新記録なし

      端末内の保存状態を確認しています。

      要復習一覧 / 学習記録のバックアップ / 解説に戻る

      同じ単元の問題