ARC025 D コンセント
古いARCの問題はそもそも挑戦者が少なく、挑戦して回るとふいにFastest codeが取れたりする。
それに気をよくした中級者が勘違いをして解説をしようとする。そんなお話。
(追記:この記事はuzzyが競プロを始めて半年程度のときに書いた記事で、まだFastestも数個程度でした。)
この問題はそもそも結構難しくて、4年以上前の問題だけど歴代でも数十人しか解いていない模様。私も例外ではなく一度降参して、解説をみてもピンと来なかったので次の問題を埋めに行った経緯があります。
しかし先日不意にクリックして考察して、解説をみたらピンときたので「俺は神だ」と自己暗示しながら、しかし3時間近くかけてACしました。
AC後に「難しい問題が解けたなぁ」と満足げにちょいちょいコードをいじって提出を重ねるとだんだん実行時間が短くなって、なんだかFastest codeが取れました。
私が取る前のFastestはコンテスト中の最初のACコードだったようなので、化け物だなぁとしか思えませんね。
縦に最大2行、横に最大10^11列の穴が並んでいて、縦か横に連続した二つの穴を使ってコンセントを差し込むとき、その差し込み方の組み合わせの総数を求める問題。
解くにあたり以下のワザを使いました。
・全体的には「DP」で数え上げました。
・「座標圧縮」しました。
・DPの漸化式を行列で書いて、「ダブリング(繰り返し二乗法)」で行列累乗を高速化しました。
・一点更新の、一番基本的な「Segment tree」で仕上げました。
では頑張っていきましょう！
まずDPで数える方法を考えます。色々ありそうな気がしますが、私が思いついたまま書きます。
順番に一列ずつ見ていくとして、縦が最大2行なので、一つ手前の列の穴の状態は両方空き、下が空き、上が空き、両方埋まり、の4つです。
つまりDPとしては4つの数を伝えていけば数え上げられます。
コンセントの指し方は、今の行だけでおさまるか、今の行と前の行にまたがるものを毎回数えます。
まずコンセントキャップ無しでパターンを考えましょう。計5種類です。
(迫真のマウスペイント)
この5種類をうまく勘定すればいいわけですね！
i列目まで見たとき数え上げてきた数4つとして、両方空きをdp[i][0]、下が空きをdp[i][1]、上が空きをdp[i][2]、両方埋まりをdp[i][3]としましょう。
上の画像を全部考えれば以下の感じになります。
dp[i+1][0] = dp[i][0] + dp[i][1] + dp[i][2] + dp[i][3]
dp[i+1][1] = dp[i][0] + dp[i][2]
dp[i+1][2] = dp[i][0] + dp[i][1]
dp[i+1][3] = 2*dp[i][0] + dp[i][1] + dp[i][2] + dp[i][3]
[i+1][0]は全て空きなので、何も置かなければ達成。問題無用で全部足せばOK。
[i+1][1]は前の行にまたがらないと実現しない。今埋める行が空いてる必要がある。
[i+1][2]も同様。
[i+1][3]は前列に関わらず縦におけるので全部足せる。さらに全部空きなら横向きに二つ置ける。
同じ感じでコンセントキャップがある場合も書けます。
上にキャップがある場合は
dp[i+1][0] = 0
dp[i+1][1] = dp[i][0] + dp[i][1] + dp[i][2] + dp[i][3]
dp[i+1][2] = 0
dp[i+1][3] = dp[i][0] + dp[i][1]
下にキャップがある場合は
dp[i+1][0] = 0
dp[i+1][1] = 0
dp[i+1][2] = dp[i][0] + dp[i][1] + dp[i][2] + dp[i][3]
dp[i+1][3] = dp[i][0] + dp[i][2]
両方にキャップがある場合は
dp[i+1][0] = 0
dp[i+1][1] = 0
dp[i+1][2] = 0
dp[i+1][3] = dp[i][0] + dp[i][1] + dp[i][2] + dp[i][3]
・・・という感じですね！
さてこれであとはこの漸化式を元に全部足し算をすればいいはずですが、最大10^11列の計算を20000回やれという今回の問題にはまだ工夫が必要ですね。
解説にあるように10^11といっても大抵の場所にはキャップはなく、キャップ無しが延々と並んでいる状態になっています。ということでダブリングが視野に入ります。
漸化式を行列っぽい並びで書いたのでキャップ無しを行列で表示するのは簡単ですね。
うん！こんな感じ！
この4×4の行列を例えばAとして、A^2、A^4、A^8、A^16・・・みたいなのを前もって計算しておいて、キャップ無しが確定の長さを2進数にして、1になってるところは掛け算してく感じ。
計算時間は行列の掛け算がO(4^3)で、10^11は二進数だと2^40くらい。つまりひとつの行列計算に64×40で2500。キャップ無し確定領域が20000個くらいで計5×10^7くらい。ということでOK！
さて、キャップ無し確定領域が一つの行列にまとめられることが分かったので、あとは20000回のキャップ付け外しの件ですね。
さらっと行列累乗つかってるわけだから当然ですけど、行列は並び順さえ変えなければ計算順は自由です。(AB)C=A(BC)です。
ということでSegment treeとか使おうというわけですね。
一番単純な一点更新のセグツリーに行列をまんま持たせて、積を各ノードに入れていく感じです。変化したところの関係するノードだけを対数時間で更新していけます。
末端のほうのノードにどの行列を割り当てるかですけど、冷静になるとコンセント抜き差しするとこの行列とキャップ無し確定の行列が交互に並んでるので、例えば奇数番と偶数番でどっちかが抜き差しするノード、とか決めるといいと思います。
ここで座標圧縮みたいなことしてます。64ビット整数のT[i]の値を入れたら左から何個目の抜き差しポイントなのか出してくれるmapとか用意するといいですね。
これでもう終わりですね。セグツリーの初期化として「抜き差しポイント間の距離-1」乗したキャップ無しの行列を偶数ノードに、まんまキャップ無しの行列を奇数ノードに入れておく。
そして左からj個目の抜き差しポイントのキャップの状態、みたいな値を持っておいてクエリに従ってキャップ状態とセグツリーを更新して、結果出力。最後の結果は両方埋まってる感じのベクトルを行列にかける。((0,0,0,1)というベクトルなので行列の右の列がでてくる)
ですがやってる最中にH=1の時のことを完全に忘れていて私はWAしました。まぁH=1は下が常に埋まっているだけなのでそのまま流用できます。ダブリングするものを下にキャップがある行列にして、最後のキャップの状態も下が埋まっている感じで初期化すれば大丈夫です。
なんだかお疲れさまでした。これまとめておこうと思ってブログ作ったのでまぁ長かったですね。
私の解法としては以上ですけど、ちょっとずつ改良したらFastestとれた件もちょいと書きます。
一番ボトルネックだったのはやはりセグツリー関連です。最初は範囲Queryも書いてセグツリーつくったんですが、よく見たら全体の結果だけ欲しいのでそんなもの不要で根のノードの行列だけ持ってくればいい。
あとセグツリーの初期化はいちいち上のノードを更新する必要はない。2*N+1個の末端の行列を入れてからまとめて上を一度更新すればいい。
行列の計算の中身は、掛け算よりmodを取るのが遅い。行列の各成分はa*b+c*d+e*f+g*hという感じだが。それぞれ10^9以下なので実は全部足しても4*10^18で64ビット整数には収まる。なので各成分一回のmodでOK。
