今週はvirtualはお休み(毎週お休みしそう)。
CFでレートを下げただけの週だった...。
出たコンテスト
KUPC2019 34位
CF#592(Div.2) 372位 2017->2008
CGR#5 2498位(????) 2008->1908
CF#593(Div.2) 335位 1908->1938
ABC143 23位
解いた問題
KUPC2019-D MaxMin Game
https://atcoder.jp/contests/kupc2019/tasks/kupc2019_d
i+1回目に勝ち負けが入れ替わったとする。このとき、i回目までに1以上2i以下のカードが全て手札から出ていることが必要。
よって、入れ替わるタイミングでは最初がどんな手札でも出ているカードの集合は同じなので、勝ち負けが変化しないようないくつかの区間に分割して考えられる。
そのような長さkの区間内で2人にカードを分配する通り数は、「最終的に|A|=|B|となり、常に|A|>=|B|を満たすように、前から集合A,Bに分配していく通り数」となる。これは実は、長さkの括弧列の数と同じである。これはカタラン数として知られており、C(2k,k)-C(2k,k-1)となる。
これを全ての区間について求め、掛け合わせれば答えが求まる。
KUPC2019-F カズマ王国の陥落
https://atcoder.jp/contests/kupc2019/tasks/kupc2019_f
各拠点から、ある1つの街だけに派遣するような最適解が存在することが示せる。
区間を右端でソートし、次のようなDPを考える:
dp(i,j):i番目の区間まで見て、今まで派遣した中で最も右にある街がjのときのダメージの最大値
右端が単調増加しているので、遷移元が狭まることがなく、このDPで最適解を求めることができる。
遷移にO(N)かかるように見えるが、累積maxを取っておくことでO(1)ででき、O(NM)でこの問題が解けた。
Mujin Programming Challenge 2017-B Row to Column
https://atcoder.jp/contests/mujin-pc-2017/tasks/mujin_pc_2017_b
明らかに、全てのマスが黒になるまでに初めてある1行が全て黒になる瞬間がある。これをi行目とし、iを決め打った時の全て黒になるまでの最小操作数を求める。
(i,j)が黒くなっていないとき、(k,i)が黒いようなkが存在するならば、(i,j)は1回で黒くできる。もしこれが存在しないなら、マス目上に1つでも黒いような(l,k)が存在すれば、最初に(l,k)->(k,i)と1回操作しておくことで、1回で(i,j)を黒くすることができる。これを全てのjについて考えれば最小操作数が求まる。
実は、これに「元から全て黒くなっていないような列の数」を足したものが答えとなる。明らかに、i行目を黒くする過程でそのような列数は増えることがない。また、実は減ることもないことが示せるので、これがiを決めた時の最適解となることがわかる。
これを全てのiについて計算するので、適当な前計算をすればO(N^2)で解ける。黒いマスが存在しないときは-1を出力すればよい。
天下一プログラマーコンテスト2016予選B-C 天下一プログラマーコンテスト1999
https://atcoder.jp/contests/tenka1-2016-qualb/tasks/tenka1_2016_qualB_c
本戦の順位によって人を並び替えておく。以下、ハシモトくんの記録上の勝ち負けを考える。
dp(i,j):i番目の人まで順位が一致していて、i番目の人がj回勝ったような確率 というDPを考える。
遷移は、dp(i,j)=sum{dp(i-1,k)}*f(i,j) のようになる。予選順位によってkの下限がjかj+1か決まる。f(i,j)は「i番目の人がj回勝つ確率」であり、これは各iについてO(N^2)で計算できる。dp(i,j)の遷移はO(N)でできるので、全体でO(N^3)で解けた。
ARC067-F Yakiniku Restaurants
https://atcoder.jp/contests/arc067/tasks/arc067_d
訪れる中で番号が最小の焼肉店をL、最大の焼肉店をRとおくと、LからRへ順に移動していくことで、移動距離の最小値を達成できる。よって、L,Rを決めれば、区間［L,R］における焼肉の美味しさの総和を最大化すればよくなる。
各チケットは、区間内で自由に使う場所を決められるので、区間内でもっともBの大きい場所で使えばよい。
Segtreeを使えばO(MlogN)で区間を決めた時の美味しさの総和の最大値がわかるが、全体でO(N^2MlogN)となってしまい間に合わない。
f(L,R):区間［L,R］における焼肉の美味しさの総和の最大値 というテーブルfを計算したい。
焼肉(i,j)が食べられるような区間［L,R］の条件を考える。全ての(i,j)についてこれが求まれば、f(L,R)にB(i,j)を足していくことで全てのf(L,R)が求まる。［L,R］でのチケットjで食べられる焼肉の中でのBの最大値がB(i,j)となればよい。
この条件は、「S<=L<=i,i<=R<=Tを満たす任意の［L,R］」という形になる。S,Tは、setを持ちながらBの小さい方から見ていくことで、各チケットごとにO(NlogN)、全体でO(MNlogN)で求められる。Bが等しいもの同士も、適当に順序付けすることでうまく処理できる。
後は条件を満たす［L,R］について、B(i,j)を足しこめばよい。
二次元平面上で考えると、長方形領域に値を加算していく形になっている。これは二次元imos法でO(NM+N^2)でできる。
これでf(L,R)が求まったので、この問題が解けた。
ABC143-F Distinct Numbers
https://atcoder.jp/contests/abc143/tasks/abc143_f
Ci:「Aj=iなるカードjの個数」とする。
X回操作すると仮定し、これが可能である条件を考える。問題は、次のように言い換えられる。
「X行K列のマス目に、数列Aの中から1つずつ数を書き込んでいく。同じ行に同じ数が入れてはいけない。マス目を全て埋められるか？」
明らかに、Ci>=Xなるiは、iで一列埋めてしまうのが最適。
後は、残っている列をCi
単調性より、後はXを二分探索すれば答えが求まる。
累積和などで必要な値を適当に前計算しておけば二分探索内の判定はO(1)でできるので、全体でO(NlogN)で解けた。
感想
学校の後のCodeforcesは必ず仮眠を取る！
