読者です 読者をやめる 読者になる 読者になる

pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

CodeChef September Challenge 2016

Chef and digits of a number

(0の数)=1 または (1の数)=1 なら OK。

Faded Palindromes

どこにでもありそうな問題。両方 '.' のときがコーナーケースだと思うけど、サンプルにあるので問題ない。

Chef and calculation

得点が 1,2,4 な時点で貪欲っぽい。6 種類を選び続ける→5 種類を選び続ける→4種類を選び続けるが最適方法になるだろう。

実際、4 種類 の選び方はすべて同じでないと最適にならない。111100 と 111010 という異なる取り方をしていた場合、これを 111110 に置き換えた方が無駄がない。 5種類のときも同様。なので貪欲にいける。

Chef and Friends

辺 (u,v) がなければ u と v は別のテーブルになるはず。ということは補グラフが二部グラフでなければ解は存在しない。

二部グラフなら実際に解が作れるので、補グラフの二部グラフ判定を行えばいい。n≦103 かつ Σn≦104 なので O(n2) でも通る。

Dividing Machine

各要素がもつ素数の個数はたかだか log(a[i]) 個しかない。そのため素数の削除は O(n log a) 回しか起きない。なので普通に削除して RMQ で最大値を求めればいい。

L..R を工夫しないで走査すると O(NQ) になってしまう。素数が残っている位置を set に入れておいて無駄なく走査できるようにしよう。

JosephLand

ちょっと誤読しそうになったポイント。

  • チケットを使いきるまで新しいチケットは買えない。
  • 1 移動するのにチケット 1 消費ではなく何回分でも消費できる(つまり 1..K[i] 上に移動できる)。

DFS しながら RMQ をいい感じに更新する DP。DFS で降りる前に RMQ[depth v]=dp[v] としておけばいい。

最初 HL 分解してほげってました…。

The New Restaurant

半径が小さいのがポイント。走査線を左から右に動かしたとき、円が走査線と交わっている時間は高々 100 である。つまり走査線を止める毎に交差している全ての円を調べても O(100N) になる。

平面走査で求めるのは下図の領域の面積。

f:id:pekempey:20160907173523p:plain

これが分かれば二次元累積和の要領で面積が計算できる。

片方の走査線だけに交わっている円とどちらも交わっていない円は配列と BIT で計算できて、両方交わっている円は真面目に全部計算する。両方に交わっている円はそんなに多くならないと思うので、おそらく計算量は問題ない。

面倒なのが円と矩形の交差領域の面積。$\int \sqrt{r^2-x^2} dx$ が分かると嬉しい。置換積分でも解けるけど普通に幾何でも解けて次のようになる(wolfram alphaに投げても出てくるけど)。

f:id:pekempey:20160907172107p:plain

sqrt とか asin とかは重いのでキャッシュすると良い。

Chef and Cut

探してたら良さ気な pdf があったので参考にしました。near min になってるけど少し変えれば k-best にも使えます。内容をよく理解してないのでこの解説は嘘だと思って構いません。

http://calhoun.nps.edu/bitstream/handle/10945/38418/BalciogluWoodWeb03.pdf?sequence=1

2 番目の最適解は、1番目の最適解 S をまず求めて e∈S を使用を禁止にして再度最適解を求めるという常套手段がある。k 番目の最適解も同様の考え方で求められる。

禁止制約を追加する毎に最小カットは単調増加するはずなので priority queue で順に処理できる。

ところで pdf に書いてあるのは禁止制約に加えて使用制約もつけるらしい。多分いいことがあると思うので付けておく。

e=(u,v) の使用を強制するには u と v が違うグループに含まれるようにすればいいので、(s,u)と(v,t)の容量を∞にすればいい。

e=(u,v) の使用を禁止するには u と v が同じグループに含まれるようにすればいいので、(u,v)の容量を∞にすればいい。

この方法だと漏れ無く重複なく取り出せるみたい。

Chef has a Spaghetti Garden(解けず)

求められそうで求められない。editorial を待つのみ(そういえば前回の cheflong の editorial はもう出ないんですか…)。

push relabel 系のフローって実際速くなるのかな。今回みたいに大量に流す解法を取るとフローの速度が気になる。