Codeforces Round #719 (Div. 3) Editorial (Japanese)

laycrs @laycrs

G，コストA[i][j]で別空間に行けて，コストA[i][j]で戻ってこれると思ってダイクストラ．966ms．後で考えたらスタートとゴールからそれぞれBFSするのが想定な気がする264ms．なぜ5000*5000にしなかった（入力…）． pic.twitter.com/x2h2igZb40

拡大

拡大

m_99 @m_99kyopro

G.ポータルを使わない場合, bfsで求められる 使う場合, ポータルによる移動を2回以上するのは無駄なのでスタート側とゴール側を決める 前者はスタートからの距離+A, 後者はゴールからの距離+Aなのでスタート・ゴールからそれぞれbfsをすれば独立に最小コストを求められる

laycrs @laycrs

E，「A[i]←i番目の*の位置-i」とかやって*の幅を0にしたらA[i]を全部一致させたくなる．中央値に集める． F，二分探索を以前聞いた場所の答えを覚えておきながらやる．0が1に変わるのは適当にfenwickで覚えておいて補正．回数数えてないけど大丈夫だろうと提出． pic.twitter.com/WbaGuwAgaD

拡大

拡大

m_99 @m_99kyopro

D.変形するとaj-j=ai-iとなるのでai-iの値をmapに入れてコンビネーション E.色々やりようはありそうだけど, 一次関数(の線分)をimosで加算した F1.二分探索 F2.最初に最大2e4回使って10個ずつ総和を求めて, 幅10の中で高々4回のクエリによって答えを求める(更新は遅延セグ木で)

m_99 @m_99kyopro

CF#719(Div3) A.ランレングス圧縮してソートして隣り合わないか調べた B.せいぜい9桁までなので9*9通り全部調べる 前計算するとちょっと高速だけど多分いらない C.n≠2の時, 市松模様に塗れば前半と後半の境界以外は隣り合わないし, 上から順に塗れば境界も自然と隣り合わずに済む

laycrs @laycrs

Codeforces Round 719 (Div. 3)． A，やる． B，全部作って二分探索で数えた． C，対角にずらしながら並べた． D，A[i]-iが一致するペアの数．A[i]-iをソートして数えた． pic.twitter.com/I6sKPqMa8A

拡大

拡大

拡大

拡大