M-SOLUTIONS プロコンオープン E - Product of Arithmetic Progression
M-SOLUTIONS プロコンオープン C - Best-of-(2n-1)
なんとかこういう問題の本質がわかった気がする。
まず状態遷移を考えると、今までにAがi回勝って、Bがj回勝った、という状態をS(i, j) とおく。これに引き分けがk回あった、という状態を考えてしまうと引き分けは永遠に続くことがあるので、状態の数が無限個になってしまい考えにくい。そのためAとBの勝数だけで状態を作る。
すると、 S(i,j) へ遷移する可能性があるのは、S(i-1, j) (Aが勝った), S(i, j-1) (Bが勝った), S(i, j) (引き分け) となる。これが難しいところは同じ状態に戻ってくる遷移がある、つまり状態遷移がDAGではないためDP等ができないところにある。そのため、普通に計算すると無限級数の計算が必要になる。
そこで、この状態遷移を期待値E[i, j] の遷移と捉え、E[i - 1, j] または E[i, j - 1] からの遷移のみで記述できないか、という考察をする(これが最も重要)。これが達成できると期待値の遷移がDAGとなり、少なくともDPで計算できる。
これは、E[i, j] から引き分けが続き 次のステートへ進む回数の期待値を計算すればよい。これは引き分けの確率をcとする時、(1/1-c) となる。漸化式を用いて証明もできるが(次のステートに進む回数の期待値をeとおくと、 e = (e-(1-c)(1-e) + (1-c) より) 要は大体1/(1-c) 回投げると1回勝ちか負けかにはなる、という感じである。
というわけで状態遷移のコストを1/(1-c)倍したDAGができたのでこれをDPとして解けばよい。今回はdpにすらする必要はなく、AまたはBがn-1回勝って、他方がn-1回以下勝って、次のAまたはBが勝ち、n回勝利確定、という期待値を計算し、全体を1/(1-c)倍すればよい。計算量はこの他方の勝数のループのところでO(N)。
ちなみに具体的に無限級数の式を書き下すと、この程度ならWolfram Alphaで計算できるらしい。OEISとともに覚えておきたい。
ありがとうWolframAlphaくんhttps://t.co/9l5H996iE8
— satanic@競プロ💪 (@satanic0258) June 1, 2019
NIKKEI Programming Contest 2019 D - Restore the Tree
トポロジカルソートして 「dp[i] = max(dp[i], dp[i + 1] + 1)」を後ろから計算する。これは何をやっているかというと、葉を0とし、各頂点から一番遠い葉までの距離が入っている。
問題文で追加されているという辺は必ず子へのショートカットとなる辺なので、子からみた直接の親となる頂点は、親候補→子 となるエッジのある親候補のうち、dp[親候補]が最小の頂点が親になる。
ちなみに dp[親] = dp[子] + 1 は誤りである。なぜなら、親から見た別の子がより遠い葉を持っている可能性があるからである。
計算量はトポロジカルソートが支配項で O(N+M)。
NIKKEI Programming Contest 2019 E - Weights on Vertices and Edges
日経のコンテスト出ましたがこれが通せなかったため解法をマスターしておく。この手の問題は得意だったはずなのに通せなかったのは少し反省。
「辺をいくつか除いたときの連結成分ごとのほにゃらら」は逆から考えてUnion Findで処理する。ここまではすぐ発想できた。このとき、この考えで辺の重みを小さい方から付け加えていったときに、トータルの連結成分の頂点の重みの総和はUnion Findで計算できる。これを計算した直後に、今見ている辺の重みと比較することで最終的にその辺が使われるかどうかが判定できる。更にそのへんはその時点での各連結成分の中で最大の重みを持つ辺になっている。
そこで上記の処理が全て終わったら今度は上記の結果必ず使われる辺のリストで、辺の重みの大きい方から、その辺の重み以下の辺からなる連結成分をdfsですべて塗りつぶしていく。計算量を落とすためにすでに通った辺は無視するものとする。このとき、辺の重みを小さい方からやってしまうと、小さい重みを持つ辺でブロックされてしまうエリアができてしまい、その後から大きい辺でdfs しようとしても「すでに通った辺は無視」というロジックによって塗りつぶされないエリアができてしまう。
計算量は辺のソートでO(m log(m))
Yukicoder 777 再帰的ケーキ
たまに目にする2次元LISなやつです。
まずシーケンスa[i]に対して、a[i_1] < a[i_2] < ... < a[i_k] となるような部分列の長さはLIS等の典型アルゴリズムで簡単に求められます。ここで、更に別のシーケンス b[i] も追加してb[i_1] < b[i_2] < ... < b[i_k] となるようにする、というお話です。
これは典型手段として下記のようにやるみたいです。
- b[i] を座標圧縮し、bx[i] (0<= bx[i] <= n-1) とする。(後にこの要素をインデックスとするRMQを用いるため)
- (a[i], bx[i]) という要素の列をa[i] 昇順、bx[i] 降順でソートする(これをすることにより、a[i] = a[i + 1] の場合のめんどくさいコーナーケースがなくなります。実験するとすぐわかります)
- 各(a[i], bx[i]) に対して、初期値0の数列dp[i] に対するRMQを用いて、[0, bx[i]) のdpmax を計算し、 d[i] = max(d[i], dpmax + 1) と更新する。
- d[i] には最後の要素がbx[i]であるような最大の部分列の長さが入っている
これは要はDP＋セグメント木による高速化を行っています。本来の遷移式は下記のとおりです。
dp[i番目まで処理][最後のbx] = max{dp[i-1][j] | j = 0..bx-1} + 1
単純に遷移を書くとO(N^2)ですが、maxはSegmentTreeでやることでO(N log(N))まで計算量が落ちています。
Yukicoderの方ではちょっとだけひねってあってあるケーキを追加する場合に1増えるのではなく、c[i]増えるという式になっています。ただ遷移式自体はほぼ変わらず以下のとおりです。
dp[i番目まで処理][最後のbx] = max{dp[i-1][j] | j = 0..bx-1} + c[i]
こうすることにより、答えは max{dp[n][j] | j = 0...n-1} となります。計算量はO(N log(N))。
Solidity on Ethereum Virutual Machine でアルゴリズムを書く
Solidityとはなんぞやという話なんですが、このあたり見てもらえばわかるかなと。つまりは仮想通貨で有名なEthereum上で今の言葉で言うならDAppsを作成するための言語です。
Solidity — Solidity 0.4.24 documentation
ちなみにこれ、独自言語ではあるのですが次のような構造をとっています。
まあ要はVMなわけで、Ethereum上のスマートコントラクトはこのEVMバイトコードで動いているわけですね。一応こういう独自VMの開発はやめて、ブラウザのWeb Assemblyにエコシステムに乗っかるためにLLVM使うなどの変更は検討されているみたいです。
さて、EVMバイトコードは単純なプログラムをカウンタ＋そのカウンタに応じたGas消費という特徴を持ったチューリングマシン仕様なので、VMの実装も何種類かあります。例えば本物のEthereumで可動しているevmとかいうコマンド(ethereumをapt installすると同時にインストールされるかと思います)はJITを兼ね備えた高級VMです。
一方で、Solidityの主要な開発環境の一つであるRemix-IDEにも簡単なエミュレータが搭載されており、こっちは未確認ですがその動作速度等から単純なバイトコードインタプリタではないかと予想しています。
さて、これらの上でアルゴリズムを書くとどのぐらいの性能が要求されるのか少し実験してみました。すると、単純なバブルソートの場合なんとRemix-IDEのインタプリタ版VMだと要素数15程度のソートで固まってしまいました。なんてこったい。要素数15ぐらいだと下手にマージソートとか書いても定数倍で逆に遅くなるんじゃないか・・・という疑念はあるものの一応書いてみましたがそれでもGas消費量は半分ぐらいにはなるようです。
というわけでやっぱりネイティブのコードで動くようなアルゴリズムをEVM上で動かすのはやめたほうがいいですね…。一応本家EVM上で動作させると要素数100程度まではまぁ動くのですがGas消費量が半端ありません。正直自分でアルゴを書くよりは組み込み関数でなんとかできるならしたほうが良いと思います。
一応知見というかSolidity書くなら次のようなところに注意するとよいようです。
- memory型で処理し、最後にstorage型に代入する。
- 組み込みの関数を使えるなら使う。例えば乱数ならXor Shiftを自分で実装するのではなく、未来のHashを使う、など。
- 再帰は実際の計算量はともかく、Gas消費量としては意外と軽いのではという疑惑(再帰版のマージソートが意外と軽かったため)
- 基本の整数が256bitとかいう恐ろしいサイズのため心理的にとても遅い感じがする。
- 関数の修飾子pure view や、変数の修飾子memory storage等が一般的な言語からすると若干戸惑う(でもすぐなれる)
- バージョンが0.1違うと別言語 ←ココ重要
- 配列がサイズ指定だったり途中まで可変長だったり若干わかりにくい
正直システムプログラミングっぽいことをするなら十分なのかもしれないですが、アルゴリズムをゴリゴリ書くにはちょっとあれですね…WASM版でなんとかなるとよいのですが。
DISCOコンテスト2019 予選 D - チップ・ストーリー ～黄金編～
あるNに対して、Nをb進数で表した時の桁の和をa[b]とおく。a[2]～a[30]までが与えられるので、Nとしてあり得る数として10^12以下のものを求める問題です。
受験数学とかでNが9の倍数かどうかの判定として各桁の和で判定できる、という知識は有名かと思います。一般にNをb進数で表したとき、N = a[b] mod b-1 となります。これは実際にb^nで展開して両者引いて見るとすぐに分かります。
そのため、中国剰余定理を使ってすべてのbに対して N= a[b] mod b-1 の条件を満たす数を1個生成すると(これをXとおきます)、条件を満たす数はある数Yが存在してX + Y*LCM(2, 3, ..., 30) となります。
LCM(2,3,...,30)=2329089562800<10^12 であるため、10^12以下のものを1個見つけたらそれしか答えの候補はありません。見つけたらその数についてa[2]～a[30]の条件を満たすか確認し、OKなら出力します。計算量は無視できるサイズです。
中国剰余定理を知ってるかどうかで参加者の出来が別れたみたいです。
