Hatena::Grouptopcoder

Gus@topcoder

topcoderのid:gusmachineの記録です。普段の日記は揺動散逸日記をどうぞ。
 | 

2011-05-09SRM 505

x opened opened: 0 pts.

半数が0点という恐ろしいsetでした。

1時間前

久々にSRMうけようと、macbook proでArenaを起動。したところpluginがmacbook proで動かないことが判明。慌ててdebianに移行。おそらくMacJavaの問題だと考えています。

300

長方形が不規則な長さの碁盤目に区切られている。区切られた部分長方形いくつかの面積が分かっている。あといくつ分かれば長方形全体の面積が求まるか。

ある4つの長方形 @ (x1, y1), (x1, y2), (x2, y2), (x2, y1) のうち、3箇所が分かっていれば残りはわかります。

規則性は判然としなかったので、とりあえずまだ分かっていないところを順番に調べればよいのではないかとあたりを付けて解きました。オーダーはO(格子の数^2)程度。結果xx分。ある場所の面積が判明したあとに、それによって新たに別の箇所の面積が判明するようなケースに気づかずちょっと手間取りました。最大入力で帰ってくることだけ確かめてsubmit。

しかしsystest failed。塗る順番をちゃんと考えないと行けないようでした。正解の方法は確認しましたがまだ本番のアルゴリズムの反例が理解できていません。

500

整数集合S = [A--B] + [C--D]のうち、Sに自分の倍数が含まれていないSの部分集合のサイズを求めよ。各変数は最大10 Billionまで伸びるので注意。

まずA--BのうちA--B自身に倍数を含むもの、C--Dのうち倍数を含むもの含まないものを求めておきます。そのあと、[A--B]のうち、[C--D]の中に倍数を含んでいないものを数えます。

[C--D]の約数は、, [C/4--D/4], [C/3--D/3], [C/2--D/2]といった分布をしています。ただし互いにoverlap擦る可能性はあります。まあとりあえずこの範囲を端から順に調べます。tsukunoさんとは逆に大きい方つまり分母の少ない方から探しました。

が、エラーでサンプルが合わずに時間切れ。1ずれていたので当時はどこかでoff-by-oneと思っていました。

あとでpracticeしてみたところ、C--Dの幅が狭いところでの処理が全く正しくないことが分かりました。それを訂正すると今度はTLE。具体的には[C--D]が狭く、ある数の倍数がその中に一つもないときに、そのままもう倍数ないよと探索を放棄していました。分母を増やして最挑戦するのが正解。

1000

与えられた整数集合を、和と積が等しくなるよう変形せよ。

見ただけ。

あとで、和と積とが等しくなるような集合のリストを手元で生成してみました。結果、サイズ50までにはバリエーションが多いので全列挙埋込みはあまりかしくこないかもしれないことを確認しました。いややり方はあると思いますが。