Hatena::Grouptopcoder

iwbtr - kmats このページをアンテナに追加 RSSフィード

2012-03-18

TopCoder SRM537 Div2 反省

| 04:11 | TopCoder SRM537 Div2 反省 - iwbtr - kmats を含むブックマーク はてなブックマーク - TopCoder SRM537 Div2 反省 - iwbtr - kmats TopCoder SRM537 Div2 反省 - iwbtr - kmats のブックマークコメント

Div. Place: 61/1365

Points: 652.84

Solved: oo-

Challenge: 1 succeeded

Rating: 916 -> 1050 (+134)

1回お休みした後の参加で多少不安ながらも良い感じに事が進んだ回.


537 Div2 250

与えられた条件にちゃんと沿うだけ.

が,ケアレスミスで落とされた人が割りといた印象.パス率70%ほどだった模様.


537 Div2 550

「(X, Y)の組み合わせで(A, B)の通貨制度に対応しろ」というのは,すなわち「XとYを用いてAとBを作れるようにしろ」ということ.XとYだけでAもBも作れれば,A*p + B*qも作れる=(X, Y)で(A, B)の通貨制度に対応していることになる.


XとYでAとBを作るにあたって,特殊な状況が2つある.

  1. 与えられたXだけでAとBを作れる(X==1を含む)
  2. Y==1であればYだけでAとBを作れる

1番の例)A=4, B=8であれば,A*p + B*q = 4(a*p+b*q)となり,(A, B)の通貨制度の元で付けられる値段は全て4の倍数になる.このとき,Xが1, 2, 4のいずれかであれば,Yがどのような値を取ろうとXのみで値段を表すことができる.この場合,-1を返さなくてはいけない.

よって,はじめにif (A % X == 0 && B % X == 0) return -1とする必要がある.


1番目のチェックを行った後は,Yを1<=Y<=max(A, B)の範囲で全探索する.上限はmax(A, B)としなくても,A, B, X <= 200であることから,Y <= 200としても計算量的に問題ない.

後は,0<= i, j <= 200程度の範囲でX*i + Y*j == A, X*i + Y*j == Bが成立すれば,その(X, Y)は代替貨幣制度として成り立つので,答えを+1する.

このとき,Y==1は必ず成り立つので,初めから答えを1にしておき,2 <= Y <= max(A, B)としても問題ない.


537 Div2 925

next_permutationを使って全探索すればいいじゃん,サンプルも通ったし・・といってそのまま出すとサイズ50の入力を突っ込まれてchallengeの餌食になる.next_permutation,すなわち順列がサイズnの配列(ベクトル)から生成する配列の数はn!個.50! = 3*10^64では当然TLEになってしまう.

他人のコードを見ただけだが,恐らく以下のようなことではないのかと・・


prerequisitesの要素は重複しないので,与えられたprerequisitesに対し,prerequisitesが-1のものを抜いたToastbookは,食べなくてはいけない順番が決まっていることになる.

視覚的な例としては,-1のToastbookをバラバラになった鎖一つ一つ,特定のprerequisitesが必要なToastbookをつながった鎖とすると,適当な長さの鎖列がいくつかと,その他バラバラの鎖,という状態ができあがる.

ooooooo ooo oooo oooooo oooo oo o o o o o o o o...

この鎖列は前から順番に辿らないと残りが無駄になってしまうのである.つまり,鎖にランダムにアクセスしたときに得られる鎖列の長さと,その確率を掛けた”得られる長さの期待値”が,鎖列一つ一つの部分解となる.

例えばlength=2の場合,ランダムに鎖にアクセスしたときに先に頭にアクセスし,次に尾にアクセスする確率は1/2である.

このとき,部分解は1*1/2 + 2*1/2 = 1.5となる.

length=3の場合,ランダムに鎖にアクセスし得るパターンは3!通りである.この内,3つ全てを得られるのは1/6,1しか得られないのは5/6となる.よって,部分解は3*1/6 + 1*5/6 = 4/3である.

length=1で列をなさない場合の部分解はもちろん1である.

すべての鎖・鎖列の部分解を求めたら,後はそれらの和を求めればreturnすべき解となる.

なお,鎖列の長さが同じ場合は,Toastbook一つ一つにどのような番号が振ってあっても同じ部分解となる.よって,部分解の導出ではメモ化が有効である.


反省点

  • 愚直にコードを組んで終わった(next_permutation)
  • challengeであまりコードを読まなかった

教訓

  • 問題の読み替えをすべし
  • 広くコードをチェックしてケアレスミスを見逃すべからず

ゲスト



トラックバック - http://topcoder.g.hatena.ne.jp/kmats/20120318