ABC 221 G — Jumping sequence

考察

上下左右の選択は、座標系を変えると二つの独立な正負の選択になる。そこで同じ距離列に対する部分和DPを一度作り、二つの目標の選択列を別々に復元して、元の方向へ組み合わせる。

元座標では各DiD_iをxx軸かyy軸のどちらか一方に使うため、両座標の選択が結び付いている。この結び付きを外すため、(u,v)=(x+y,x−y)(u,v)=(x+y,x-y)という45度座標変換を考える。各方向の変位は次のようになる。

元の方向uuの変位vvの変位
右 R+Di+D_i+Di+D_i
左 L−Di-D_i−Di-D_i
上 U+Di+D_i−Di-D_i
下 D−Di-D_i+Di+D_i

ここでは二つの符号の全4組が揃っている。従って、一方の符号を決めても他方に制約は生じず、目標(A+B,A−B)(A+B,A-B)への到達を二つの符号和の問題へ分離できる。

S=∑i=1NDiS=\sum_{i=1}^{N}D_iとおく。uu側で正にする距離の和をPPとすると、負にする距離の和はS−PS-Pなので、最終座標はP−(S−P)=2P−SP-(S-P)=2P-Sである。vv側も同じ変形をすると、必要な部分和は

P=S+A+B2,Q=S+A−B2P=\frac{S+A+B}{2},\qquad Q=\frac{S+A-B}{2}

となる。分子のどちらかが奇数、または得られる目標のどちらかが00未満・SS超過なら、ここで No と判定する。範囲内の整数でも、その和を作れるとは限らないのでDPで確かめる。

二次元の到達位置をそのまま管理すると、候補領域は総距離の二乗規模になる。一方、部分和なら00からSSまでで済む。ただしN≤2000N\leq 2000、S≤3.6×106S\leq 3.6\times 10^6なので、真偽配列の各要素を一つずつ更新しても最大約7.2×1097.2\times 10^9回と重い。ここで到達集合をbitsetに詰め、64個の和を一語で更新する。

dpidp_iを「先頭ii個から選んで作れる和」のbitsetとし、dpi[s]=1dp_i[s]=1を和ssが作れることと定義する。各行はbit 00からbit SSまでを持つ。dp0dp_0はbit 00だけを1にし、i=1,…,Ni=1,\ldots,Nの順に

dpi=dpi−1OR(dpi−1≪Di)dp_i=dp_{i-1}\mathbin{\mathrm{OR}}(dp_{i-1}\ll D_i)

と更新する。右辺の前半は不採用、後半は採用して和にDiD_iを加える場合を表す。どちらも更新前の行から計算するので、一つの距離を重複して使わない。dpN[P]dp_N[P]またはdpN[Q]dp_N[Q]が0なら No である。

経路を出力するため、ここでは先頭からの各段階の履歴dp0,…,dpNdp_0,\ldots,dp_Nを保存する方式を採用する。最終行だけでは、ある距離を使わずに残りの和を作れたかを判定できないからである。履歴自体は目標に依存しないので、P,QP,Qで一つを共用できる。

一つの目標からの復元は、残りの和をttとして、次の手順で行う。

  1. ttを目標PPまたはQQにする。到達判定済みなので、最初はdpN[t]=1dp_N[t]=1である。
  2. i=N,N−1,…,1i=N,N-1,\ldots,1の順に、一つ前の行dpi−1[t]dp_{i-1}[t]を調べる。1ならDiD_iを使わずに残りの和を作れるので、不採用とし、ttは変えない。
  3. 0ならDiD_iを採用し、t←t−Dit\leftarrow t-D_iとする。減算前にはdpi[t]=1dp_i[t]=1で、不採用では到達できない以上、採用による遷移が必ず存在する。従って減算後もdpi−1[t]=1dp_{i-1}[t]=1で、負の添字にはならない。
  4. 各位置の採否を記録しておく。全て戻ると、空の先頭部分で作れる和は0だけなので、t=0t=0となる。

採用・不採用の両方が可能でも、一つの経路が得られればよいので不採用を選んでよい。PPの復元結果をpip_i、QQの復元結果をqiq_iとし、それぞれ採用を1、不採用を0で表す。二回目はt=Qt=Qから新たに戻り、履歴のbitを消さない。 同じDiD_iを両方の部分和で採用してもよい。二つの採否は、一回の跳躍の二つの符号を表すからである。

例えばD=(1,2,4)D=(1,2,4)、目標(A,B)=(1,4)(A,B)=(1,4)なら、S=7S=7、P=6P=6、Q=2Q=2である。dp0,dp1,dp2dp_0,dp_1,dp_2の到達集合はそれぞれ{0}\{0\}、{0,1}\{0,1\}、{0,1,2,3}\{0,1,2,3\}となる。

  • i=3i=3では、PP側の残り6はdp2dp_2で作れないので4を採用し、残り2にする。QQ側の残り2は既に作れるので4を不採用にする。
  • i=2i=2では、両方とも残り2をdp1dp_1で作れないので2を採用し、残り0にする。
  • i=1i=1では、両方ともdp0[0]=1dp_0[0]=1なので1を不採用にする。

従ってp=(0,1,1)p=(0,1,1)、q=(0,1,0)q=(0,1,0)と、異なる二列が得られる。各位置で(pi,qi)(p_i,q_i)を(1,1)→R(1,1)\to\text{R}、(0,0)→L(0,0)\to\text{L}、(1,0)→U(1,0)\to\text{U}、(0,1)→D(0,1)\to\text{D}と戻す。この例の出力は LRU となり、(0,0)→(−1,0)→(1,0)→(1,4)(0,0)\to(-1,0)\to(1,0)\to(1,4)と目標に着く。一般の場合も長さNNの文字列のii番目に方向を書き込み、Yes とともに出力する。

典型の発動条件

45度座標変換

二次元で各操作がxx軸またはyy軸方向を選び、両座標の選択が結び付いているときに候補となる。(x+y,x−y)(x+y,x-y)へ写し、変換後の操作集合が二つの符号の全組合せになれば、各成分を独立に解ける。一部の符号組が欠けている問題では、この独立性は成立しない。

bitset subset sum と復元

正の整数の重みから各要素を高々一度選び、総和が数百万程度に収まるなら、到達可否をbitsetのshiftとORでまとめて更新できる。さらに選択列が必要なら各段階の履歴を残し、「直前の段階で、今の和へ既に到達できたか」を逆順に調べる。重み列が同じ複数の目標には、同じ履歴を共用できる。

問題固有の要素

45度変換後の四方向が単に候補を減らすのではなく、二符号の全直積になるため、二つの部分和を別々に解いても必ず一つの実方向へ合成できる。

別の問題へ持ち帰る視点は、多次元操作の候補集合が符号や小集合の直積になる座標系を探すこと。独立に解いてよいかは、成分の任意の組合せが元の合法な操作に戻るかで確認する。

正当性

部分和DPの各遷移は、DiD_iを使わない選択と一度だけ使う選択を過不足なく表すので、dpi[s]dp_i[s]は先頭ii個で和ssを作れることと同値になる。逆追跡では、処理前のdpi[t]=1dp_i[t]=1を保つ。dpi−1[t]=1dp_{i-1}[t]=1なら不採用で同じ和を残せる。偽なら遷移式のもう一方が真でなければならず、t≥Dit\geq D_iかつdpi−1[t−Di]=1dp_{i-1}[t-D_i]=1なので、採用してttを減らせる。従って常に先頭i−1i-1個へ進め、最後はdp0[t]=1dp_0[t]=1よりt=0t=0となる。各添字を一度ずつ処理するので、得られた採否列は各距離を高々一度使い、指定した部分和を実現する。

各跳躍の方向と変換後の二符号は一対一である。P,QP,Qから別々に復元した採否列を組み合わせても各位置で合法な一方向に戻り、変換後の終点は(A+B,A−B)(A+B,A-B)となる。逆変換で元の終点も(A,B)(A,B)になる。反対に、合法な経路からは必ず二つの部分和が得られるので、偶奇・範囲の検査または到達判定で失敗した場合には経路は存在しない。

実装上の注意

  • P,QP,Qの偶奇・範囲をbitset参照前に検査する。目標0は空集合、目標SSは全要素の採用に対応し、どちらも有効である。DiD_iが同値でも添字ごとに別の跳躍として扱う。
  • 履歴は1 bitずつ詰めた格納を使う。1状態を1 byteで持つと約7.2 GBになり収まらない。約900 MBの履歴を関数の通常のローカル配列としてスタックに置かず、静的領域またはヒープに確保する。行全体の不要なコピーを避け、shiftやORの一時bitsetもメモリ見積りに含める。
  • 64 bit語列でshiftを自作する場合は、語内の移動量0を特別扱いし、64 bitちょうどのshiftを避ける。最後の語のbit SSより上は範囲外として扱う。
  • 逆追跡ではdpidp_iではなくdpi−1dp_{i-1}を読む。方向は元の添字位置へ書き込む。文字列の先頭への挿入を繰り返すと、移動・コピーのため復元全体がO(N2)O(N^2)になり得る。

省メモリ化の代替案として、個別公式解説には、距離列を前後に分割して各半分の到達集合を再計算し、目標を二つの部分和へ分けて再帰する方法がある。履歴全体を持たずに復元できるが、ここで具体化した逆追跡とは別の方式である。以下の計算量は、各段階の履歴を保存する方式について評価する。

復習の核

  • 多次元の選択を独立に解く前に、変換後の候補が各成分の全組合せを含むか確認する。
  • DPの復元では「今の状態が、残りの要素で実現可能」を保ちながら一段ずつ戻る。直前でも同じ和を作れれば不採用、作れなければ採用が必要になる。
  • 複数の目標が同じ重み列を使うなら、到達履歴は一つでよい。目標ごとに残りの和と採否列を分ける。

計算量と制約

時間

一語をw=64w=64 bitとし、bit 00からbit SSまでのS+1S+1 bitを格納する語数をM=⌈(S+1)/w⌉M=\lceil(S+1)/w\rceilとおく。入力・総和・目標の計算はO(N)O(N)、履歴の初期化とNN回のshift・OR・行保存はO((N+1)M)O((N+1)M)である。二つの目標の逆追跡は各段階で定数回のbit参照を行うので合わせてO(N)O(N)、方向列の組立てと出力もO(N)O(N)。全体でO(NM+N)O(NM+N)となる。

空間

履歴はdp0dp_0を含むN+1N+1行で、6464 bit語を(N+1)M(N+1)M個使う。shiftの一時領域はO(M)O(M)語、距離列・二つの採否列・出力文字列は合わせてO(N)O(N)領域である。全体はO((N+1)M+M+N)O((N+1)M+M+N)語、すなわちO(NM+N)O(NM+N)語。二つの目標に履歴を二組用意する必要はない。

制約との対応

公式制約は1≤N≤20001\leq N\leq 2000、∣A∣,∣B∣≤3.6×106|A|,|B|\leq 3.6\times 10^6、1≤Di≤18001\leq D_i\leq 1800で、入力は整数。制限時間は5秒、メモリ制限は1024 MiBである。従ってS≤3,600,000S\leq 3{,}600{,}000、最大の語数はM=56,251M=56{,}251となり、DPは約1.13×1081.13\times 10^8語分の更新を行う規模になる。

最大サイズの履歴の容量は

2001×56,251×8=900,466,008 byte2001\times 56{,}251\times 8=900{,}466{,}008\ \text{byte}

で、約900.47 MB、約858.8 MiBである。これはbit SSとdp0dp_0、各行の語境界への切上げを含む。shift用の一時bitset一つは56,251×8=450,00856{,}251\times 8=450{,}008 byteで、OR結果も別に作る実装ならその分も加わる。これらと入力・出力などを含めて1024 MiBに収める。公式解説も履歴を全て保存するbitset方式を示しており、ここで補った逆追跡の不変条件・小例・語単位の見積りは、その手順を具体的に追うための説明である。

出典

分類・前提・執筆情報

掲載状態: 収録済み

Jumping sequence の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: bitsetで集合演算をword並列化する

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

    主タグ: bitsetによるword並列集合演算

    補助タグ: 構成解・witness復元 幾何の基本判定・配置・座標変換

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

    学習の位置

    体系上の位置: bitsetで集合演算をword並列化する

    • 集合をbit列へ符号化し、交差・和・shift・popcountをword並列に実行した計算量を評価できる。

    先に読む単元:

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

    • 集合状態そのものを一つずつ遷移するbitmask DP、および単一整数のbit演算だけで完結する処理。

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題