SRM477
インターン中は夜更かしなんてしてられないので、向こう2ヶ月はTopCoderはお預けかな。
なんて思っていたら、オフィス引越しのため2日間暇を出されたところに都合良くSRMが現れました。
250: Islands
- 六角座標。ものすごく面倒臭そうだ...。
- ...
- あれ？六角座標で隣接してるか調べるだけ？
- 簡単だ。適当に書いてsubmit.
- 隣接判定をちょっと typo してハマったのはご愛嬌。
500: PythTriplets
- 数列から (a^2 + b^2 = c^2 and gcd(a, b) == 1) であるような (a, b, c) を disjoint にいくつ取れるか、か。
- --絶賛問題勘違い中--
- なんかフローっぽいな。
- でも a, b, c と3つあると厄介だなぁ。2つなら簡単そうなんだけど...。
- ...あれ？ c の棒だけは材質違うみたいなストーリーがなかったっけ？あれはどう絡んでくるんだろう？
- (読み直し中)
- c は数列に無くてもいいのか。なら2部マッチングで大丈夫そう。
- ...って、どうやって2部グラフにするんだろ？
- sampleをもっかい見てみる。どのペアも偶数と奇数だ！
- 偶奇で2部に分けるとかダメかな。ダメだよな。
- いや、偶数同士でペアにしたら互いに素にならないじゃん。
- 偶奇で2部に分けるとかダメかな。ダメだよな。
- 実装！
- そういえば、最大流のライブラリどこにやったっけ？
- 最近無くしちゃったような気がしている。
- そもそも昨年の夏合宿以来最大流を使った覚えが無い。
- えーと。どうしよう。
- って、そもそも夏合宿にはこのPCを持ってったんだから、どっかに眠ってるはずだ。
- あれは初日のコンテスト終了間際に通したはず。タイムスタンプを見ながら探す。
- あった。やった。
- あれは初日のコンテスト終了間際に通したはず。タイムスタンプを見ながら探す。
- こぴ。ぺ。がりがりがりがり。
- あ、これ int だとオーバーフローするな。撃墜ケースっと。
- 書けた。
- って、あれ？本当に偶奇性で分けていいの？
- 偶数同士は gcd(a, b) == 2n なのでペアにできない。これはOK.
- 奇数同士は？ペアにしてもいいんじゃね？
- ...とりあえず1000ぐらいまで全探索して、(2n+1)^2 + (2m+1)^2 = c^2 => gcd(2n+1, 2m+1) != 1 を確かめてみましょう。
- そうなってた。ならきっと証明できるはず！
- 証明は後回しにしてとりあえず submit.
- あ、そうだ。オーバーフローの撃墜ケースも作らないと。
- 適当にペアを作れる大きな数を生成してみる。
- ...作れない。
- ...作れない。
- ...作れない。
- a^2 + b^2 が整数になるような (a, b) って 1,000,000 だと全然見つからないんだなぁ。
- 500,000 あたりで探してみる。いくつか見つかった。
- ちゃんと撃墜ケースになってることを確かめたあたりでCoding Phase終了。
Challenge Phase
- オーバーフローしそうな人を見つけるや否や突撃。
- +100.00
- 先を越された人が3人ぐらい。残念だけどまぁいいか。
- 時間はたっぷり余ってるけど、もう落とせそうに無いので終了。
System Test
- 500落ちた。残念。
- oxx +100.00 323.15
- 1277 -> 1390
