Hatena::Grouptopcoder

minus9dの記録

2012-03-17

Round #112 (Div. 2)

| 20:57 | Round #112 (Div. 2) - minus9dの記録 を含むブックマーク はてなブックマーク - Round #112 (Div. 2) - minus9dの記録

型のオーバーフローに泣かされて2問落とした悲惨な回。ox---。R1625→R1523(-102)。

A. Supercentral Point

条件に合う座標の数を注意深く数えるだけ。

B. Burning Midnight Oil

高校数学で習う数列の極限で、r < 1のとき、a + ar + ar^2 + ... の和はa / (1 - r)という公式がある。この公式を使って

n = v / ( 1 - 1/k )

をvについて解くと、vがとりえる可能性のある最小の値が出てくる。あとはvが問題文の条件に合うようになるまで、vの値を1ずつ増やしながらシミュレーションすればよい。

…のだが、このシミュレーションするところで、kの値が例えば9のとき、k^10がint型ではオーバーフローするのに気づいていなかった。よってシミュレーションに失敗、システムテストでWA

オーバーフローしないよう修正したソースは以下。

http://codeforces.com/contest/165/submission/1371293

C. Another Problem on Strings

分割統治で解くことにした。文字列Sに対して条件を満たす部分文字列の数をf(S)とおくとする。文字列Sを前半部S1と後半部S2に分けるとき、

f(S) = f(S1) + f(S2) + (S1とS2にまたがって条件を満たす部分文字列の数)

となると考えられる。

…のだが、またまたここでオーバーフローが。aをlong long 型の変数、b, cをint型の変数として、b = c = 50000のとき、

 a = b * c

でオーバーフローすることに気づいていなかった。正しくは

 a = (long long)b * c

とでもするべきだった。これが原因でpretest 11が通らず。誤りはこの場所のみで、他は正しかっただけに残念。

後で解き直したコードは以下。

http://codeforces.com/contest/165/submission/1371024

こういう間違いを2つも犯してしまうと、標準で多倍長整数が扱える動的言語に逃げたくなる。

SMR 529 Div2

| 20:57 | SMR 529 Div2 - minus9dの記録 を含むブックマーク はてなブックマーク - SMR 529 Div2 - minus9dの記録

初めてEclipseで参加。EclipseはVisual Stuidioとは違い、ビルドしても自動的にソースが保存されないことにずっと気づかずにはまり、Eclipseを諦めて通常のArenaを開くもなぜかMac版Arenaにはソースをペーストできないのに憤慨し、急いでWin機に環境を移動するはめになり…、結局Arena上で手打ち。250の点数が恐ろしく低くなってしまった。550は割りとすぐ解けたので何とか格好がついた。

oo-。R1129→R1168。

250 KingXNewBaby

コードはちょっと汚いけど問題自体はすぐ解けた。間違ってる人が意外といたが撃墜できず残念。

ソースは以下。

http://community.topcoder.com/stat?c=problem_solution&rm=312097&rd=14730&pm=11823&cr=23027339

550 KingXNewCurrency

XとYを使ってAとBの両方を作り出せることが必要十分条件。XだけでAとBの両方を作り出せる場合はYはどんな数字でもとりうるので、-1を返す。その他の場合は、Yを1から200まで変化させながら、条件を満たすYの数を数えればいいだけ。

ソースは以下。

http://community.topcoder.com/stat?c=problem_solution&rd=14730&rm=312097&cr=23027339&pm=11817


Round #112 (Div. 2)

| 20:39 | Round #112 (Div. 2) - minus9dの記録 を含むブックマーク はてなブックマーク - Round #112 (Div. 2) - minus9dの記録

型のオーバーフローに泣かされた回。ox---。R1625→R1523(-102)。

A. Supercentral Point

条件に合う座標の数を注意深く数えるだけ。

B. Burning Midnight Oil

高校数学で習う数列の極限で、r < 1のとき、a + ar + ar^2 + ... の和はa / (1 - r)という公式がある。この公式を使って

n = v / ( 1 - 1/k )

をvについて解くと、vがとりえる可能性のある最小の値が出てくる。あとはvが問題文の条件に合うようになるまで、vの値を1ずつ増やしながらシミュレーションすればよい。

…のだが、このシミュレーションするところで、kの値が例えば9のとき、k^10がin型ではオーバーフローするのに気づいていなかった。よってシミュレーションに失敗、システムテストでWA

オーバーフローしないよう修正したソースは以下。

http://codeforces.com/contest/165/submission/1371293

C - Another Problem on Strings

分割統治で解くことにした。文字列Sに対して条件を満たす部分文字列の数をf(S)とおく。文字列Sを前半部S1と後半部S2に分けるとき、

f(S) = f(S1) + f(S2) + (S1とS2にまたがって条件を満たす部分文字列の数)

となると考えられる。

…のだが、またまたここでオーバーフローが。aをlong long 型の変数、b, cをint型の変数として、b = c = 50000のとき、

 a = b * c

でオーバーフローすることに気づいていなかった。正しくは

 a = (long long)b * c

とでもするべきだった。これが原因でpretest 11が通らず。方針は正しかっただけに残念。

後で解き直したコードは以下。

http://codeforces.com/contest/165/submission/1371024

こういう間違いを2つも犯してしまうと、標準で多倍長整数が扱える動的言語に逃げたくなる。