CSAcademy Round #50 (Div. 2 only) Min Races
問題概要
N人から何人か選んで複数回レースをする. N人はKクラスに分かれている.
また,N人の実力は決まっており,レースをするとその実力通りの順位になる.
レースをした時,自分より順位が上の人全員が自分より上のクラスであるならその人は勝利となる.
全員が勝利するためには最低何回レースを行う必要があるか.
クラスはa_i, 実力はb_iで与えられる(どちらも小さい方が高い)
解法
a_iでソートして前から順に見ていく. 毎回各レースの最下位の人の順位を保存しておく.
(少し簡単な問題として自分より順位が上の人が自分以上(ここが違う)のクラスの人であれば勝利とする問題を考える)
ここで,もし最下位の人が自分より順位が上のレースがあるなら,そのようなレースのうち最下位の人が最も順位が低いレースに参加して自分が最下位となれば良い.
また,そのようなレースがないなら自分一人のレースを作れば良い.
最下位の人の順位を保存しておくデータ構造を考えると,二分探索,データの追加,更新ができれば良さそうなので,これはsetで実現できる.
次に,最初の自分と同じクラスが自分以上の順位でも良いという制約を除去して考えると,
同じクラスの場合は下の順位から見て行けば,上の順位を見たときに同じクラスでは自分より順位が下の人しかレースに参加していないため,
そのようなレースに参加することは避けられそうということがわかる(自分より上の人が最下位であるレースにしか参加しないため)
よってa_iの昇順に,a_iが等しい場合はb_iの降順に並べれば良い.( b_i*=(-1)してpairでsortすれば良い )
計算量はO(NlogN)となる.
また想定解としてはb_iでソートすればa_iから最長部分増加列(LIS)を取り除く作業をすればよく,これは最長部分非増加列の長さと一致する.
よくあるDPでも良いしSegmentTreeでも良い.
メモ
想定解の解法知らなかった. そうなりそうなのはわかるが証明できない..
*追記
まさにこれ
数列の要素を頂点と考えてa_iからi<j, a_i<a_jなるa_jに対して辺を貼るとこのグラフはDAGで求める答え(LISを何回取り除けるか)は最小パス被覆に一致する.
またこのDAGは推移閉包なので,Dilworthの定理よりどの二点間にもパスが存在しないような頂点の集合の大きさと一致する.
これは最長部分非増加列の長さそのもの.
推移閉包参考
競プロslackで聞いてよかった.. tozanさんありがとうございました.
コード
UTPC2014 D - ラボライブ タフグローバルフェスティバル
解法
M=1,2 の場合は容易に解ける. 以降ではM=3とする.
まず下準備として押す場所で同じ場所が連続して来る場合は結合して一つの区間にしておこう.
とりあえず一番近い指を使う貪欲を考えてみると,
p1 <--> 指1 <-> p2 <--> 指2 <-> 指3 , s1=2, t1 = s2 = 3
みたいな場合では明らかに最適でない.(p2は指2で押さないと無理)
次にどの指を使うか,O(2N)の状態数があるのでDPでできそう.
最近押したのがpx[i],py[i]であるとすると,s[i]=t[i-1]であるため必ずpx[i-1],py[i-1]にも指が置かれていたことになる.
なので1つの指はpx[j],py[j]にあったとすると全ての状態を表せるため,
dp[i][j] := (指が i, i-1, jを押している状態にできるか) とおく.
もしdp[i][j]がtrueなら
if(i-1でi+1を押せる) dp[i+1][j] = true
if(jでi+1を押せる) dp[i+1][i-1] = true
と配って行くDPをすれば良い.
なお座標は指1,指2,指3,p1,p2,...,pNと繋げて持っておくと便利.
メモ
結構好きだけどM=3だけで良くない？
コード
AGC 021 B - Holes
解法
前提知識: 凸包 (ググればいっぱい出てくる)
Rが十分に大きいので数学的にINFだとして考察していく.
各点に落ちるような領域は与えられた二点の全ての組を取った垂直二等分線で区切られる(ボロノイ図と言うらしい)
R=INFなので,この領域が有限領域であればそこに落ちる確率は0となり,そのような点は凸包に含まれない点である.
よって凸包同士の垂直二等分線で区切られた領域を考えていく.
上の考察から有限領域は無視して良いので,凸包内部の領域は無視して図でのa/2PIがAの全体に対する比率となると考えても良い.
青aの角度は外角の赤aと等しいので,凸包で隣接する点との外角を求めそれを2PIで割る.
凸包の出力は反時計回り順に出てくるので素直に実装している.
ただし,-PI < arg(Point) < PIとなるので一方が境界(PI)を超えて負になった場合には+2PIして補正しないといけない.
またindexと点をmapで紐づけているが,その場合比較関数compが必要となる.
メモ
凸包の問題解いたことなかったけど割と素直に思いついたので出たかったね.
ライブラリはasi1024さんの.
コード
ARC 068 E - Snuke Line (700)
問題概要
N個の区間[l_i,r_i],自然数Mが与えられる.
1 <= d <= Mについて,dの倍数を含む区間はいくつあるかそれぞれ答えよ.
1 <= N <= 3*105, 1 <= M <=105
解法
各dについて dの倍数を含むような区間を数え上げていく.
愚直にやろうとすると [1,M] の d の倍数で, d を動かしていくと
ループの回数は M + M/2 + M/3 + .. M/M = O(MlogM) となり,
全てのN個の区間について数えれば全体で O(NMlogM) となる.
一方で, r_i - l_i >= d-1 となる区間は必ず倍数を含むので,
この区間については O(1) で求められまともに数えなくても良いことがわかる.
よって r_i - l_i でソートして r_i - l_i < d-1となる区間だけを見ていこうという発想が生まれる.
このような区間はdの倍数を高々1つしか含まない.
よってこの区間(今見ているdに対して, r_i - l_i < d-1 を満たすような区間)について,
cnt[ x ] := ( x と重なる区間は何個あるか ) としてやって,
i=d,2d,..kd の cnt[ x ] の和を数えればよい.
dの倍数を高々1つしか含まない性質から, cnt[ id ] と cnt[ jd ] (i!=j) が同じ区間を重複して数えていることはないからである.
また d を動かしていくと新しい区間を追加していく必要があるが, これは
cnt[ x ] ( l_i <= x <= r_i ) に +1 する操作になる.
これは FenwickTree(BIT)を使えば高速にできる.
FenwickTreeは1つ足す+区間和が求められるデータ構造だが,imos法のようにl_iに+1,r_i+1に-1すると,それまでの和がその数の値となる. 計算量は O(NlogN+logM*(M/1+M/2+..+M/M)) = O(NlogN + M(logM)2 )
メモ
割と素直な解法だと思うが思いつかなかった.
区間に足しこんで数えようと思っていたら頭に浮かびそう.
倍数の全列挙がO(MlogM)なのも頭になかったかも.
コード
yukicoder No.595 登山
問題概要
要素数Nの数列{a_i}とコストPが与えられる.
任意の場所へのワープにはコストP,隣接するiからjへのの移動にはmax(0,a[i]-a[j])かかる時,全ての点を訪れる最小コストを求めよ.
2 <= N <= 2*105, 0 <= P,a[i] <= 109
解法
1 普通のDP
解説が詳しい.
dp[i][j] := (iまでを全て回るコストで,jはそこが左に行く区間がどうか(0or1)) とすると,
dp[i+1][1] =min(dp[i][0],dp[i][1])+P(ワープしてくる),dp[i][1]+max(0,a[i]-a[i])(そのまま進む))
dp[i+1][0]も同様に遷移する.
2 RMQを使って高速化
iからjまで歩くコストをd(i,j)と書く.
この二方向の累積和を
Sl(i) = d(0,1)+d(1,2)+...+d(i-1,i)
Sr(i) = d(N,N-1)+...+d(i+1,i) として求めておく.
同様にDPの式を置くと,dp[i] は以下3つのminを取れば良い.
1.1回もワープせずにiまで歩く = Sl(i)
2.j<iなるjまでワープしj->iを歩く = dp[j] + P + Sl(i) - S(j)
3.j<iなるjまで来てiにワープしi->j+1を歩く = dp[j] + P +Sr(j+1) - S(i)
2.でワープせずにjまでくる方法もあるように見えるが,それは結局1.で余分に1回ワープしているだけなので切り捨てられる.
よって2,3のjに関する項をRMQのSegmentTreeに保存しておき,3つのminを取れば求められる.
メモ
最初 j = (i地点にいるか) としたが,それだと右から来た時ワープコストをどこに足せば良いかがわからなくなった.
解法は区間と考えることで最初にワープコストを足している.
その問題を書き出した上でうまく解決できるような状態の表し方を考察するようにしよう.
コード
yukicoder No.649 ここでちょっとQK！
問題概要
自然数K,Qが与えられる.以下のクエリQ個を処理せよ.
1. 配列に値Xを挿入する
2. 配列のK番目に大きい値を出力し,削除する
1 <= Q,K <= 2*105, 1 <= X <= 1018
解法
想定解で解いた.
minキューとmaxキューを用意し,maxキューにはK番目に小さい値までを入れ,minキューにはそれ以降の値を入れる.
解説と同じように場合分けして処理を書いてけば良い.
Kが固定ならこれで良いが,Kが毎回変わる場合には少し複雑になる.
ARC 033 C - データ構造がまさにこの問題.
この問題にはいくつか解がある.
1. 座標圧縮してFenwick Tree
クエリを先読みして現れる全ての数を座標圧縮すれば 1 <= v' <= Qとなる.以下はこの数に変換して使う.
蟻本にもあるが,これはソートして何番目の数かを二分探索すれば良い.O(QlogQ).
座標のサイズのFenwick Treeを作って以下のように処理すれば解ける.
クエリ1(v) treeのv'の要素に+1する
クエリ2(K) treeのv'未満の総和が初めてK-1以上になる(それ以下の値がK-1個ある)ようなv'を二分探索する
クエリ1がO(logQ), クエリ2がO((logQ)2)で解けるので全体でO(Q(logQ)2).
- 平衡二分木を作る
yukicoderの解説に書いてある. gnu拡張を使うと楽. - 平方分割
ARC解説にあるけどわからん(そのうち)
メモ
K固定はできたが,Kが可変だと解けなかった気がする.汎用性が高い問題なので覚えておきたい.
コード
yukicoder No.196 典型DP (1)
問題概要
N頂点の0を根とする木が与えられる. 木を白黒に塗る.
ある頂点が黒の時,その子が全て黒であるという制約を満たしながら塗る時,黒の数がKであるのは何通りか.
解法
dp[i][j] := (i頂点以下で黒がj個の場合の数)とする.
初期値は dp[i][0] = 1, dp[i][j] = 0 (j!=0)
遷移はiの子をi'として,dp[i][j] = sum_(k+l=j)(dp[i][k]*dp[i'][l])
毎回遷移で0<=k,l<=K としてしまうと計算量T(x)は
T(x+1) = T(x) + K2 より O(N3) となる.
しかしi'を取り込む前のiを除いたiの部分木のサイズx, i'の部分木のサイズをyとすると,
0<=k<=x,0<=l<=rだけ見ればよく, T(x+y) = T(x) + T(y) + xy でこれは T(x) = O(xy) = O(N2)となる.
よってDFSと同時に部分木のサイズを求めていき,その範囲だけkとlを動かせば良い.
dp[i][x] = 1となる点にも注意(iを黒に塗る場合はi以下も全て黒になり,これは1通り)
メモ
計算量落ちるのを知らなかったので解けなかった.
畳み込みっぽいしもしかして毎回FFTしても解けるかも?
