March Challenge 2013, TCO 2013, Codeforces #172
いくつかコンテストに出たので記録しておきます。
March Challenge 2013
http://www.codechef.com/MARCH13
CodeChefのLong Contest。
Approximately
103993/33102の値を求める問題。
小数点以下100万桁まで求めるので、実際に筆算をシミュレートする。もしかしてJavaのBigDecimalクラスでいけるか？？とやってみたけどさすがに無理でした。
Fire Escape Routes
人数Nと友人関係が与えられたとき、友人関係のある人間をグループにする。また、グループで一人リーダーを決めるとき、グループ数とリーダーの決め方が何通りあるかを求める問題。
やるだけ・・・だけど実装が微妙に難しい。
グループ化はUnion-Find木(http://ja.wikipedia.org/wiki/%E7%B4%A0%E9%9B%86%E5%90%88%E3%83%87%E3%83%BC%E3%82%BF%E6%A7%8B%E9%80%A0)とか使うといいって聞いたことがあるけど、実装できないので配列で作成。
それぞれの人について友人関係を持っておき、それらを同じグループにする。さらに友人の友人も再帰的に同じグループにしていく。
http://www.codechef.com/viewsolution/1883111
解けたのは前回と同じ3問でした。Random decreasing functionはEditorialが出たら解いてみたい。
Long Contest Rating 1784 -> 2113
TCO13 Round 1C
http://community.topcoder.com/stat?c=round_overview&rd=15585
TopCoder Open Round 1Cに参加。登録が早い人から2000人出れて、600位以内の人が次のラウンドに進めます。コンテストの形式はSRMと同じで、Twitterで聞いた話だと、難易度はDiv2以上Div1らしいです。
僕はRoom56。Div1もDiv2もごちゃまぜになってて、レッドコーダーとかいてビビってました。
The Array
隣の要素が最大dだけ離れている長さnの配列と始めの要素と終わりの要素が与えられる。考えられる中で配列内の最大の要素を求める。
Easyなのにむずい・・・とか思いつつ考察。各要素は配列の始めからも終わりからも到達出来る大きさであるはずなので、それらのminをとる。
http://community.topcoder.com/stat?c=problem_solution&rm=316581&rd=15585&pm=12455&cr=23103815
TheOlympiadInInformatics
N個の部屋がある。それぞれの部屋には何人かの人がおり、部屋内の人の合計点が与えられる。整数kが与えられたとき、最低何点あれば自分より大きいスコアを持つ人をk人以下に抑えられるか。
残り30分くらいで解法を思いつく。二分探索で最低点を求めれば良い。実装は難しいかもしれないけど、発想はEasyより簡単？？
http://community.topcoder.com/stat?c=problem_solution&rd=15585&rm=316581&cr=23103815&pm=12456
2問解けて終了時の順位は424.73Ptで850位くらい。Challenging Phase終了後に750位くらいになり、まー600位以内は無理かーと思っていましたが、System Test後に476位まで上がりました。実力以上のものが出たおかげでRound1突破。下がり続けていたレーティングも久々にアップ。
Rating 1024 -> 1121
Codeforces #172 Div2
B. Nearest Fraction
整数n, x, yが与えられる。以下の問題を解く。
min
| (x / y) - (a / b) |
subject to
a, b (1 ≤ b ≤ n; 0 ≤ a)
Bなのに難しい問題（終了後に解けていたのが300人ちょっとだった。CodeforcesのBはたまに鬼畜になる気がする・・・）。
n <= 100000なので全部を調べるのは無理そう。でもO(1)で出すのも無理そう。
bを固定したとき、|(x / y) - (a / b)|を最小にするaはx*b / yの近くにあるはず。bを1からnまで動かしてa = x*b / y (+- 1)を調べて、|(x / y) - (a / b)|を最小にするa, bを求める。実装にすごい苦労した。
http://codeforces.com/contest/281/submission/3280960
Cは三角関数の計算をし、とりあえず実装してみたけどサンプル合わず。
落ちるかなと思ったBが落ちず、スコア1210でなんと223位という今までの最高順位でした。しかもRoom内2位。もう10点でRoom内1位だった。惜しい！
Rating 1474 -> 1611
今までの最高レーティング1500を大きく更新。色が緑から青くなりました。緑落ちしないように頑張りたい。
