SRM485 の成績・ソース (要ログイン) : AC/AC/- : 機械化計画
500開く
- まじめに機械的に解けるかどうか検討しようと思って、エセ形式的に題意を書いてみることにしました。書いてみただけ。
- 入力
u : {B,W,?}^(h,w)
where 1≦h, w≦50
#{ b : {B,W,?}^(h,w) |
∀r c. b[r][c]∈(if u[r][c]=? then {B,W} else {u[r][c]}),
∀r1 r2 c1 c2. r1<r2 && c1<c2 => # b[{r1,r2}][{c1,c2}] = 2 }
- 『白と黒と？のマスがあるh×wの盤面があります。？を全部埋めて"長方形回避"にするやり方は何通り？"長方形回避"とは、同じ色の4マスを選んで軸平行な長方形を作れないこと』
- 直感でDP
- えーと、まず仮に左１列塗ったとして
- i行目とj行目が黒だったとしたら、以降の列でi,jを両方黒にはできない
- という制約を満たす塗り方をじわじわ右に
- 制約は白黒両方あるから 50*(50-1)/2*2 個で2500個くらいで
- えーと一列につき 2^2500 の状態があるDP
- はい無理
- そもそも一列塗る塗り方の時点で2^50通りあるし
- ううむ
- 長方形回避の話は二列二行が関わるわけだから、二列一度に考えるというのは
- 左端二列を、黒黒、黒白、白黒、白白、で塗る塗り方は4^50通り
- に見えるが、黒黒と白白は、それぞれ高々１回ずつしか使えない
- という制約がある
- だからなんだ…
- 結局それで塗ったとして、次の２列目３列目の塗り方、を数えるには２列目の状態から３列目の状態を数える漸化式になって、それは１列の総状態数だからさっきと変わってないなあ
- なんとか状態減らせないかな
- この"長方形回避"の条件って、列の並び替えや行の並び替えで変化しないよね
- 回避できてる塗り方の列を並び替えても回避できてるし、できてないのはできてない
- ということは、１列目塗る
- ソートして上半分白、下半分黒、とかに状態を正規化する
- みたいなことができたり
- すると状態は「白が何個」という一個の整数で記述できる。50通り！
- すごい減った！
- で、それをどう進めるかというと？
- 白に塗った上半分では、
- さっきの二列同時塗りのときと同じ考えで、以降、一列につき白は高々１つ
- 黒の下半分では、以降一列につき、黒は高々１つ
- というわけで、塗り方の候補はせいぜい50*50通りとかそれくらいに…
- あー、でも、元々塗られている部分があるんだよなあ。
- 全部？だったらソートしても塗ってない部分は不変だけど
- 元々の塗られ方がどこ行ったか追跡していると結局状態数減らないような気がしてきた…
- いやでもしかし、この
- ってことは、かなり塗り方の候補少ないわけで
- 実はあんまり広すぎると塗れないということはないか。
- 最初に●が三行あったとする
●
●
●
- 次の行オール○にすると三行目が塗れなくなる
- それ以外だと、一カ所だけ●、しかない
●○
●○
●●
- 次の行は？オール○…は、ない、右上に長方形できちゃう。
●○○
●○●
●●○
●○○●
●○●○
●●○○
- 要するに、左端の列に三個●があると、せいぜい４列までしか塗れない
- 当然三個○でも同じ
- ということは、５行あると確実に●か○は３個になるから、
- ５行５列以上あると塗り方は０通り！
- きたこれ。
- ５行５列以上なら即座にreturn 0;
- それ以外なら、必要なら転置して、縦幅は４行、としてよい
- これなら最初に考えたDP行くだろう。
- 禁止パターンは4*(4-1)/2*2だから12通りしかないので
- 一列あたりの状態は2^12通り
- 塗り方は2^4通り
- 最大50列
- 2^12 * 2^4 * 50 ステップ…は、300万、間に合う間に合う。
- ガリガリガリ…
- 書いた
- サンプル通った
- 行っちゃえ！
250開く
v : int^d
where 4≦d≦50
min { a:int^d |
∀i. ∃p. 1≦a[i]＝v[i]・2^p＜2^31,
∀i. a[i+1]-a[i]=a[1]-a[0] }
- 『positive signed intの範囲の等差数列があったんだけど、偶数が嫌いな人が偶数項を奇数になるまで2で割りまくっちゃいました。元の等差数列を復元してね。一意に定まらない場合は辞書順最小の物。』
- 全探索でいいんじゃないかな。
- 等差数列は、２個のパラメータで決まる。
- 初項 a[0] と公差 s
- あるいは初項 a[0] と次項 a[1]
- a[0]は入力v[0]の1倍2倍4倍…のどれかでintに収まると分かってるからせいぜい32通り
- a[1]も同様
- なので、32*32通り全部等差数列作ってみて、条件を満たすものだけ残して、最小のものを返せばOK
1000開く
- お、SRMには珍しく図形問題きた
- そしてformalに書くのしんどい…
- 『凸多角形Dと、それを囲む別の凸多角形Sがあります。Sの周上の１点をランダムに選びます。そこから、選んだ点から一番遠いS上の点まで線分を結びます。それがDと交わる確率は？』
- 確率というのは要するに、
- 上のやりかたで線を引いたらDと交わる区間の長さ / Sの周の長さ
- だな。
- Sの各辺ごとに、どっからどこまでがDと交わるか、なんとかして求める感じで。
- ええと、仮に周上の点pを固定したとしよう。
- 「一番遠い点」はどっかの頂点になる
- 辺の上だとすると、辺を左右どっちかに動けばもっと遠くなるので。
- てことは、頂点と頂点のあいだの垂直二等分線を引きまくると、直線を「こっからこっちはこの頂点よりこの頂点の方が遠い」ゾーンにせいぜい2500分割できるので、それを左から右に集計すると、「こっからここまではこの頂点が最も遠い」という区間分けができる。
- ええと、直線と直線の交点を求めるルーチンその他が必要…
- そのそれぞれの区間の中で、最遠頂点qまでの線分がDと交わる範囲を求めて、あとはその長さを足しまくれば…
- Dが凸多角形だから、交わらない→交わる→交わらない と変わるので三分探索かなにかでどうにかなりませんかね
- というルーチンが必要…
- あ、逆に、qから多角形Dを直線上に投影すると、交わる範囲がわかるので、それと今見てる区間の共通部分、の方が楽かも
- 多角形のprojectionは頂点を投影してその区間をとればいい
- ということはこれも実質、直線と直線の交点…
撃墜タイム
- 勘違いしていて１失敗 (-25)
- 250はなぜ4≦dなのだろう…と疑問に思ってたのですが
- 「a[0], a[2] と a[1], a[3] のどっちかは元の等差数列がそのまま残ってる」が成り立つのですね！
- どっちも2割りされてるとすると答えが全部偶数になって、それは辞書順最小解ではない
- なるほどなあ
感想
- と、今日人力で導出した解法は機械的に作れるだろうか。
- 250は
min { a:int^d |
∀i. ∃p. 1≦a[i]＝v[i]・2^p＜2^31,
∀i. a[i+1]-a[i]=a[1]-a[0] }
- これを本当素直にforループで書いただけの解法なので、どうにか
- 500は、大きすぎると解が0、という推論は…うーむ
