Hatena::Grouptopcoder

解いた問題

TopCoder: OgieKako / Codeforces: OgieKako

|

2012-12-14

計算量の異なる解法を組み合わせる問題について

23:19

これは,Competitive Programming Advent Calendar Div2012 の15日目の記事です.

はじめに

この記事では,自分の好きなタイプの問題について書きます.

実は,自分の知る限り,このタイプに当てはまる問題は2例しかしりません.

詳しい人が,他の作例を教えてくれないかなー,とか,作例が増えてほしいなーという思いを込めてこの記事を書きました.

当然ですが,問題が紹介され,その解法が書いてあります.

計算量の異なる解法を組み合わせる問題とは

自分がここで意図しているタイプの問題は次のようなものです.

  • 問題の入力には,そこから定まる値 p がある.
  • 問題を正しく解くアルゴリズム A, B が存在して,その計算量はそれぞれ p の増加関数,減少関数になっている.A,Bどちらも単独ではTLEする
  • pが小さい時にはA, 大きい時にはB を使うことによって,TLEしない解答を作れる

よくある場合分け解法と異なるのは,A,Bともにpがどんな値であっても正しいアルゴリズムではある,という点です.

場合分け問題でよくあるのは,例えばpが5以上だったら,常に 0 を返し(A),それ未満だったらDPする(B),みたいなものですが,この場合,pが5未満の時に A を使うと,TLEではなく WAになります.

(cf.SRM485 RectangleAvoidingColoring)

作例

はじめに書いたように,2つしか作例を知りません.

両方とも公式解説が詳しいので,詳細はそれを見て下さい.

TCO2010 wildcard 1000 : ShrooksOnTheBoard

http://apps.topcoder.com/wiki/display/tc/TCO'10+Wildcard+Round

左右にKマス動けるコマ(shrook)を,H*W のボードに,互いに取りがかからないように置く方法は何通りあるか.mod 100003 で.
K,H,W ≦ 10^9 

列について計算して,あとで H 乗すればよいので,H = 1 として良いです.

  • p = K
  • A: 漸化式つくって,K*K の行列累乗で解く
  • B: コマの置かれる個数 ≦ W/K+1 に対し Lucasの定理を用い,O(1)で組み合わせ計算

両者の計算量は,

A : O(K^3log W) (行列の特性多項式を使って高速化するともっと良い), B : O(W/K)

となって,K≦130 くらいで使い分けると,すべてのデータに通ります.

GCJ2011 R3 D : Mystery Square

http://code.google.com/codejam/contest/1158485/dashboard#s=a&a=3

平方数 N = n^2 を2進数表記したものの,いくつかが '?' で置き換わった文字列 S が与えられる.復元せよ.復元は一意に可能であることが保証されている.
|S| ≦ 125, Q = '?'の数 ≦ 40, S[0] = '1'

n の最下位ビットの位置はすべて試すことにして,n は奇数であると仮定します.

  • p = |S| の前半にある'?'の数
  • A : 前半を決めうちすると,n の候補は一意に定まる
  • B : 後半を決め打ちし,n を 4 で割った余りを決め打ち(1 or 3)すると,n の候補は,下から一意に決めていける.

両者の計算量は

A : O(2^q|S|), B : O(2^{Q-q}|S|) となって,q≦Q/2 で使い分けると,全体で

 O(2^{Q/2}|S|^2) の解法となります.枝刈りされて定数が小さいのと,制限時間が長いので,これで通ります.

おわりに

このような問題の作例が少ないのは,やっぱり作りにくいからなんでしょうが,

ひとつの問題に対して,計算量にトレードオフがある複数のアルゴリズムがあること自体は,そんなに珍しいことではありません.

例えば,ナップサック問題であれば,荷物の個数が多く,容量制約が小さいとDP,個数が少なく,容量制約が大きいと,半分全列挙で解くことができますが,両者を交換はできません.

また,nCr mod mの求め方には,さまざまなパラメータでの,nCr mod m の効率的な求め方が紹介されています.

問題をつくるときに難しいのは,おそらく,これらをいかに自然な制約条件で使い分けさせるか,という点なんでしょうね.


あと,上記でみたのは,2つのアルゴリズムの使い分けだったけど,複数のパラメータp,qを組み合わせて,

Aはpが小さいと得意,Bはpが大きくqが小さいと得意,Cはpが大きくqが大きいと得意,みたいにすれば,3つ以上のアルゴリズムを使い分けさせることも可能かもしれませんが,妄想かもしれません.

2012-10-19

SRM558 Hard

03:40

問題

wataさんの出題.

グリッドグラフ があって,頂点v に石を置くコストが a_v.

石が置かれているか,まわりが石ばかりのとき,b_v もらえる.

得点を最大化せよ.

解法

  • 石を置く ⇔ x_v = 1
  • 石をおかず,dominated ⇔ y_v = 1

とする.

問題は,

 \rm{maximize} \sum(b_v-a_v)x_v + \sum b_vy_v

s.t.

 x_v+y_v\leq 1

 y_v \leq x_u  (\forall (u,v) \in E)

と表される.

上の制約は,石が置かれ,かつ置かれないことはないことを表している.下の制約は,dominatedならば,まわりに石が置かれていることを表す.

このままだと,上の制約があるから最小カットではないが,

二部グラフであることを利用して,

 x_v' = \begin{cases}    x_v & (v\in V_0) \\ 1-x_v & (v\in V_1)  \end{cases},  y_v' = \begin{cases}    1-y_v & (v\in V_0) \\ y_v & (v\in V_1)  \end{cases}

と置き直してやることで,すべての制約式を

 x \leq y

の形にできる.よって,最小カットで解ける.


思いつき方(?)

一つの制約式に3つ以上共有変数が入ると絶望的なので,

なんとか2つ以下しか入らないような定式化を考えた.

そうすると, x+y が入ってしまってダメかと思ったが,二部グラフなので大丈夫だった.

2012-06-26

高度合成数

12:09

n桁の数の,約数の数の最大 : http://oeis.org/A066150/list

それを実現する数 : http://oeis.org/A066151/list

2012-06-23

TCO12 R3A

03:47

コーナーケース!!!!!

250

補グラフを考えると,すべて次数が2以下であるようなグラフの,最小彩色数を求めよ.

最初になんか,頂点0に接続してるのは全部違う色で塗らないといけない! と勘違いしてコードを書き時間を無駄にした.

どうせそこまで瞬発力勝負にはならないんだから,落ち着け

補グラフの連結成分ごとに考えて良い.それはパスか,サイクル.

頂点数4以上だったら,2個ごとに塗るのがよい.

三角形がコーナーケースで,この場合のみ全部同じ色で塗れる.

一般の場合で考えてしまうけど,小さい場合で成り立たないことがある.「十分に大きい場合」を考えていることを意識して,十分とは実際なんなのかチェック.

500

ケーキ分割して,キャンドルと,3つのパスにわけるやつ

座標圧縮してフロー.

問題は,どこまでマージンを残すか.

3残せば十分なことはわかりつつ,グラフが大きくなりすぎる気がして

でも,グラフの枝数は,頂点数の2乗じゃなくて,定数倍じゃん,グリッドだから.

1しか残さなかったから,壁ぎわを3つ這うようなやつで落ちた.

2012-06-12

SRM542 1000

18:01

うさぎで,minCutつかうやつ

r以上にできるか? として,式変形して最小化問題にして,

minCutでとける,と信じてグラフを作る.

|