SRM 461 300pt: ColoringRectangle

問題概要

H*W(H,W<10^4)の長方形の板がある。赤い様々な直径の円盤をN(<50)枚、青いのをM枚持っている(直径<10^4)。最小何枚の円盤で板を被覆できるか求める問題。ただし、左から順に板を置いていき、同じ色の板が重なってはならない。

考えたこと

• (はじめて参加したDiv 1のSRM。Div 1ではじめて通したのはこの問題)
• 問題読むの2回目で問題の内容大体覚えてた。
• 円盤は大きいものからつかうのが最善な気がする。
• 赤からはじめるか青からはじめるかの2通りあるけど、両方シミュレーションしてやる。
• 同じような処理が出てきたので関数にして処理する。
• 計算でdoubleが出てくるけど流石にこれは避けようがない。
• 何か通らないと思っていたら1ヶ所等号間違えてたのと、半径と直径を勘違いしていた。
• 時間はかかったけど無事通った。当時と比べるとコードの内容もスコアも改善されていることが分かる。

SRM 461 500pt : BuildingCities

問題概要

2次元平面上にN(<50)個の街がある(0< x, y < 1000)。0からN-1までの経路を考える。経路の長さをmaxT(<10^5)以下、パス上の辺の最大値をmaxD(<10^5)以下になるように新しく街を設置したい。設置しなければならない街の数の最小値を求める問題。

考えたこと

• (当時は問題文読んだけど問題の意味が分からなかったような記憶がある)
• 方針がすぐには見えない。
• とりあえず到達不可能な判定は直接つないでみて大丈夫かどうかで判定できる。
• 置く数を固定して考えたら行ける？
• 新しく街を設置するときは2街間をつなぐ線分上に置くのが最適なはず。
• 置く数固定しても過去にいくつあったか覚えておいたりすると情報量多すぎる。
• というか、置く数の上限なんて高々2000*√2位なんだから意外と少ない。
• で、街の数にこれまで置いた数の状態を付与すると状態数(50*3000)くらい？
• あとはDijkstraするだけじゃん。
• 辺の数は、50なので全体でO(50^2 * 3000)？これにlogがつくと結構重いような気もする。
• 各頂点でfacetもって枝刈りする手段もあるけど、それは最後の手段にしたい。
  • 例えば各頂点でRMQ持つとかで実装できる。
• ということで普通に書く。とはいえ距離の計算などは結構重いのでそこは前処理をかけておく。
• 無事通った。結構実行時間長かったから、もうすこし賢いやり方があるのかも。
• 例えば簡単な枝刈りとして、距離がmaxTを越えたら打ちきるとか、答えの最小値を覚えて置いて設置回数がそれを越えたら打ちきるとか。