sataniC++

C++、競プロ、数学などについて色々考えたりします。

World CodeSprint 12 雑多解説

World CodeSprint 12にて,ついにコンテスト中全完してパーカーゲットしました!
嬉しい勢いで解説記事を簡単に書いておきます.

なお,コンテスト中に個人slackで書いてたやつのコピペなので,結構適当だったり微妙に間違ってたりするかもしれないのでそこはご了承ください.(いつかちゃんと書くことがある…かも?)


テンプレが長いので初めに示して,問題解説では主要部分だけ書いておきます.
(マクロ多いので見づらいですが,REP,RREP,FOR,RFORはfor関係,VAR,VEC,VEC_ROWあたりは入力関係,OUT,SP,BRは出力関係です)


1. The Salesman

問題文

解説

昇順ソート→x[n-1]-x[0]が答え.

コード

コメント

†やるだけ†

2. Red Knight's Shortest Path

問題文

解説

上下移動してから左右移動する.
上下移動するとき,高さは±2しか出来ないので高さの偶奇が合っていなければImpossible.
同様に左右移動も±2しか出来ないので偶奇をチェックする.
最後に決められた優先順位通りになるようソートする.

コード

コメント

枠からはみ出るケースがありそうな気もしましたが,優先順位でソートしてやったらACでした.

3. Breaking Sticks

問題文

解説

各a[i]は独立に,最大の素因数で割っていくようにすると最適(っぽい).

コード

コメント

実験したら最大の素因数で割ればよいと分かったんですが,証明はしてないです….
実験はこんなやつを書きました.

4. Factorial Array

問題文

解説

n! mod 1e9はn>=40では0なので.40以上は全て40として管理.
40の区間[l,r)をsetで持っておいて,
・1加算クエリは左から順に足してく,途中40区間に入ったら区間の終わりまで一気に飛ぶようにする.
・階乗和計算クエリは予めBITに階乗の値を乗せておけばOK.
・更新クエリは普通にやる(40→40未満になるときは区間が分裂したりするので注意)

コード

コメント

「40以上は全て40とみなしてよい」が一番の気づきポイントでした.
そのように同じ要素が大量にある列についてのクエリは,その要素がある区間をsetで管理すればいいよ!ってのを前Twitterで見たのが勝因だったと思います.

5. Animal Transport

問題文

解説

†実家†

まずEとC->1, DとM->0などと置き換えて,0と1の区間が重ならないようにとる問題としてよい.
(以降,t=0/1の区間をt区間と呼びます)

位置iを見ているとき(iは先頭から順に見る),
dp_i[t=0/1][j]:=区間[j,i]ではt区間を使い,j-1では(1-t)区間を使うとしたときに取れる区間の最大数

としたDPテーブルを更新していく.

更新は,左端がl,右端がiのt区間について,dp[t]の[0,l]に1を遅延セグ木で足す.
すると,位置iでtを使ったときの最大区間数はdp[t]の[0,i]の最大値Mとなるため,これもセグ木で取得するようにする.
このとき,答え配列ansのM番目にiを書き込む(既にi以下が書き込まれていたら書かない).
そしてansを後ろから最小値の更新を行えばよい.

(s[i]<d[i]とは限らないので注意(10WA))

コード

コメント

いわゆる†実家†をこういう難しめの問題で初めて出来た気がします.
(簡単な問題をセグ木パンチすることはたまにあった)

†実家†と呼ばれるのは,典型も典型で「ああアレね」と実家のような安心感をもって書けるから,
みたいな話を聞いたような気がするんですが,どうにもまだ全然パッと思いつけなかったので,
将来的に実家を増やしていきたいです.(?)

6. Keko the Brilliant

問題文

解説

dp[v][x]:=根をvとする部分木T(v)でvの値をx(以上)としたときにT(v)が制約を満たすようにするのに変更する必要のある最小頂点数

とした木DPを考えると,dp[v]の配列は[0,0,0,1,1,2,2,3,3,3,4]みたいに単調非減少な形になるので,
この増加する部分だけをもつ(いもすする前みたいな感じ,以下増加配列と呼ぶ).

vの子からvへの遷移は,よく観察すると,すべての子の増加配列を足して(マージテクしたけどしなくても良さそう?)出来た増加配列について次の3操作を行えばよいことがわかる:
1.増加配列[0]に1加える
2.r[v]以下で最大の非0要素から1引く
3.増加配列[r[v]+1]に1加える

あとはdp[0]の増加配列[0]が答えとなる.

実装では,増加配列をmapで持てば,上記3操作はO(logN)で出来る.
この遷移がN回行われるので全体としてはO(NlogN)となる.

ちなみに,木上のdfsを再帰で書くとstackoverflowするので非再帰で書かないとダメっぽい.

コード

再帰で書いてたものをrec_algo名前空間に(RE),非再帰で書いたものをunrec_algo名前空間に書いてます.
(非再帰で"dfs"という関数が再帰してないのが変ですが気にしないでください)

コメント

少し前にCSAでこれの列バージョンみたいな問題が出て,それの想定解はLISを求めてやるものだったので割とそっちに思考を持ってかれました.

そのあと増加配列を全て持つO(N^2)☟を書いて,最終的に上記の解法を思いつけました.♨

7. Max Transform

問題文

解説

(1-indexed注意)

f:id:satanic0258:20171216235745p:plain
図1. S(A)からS(S(A))を作るときに出来るピラミッド
図1はS(A)で隣接2要素のmaxをそれらの上に書いて出来るピラミッドを左にずらしたもの.
これを左下から右に向かって順に見ていくとS(S(A))となる.
つまりこのピラミッドの全要素の和を答えればよいことになる.

左下の小さい三角形はAからS(A)を作るときに出来るピラミッドで,このピラミッドを左下から右に向かって順に見ていくとS(A)となる.
よく見ると,このピラミッドの右隣に1段目を無くしたピラミッドがあり,さらに右隣には1,2段目を無くしたピラミッドがある(ピラミッドが無くなるまで続く).
すなわち,左下ピラミッドについて,i段目の値をi倍すると左下ピラミッドしか見る必要がなくなる.

i段目i倍ピラミッドの和について,ピラミッドをよく見ると数の大きいものから優先して上と左上に数を書き込んでいって出来る平行四辺形から構成されていることが分かる.
この平行四辺形のi段目をi倍したものの和は,一番下の起点となる数がx,幅w,高さhとすると,xwh(w+h)/2であることがよく考えると分かる.
あとはこれを数の大きい順に足していけばよい.
(幅,高さを求めるために,まだ埋まっていない区間をsetで管理するとO(NlogN)で出来る)

次に,今見たピラミッドの上にある大きい平行四辺形の和を求める.
見てみると,ほとんどの要素がM:=max(a)で埋まっていて平行四辺形の右下にMでない要素があったりするが,全ての要素がMで埋まっているとして計算し,後で過剰な分を引くことにする.
この平行四辺形は,i=2~nについて幅i,高さ(i-1)i/2であることが分かるので,答えにM×Σ_{i:2~n}( (i-1)i^2)/2を足す.

f:id:satanic0258:20171216235748p:plain
図2. 過剰分を計算するにあたって
最後に過剰分について,それぞれどの区間のmaxに起因しているかを調べると,
図2のように左下ピラミッドより右から来ている数字はもともと左端の区間から生成されていることから,
左端からl個と右端からr個の要素のmaxからなっていることが分かる.
(画像の赤数字は左がl,右がrを表す)

さらに,画像の青枠内は右隣の大平行四辺形にも出現し,オレンジ枠内はさらに右隣の大平行四辺形にも出現する(同様に右端の大平行四辺形まで).
つまり先ほどの議論と同様に,枠の中に入った個数分だけ倍にして計算すればよいことが分かる.
この"枠の中に入った個数分"とは,画像を見てみるとmin(l-1,r)となることが分かるので,
結果として各l=1~n,r=1~nについて,min(l-1,r)×(M-max(a[1~l],a[r~n]))の和が過剰分の合計となる.

f:id:satanic0258:20171216235751p:plain
図3. 過剰分についての考察
上の式において,aをa[i]=M-a[i]としてml[i]:=min(a[1~i]),mr[i]:=min(a[i~n])と置くと,
各l,rでmin(l-1,r)×min(ml[l],mr[r])を求めればよいことになる.
それぞれの数を表にすると図3のようになる.

ここで,min(l-1,r)は左上が角となるようなL字型に同じ数が配列していることが分かる.
そのため,このL字型上にあるmin(ml[l],mr[r])の和が分かればそれにL字型にある数を掛ければよいことになる.

L字型上にあるmin(ml[l],mr[r])の和を求めるために,(行の和)+(列の和)-(角)を求める.
愚直に見るとO(N)かかって全体でO(N^2)となるが,ここでmrが単調非増加列となっていることから,
ml[i]とmrの各要素でminを取るとき,mrの左端からどこまでml[i]で書き換えられるかはにぶたんで求めることが出来る.

従ってその位置をpとすると,ml[i]×p+Σmr[p+1~n]が行の和となる(mlも同様に単調非増加列であるから,列も同じようににぶたんで求められる).
角の値は普通にmin(ml[l],mr[r])を求めればよい.

これでL字型上にある数の和がO(logN)で求まり,L字はO(N)個あるので,以上より過剰分はO(NlogN)で求まる.


結果として,左下ピラミッドではsetを使うのでO(NlogN),大平行四辺形はO(N),過剰分はO(NlogN)で求まるので全体でO(NlogN)で答えが求まる. (完)

コード

コメント

かなり厳しい戦いでしたが,エクセルで実験しまくっていたら何とか解法が降りてきました.
やることはいっぱいありますが,一つ一つのアルゴリズムはそこまで難しいものではないのでひたすら考察に時間を掛ければACしやすい問題かも?(それでも大変ですが)

まとめ

毎回CodeSprintではご飯食べてる間も講義受けてる間も夢の中でも48時間ずっと考察しているのですが,中々100位以内に入れなくて苦汁をなめていました.

今回無事全完出来たのは,最終問題で要求されるアルゴリズムがそこまで高度でなかったからだと思います.
(ナントカ分解とかイケイケデータ構造とかはあまり得意でないので)


次回も100位以内がんばるぞい!