来週のGCJ Round 1

火曜までに日時を決めなきゃいかんので、まあ適当に。朝10時とか起きれない可能性もあるけれど。
まだそんなに苦しい戦いにはならないと思うけど、自分の能力がいろいろ落ちていることを実感するQualification Roundだったことを考えると、恐ろしい。
ということで問題ごとの雑感。Aに関してはGreedyでおｋ、とすぐ気付いた。とはいえ、問題の意味を読み取るのにちょっと苦労。まあ、スライム問題の倒し方に関する直観は衰えていない気はしたが、最近C90ばっかり書いていることもあって、forの中でindexの変数宣言をするのを忘れることが多々。後、Serach Engineにspaceが入っているという仕様により、ScannerのnextLineを呼ぶところでごちゃごちゃと。すぐに気づけるとはいえ、こういうところが今後の命取りになるかも。
問題BもSortするだけなんだけども、ひさびさにimplements Comparableとか書いたわけで、順序を逆にしていて失敗。後はoutput formatで2回もErrorを。直観と解き方自体は決して間違ってないものの、こういうはまり方は良くない。今後修正せねば。
問題Cは大失敗。最初、外側の枠を除外した状態で通りぬけない確率をDirectに計算しようとしてダメ。これを計算するには、横のガットと縦のガットに当たる確率をそれぞれ計算して、両方に当たる確率を引けばいいわけだけど、両方に当たる確率の計算がほぼ不可能。角の丸い正方形と円の共通部分とか無理無理無理。次はメッシュに切って計算始めたけれども、id:tanakhさんが指摘しているように細いガットがたくさんあるとダメ。うまくいかない。4桁くらいまでは合うんだけど。これを考えると、モンテカルロも無理そうだというのがすぐわかる。で、ふつうに通りぬけない確率を考えれば図形がシンプルになることに気づいて終了。
問題セットとしては、意外と難しかった、くらいか。Qualificationというくらいだから、もう一段階くらい優しい問題になるかと思ってたけども、A, Bでさえ誰でも解ける問題じゃなかった気がする。これが解けなきゃ話にならないというのは事実だと思うけど。