Hatena::Grouptopcoder

yehara のTopCoder日記

2012-06-08

SRM 545 Div1

12:27 | SRM 545 Div1 - yehara のTopCoder日記 を含むブックマーク はてなブックマーク - SRM 545 Div1 - yehara のTopCoder日記

143.42 + 261.17 + 0 + 50*0 - 25*0 = 404.59 (103位) Ratings 1876 -> 1947

すごく久しぶりだけど、なんか書いておくかな。問題自体の説明はやめて、どういう方針で実装したかのメモだけ。

Level One - StrIIRec (275)

12:27 |  Level One - StrIIRec (275) - yehara のTopCoder日記 を含むブックマーク はてなブックマーク -  Level One - StrIIRec (275) - yehara のTopCoder日記

問題がややこしいけど、まあ先頭から順に深さ優先で探索していくだけ。探索は辞書順で小さいものから。途中の段階で、この先最も辞書順で後になる形を仮定したときの inversion を計算することで、それ以上深く探索を進めて解がみつかるかを判定できるので、そこで枝刈りできる。実装は時間かかった・・・

Level Two - Spacetsk (500)

12:27 |  Level Two - Spacetsk (500) - yehara のTopCoder日記 を含むブックマーク はてなブックマーク -  Level Two - Spacetsk (500) - yehara のTopCoder日記

K=1 の場合は、格子点の数 (H+1) * (L+1) を返して終了。以下、K>1 のケース。

まず真上に飛ぶ場合を別に計算。出発点を固定したとしたら組み合わせ C(H+1, K) (C(a, b) はコンビネーション aCb のつもり)で、出発点が L+1 通り選べるので、C(H+1, K) * (L+1)。

斜めに飛ぶ場合は、出発点と、最終発信場所の相対位置関係毎に計算した。左右対称に考えられるので、右斜めに飛ぶ場合だけを考えて結果を2倍する。最終発信場所の相対位置は (K-1,K-1) 〜 (L, H) の 2 次元範囲を全探索。相対位置を (x, y) とすると GCD(x, y) + 1 が出発点から最終発信場所までに存在する格子点の数になるので、最終発信場所は常に発信するとして、残りの組み合わせは C(GCD(x, y), K-1)。これに出発点のとりかた L - x + 1 と、左右対称分の 2 を掛けて加算すれば OK。

まとめ

12:28 |  まとめ - yehara のTopCoder日記 を含むブックマーク はてなブックマーク -  まとめ - yehara のTopCoder日記

ひさしぶりに Medium ができて highest 更新。2000 が見えてきたか?

ゲスト



トラックバック - http://topcoder.g.hatena.ne.jp/yehara/20120608