Hatena::Grouptopcoder

TopCoder煮ブログ

本家ブログはこっち → http://d.hatena.ne.jp/nitoyon/

2008-10-26

KPlanetaryAlignment (SRM414 DIV1 Hard)

| 22:57 | KPlanetaryAlignment (SRM414 DIV1 Hard) - TopCoder煮ブログ を含むブックマーク はてなブックマーク - KPlanetaryAlignment (SRM414 DIV1 Hard) - TopCoder煮ブログ

難しそうだったので、とりあえず力技で解く。やはり入力の規模が大きくなると時間がかかりすぎるが、題材が面白かったこともあって勉強になった。


模範解答を探して結果を見たら解けた人は1人のみ。泥臭かったらどうしようと思ったがすごく綺麗なコード。惑星が k 個重なる組み合わせごとに、一直線になる周期を記録している。最後に、それぞれの組み合わせについて、数え上げていく。重複してカウントするのを防ぐために、k個同時を足して、k + 1個同時を引いて、k + 2個同時を足して、k + 3を引いて…としている。円がn個のベン図を考えると分かりよい。かっこいい。分子分母の情報が重要になるので、有理数クラスを作って表現しているところもポイント。

LavonLavon2011/07/08 02:06Gee whiz, and I tohught this would be hard to find out.

ezonlvzzezonlvzz2011/07/09 22:23JvdRbr , [url=http://nrkrnawayroz.com/]nrkrnawayroz[/url], [link=http://dahqqmnzaikt.com/]dahqqmnzaikt[/link], http://abtsyryszdck.com/

lsztkrmlsztkrm2011/07/11 01:06avBaTE <a href="http://jfonyhaisomt.com/">jfonyhaisomt</a>

dojczvlyoeydojczvlyoey2011/07/11 23:03iHNjn2 , [url=http://atbxicznuqng.com/]atbxicznuqng[/url], [link=http://jurrdqdadcrh.com/]jurrdqdadcrh[/link], http://sajjqxxxxowc.com/