Hatena::Grouptopcoder

minus9dの記録

2012-04-15

コンテストのメモを書き忘れた長い間経ってしまった。メモを書いておかないと、後から自分の解答を参照したい時に不便なのでなるべくがんばって書きたい。

SRM 540 Div2

| 15:49 | SRM 540 Div2 - minus9dの記録 を含むブックマーク はてなブックマーク - SRM 540 Div2 - minus9dの記録

500でWA続出のため、自己最高のDiv2内20位。Room内では2位だったため賞金の$20は逃したけど、Rが一気に上がってDiv1に行けたのは嬉しかった。oo-。R1202(+160)。なおこの回、賞金付きのためにチートを行う者がいて、レーティングが反映されるのに時間がかかったようだ。 http://apps.topcoder.com/forums/?module=Thread&threadID=743435&start=0

250. RandomColoringDiv2

条件に合うRGBの組の数を数える。ブルートフォースが簡単で良い。Div2の250は、まずブルートフォースができないかどうか考えるのがよさそうだ。

http://community.topcoder.com/stat?c=problem_solution&rm=312582&rd=14732&pm=11872&cr=23027339

500. ImportantSequence

配列Bの要素が取りうる値の範囲が大きいのでブルートフォースは無理。配列Aの最初の要素の値a_0をxと置くと、a_1以下すべての要素の値をxを使って表せる。あとはa_0以下すべての要素が正の値であると不等式を立てて解くと、可能性のあるxの数が分かる。

http://apps.topcoder.com/forums/?module=Thread&threadID=743163&start=0 に親切な説明があった。

http://community.topcoder.com/stat?c=problem_solution&rm=312582&rd=14732&pm=11842&cr=23027339

2012 TCO Algorithm Round 1C

| 15:49 | 2012 TCO Algorithm Round 1C - minus9dの記録 を含むブックマーク はてなブックマーク - 2012 TCO Algorithm Round 1C - minus9dの記録

600位以内に入れたことと、Div1に留まれたことが嬉しかった。最近Eclipseプラグインを導入したおかげでテストが一瞬ででき、解答速度が向上している。oo-。R1262(+60)。

250. PasswordXGuessing

同じ桁数の、数字のみからなる文字列が複数与えられる。どの文字列とも数字が1個のみ異なるような文字列はいくつあるかを出力する。

与えられた文字列のうちの一つから、数字が1個のみ異なるような文字列の集合を、候補文字列として生成。あとはこの候補文字列の一つ一つについて、条件に合うかどうかを試せばよい。

http://community.topcoder.com/stat?c=problem_solution&rm=312643&rd=15092&pm=11867&cr=23027339

500. PasswordXGrid

格子状のグラフと、各エッジのコストが与えられる。格子の左上から右下まで、どのパスを通ってもそのコストの総和が同じ値になるようにコストを各エッジに加えることを考える。それが実現するときの、コストの総和の最小値を求める。

とりあえず、最初に与えられたグラフ上のパスのうち、コストの総和が最大となる場合を見つけ、その総和を得る。本当にこの総和が題意に合う値なのか証明できず自信がなかったが、結果的にはそれで合っていた。コストの総和の最大値を求めるコードが汚くなってしまった… よく考えると斜めにジグザグスキャンする必要はまったくなく、ラスタスキャンでよかった。

http://community.topcoder.com/stat?c=problem_solution&rm=312643&rd=15092&pm=11873&cr=23027339

Croc Champ 2012 - Round 1

| 15:02 | Croc Champ 2012 - Round 1 - minus9dの記録 を含むブックマーク はてなブックマーク - Croc Champ 2012 - Round 1 - minus9dの記録

Qualに参加していなかった人でもRatedとして参加できたので参加。ox---。R1586(-68)。

A. Rock-Paper-Scissors

AとBがじゃんけんで対戦。Aは周期m、Bは周期kで同じ手を出し続ける。n回じゃんけんしたときに、AとBとが負ける回数をそれぞれ出力する。

1回目からm*k回目までのAとBとの対戦結果を調べると、それ以降の対戦結果は計算しなくても分かることを利用すればよい。

http://codeforces.com/contest/173/submission/1481110

B. Chamber of Secrets

右下のbasilisk、左上の入り口、マス目中の柱それぞれをノードとみなし、同じ列、または同じ行にあるノード間にはコスト1のリンクを張る。あとは最短路を求めると、魔法をかけるべき柱が分かるはず。このように考えて実装したが、柱がたくさんあるときにメモリ制限に引っかかりシステムエラー。まだ復習できていない。

↓メモリ制限で落ちるコード

http://codeforces.com/contest/173/submission/1484247

Round #115

| 15:02 | Round #115 - minus9dの記録 を含むブックマーク はてなブックマーク - Round #115 - minus9dの記録

Div1とDiv2とで部屋は分かれていたけど、問題は同じだった回。また問題は6問。裏でGCJの予選があったせいかいつもより参加者が少なかった。ooo---。R1644(+58)。

A. Robot Bicorn Attack

数字から構成される文字列が与えられる。それを、点数の範囲が0から1000000になるように3分割。もっとも点数の合計が高くなる分割の仕方を探し、そのときの点数を出力する。

すべての分割の仕方を総当りで試す方針で解けた。文字列000のときに-1を返している人がいたので撃墜。

http://codeforces.com/contest/175/submission/1532399

B. Plane of Tanks: Pro

問題文が分かりにくくて合ってるか全然自信なかった。結果的には合っていたもののストレスのたまる問題だった。

http://codeforces.com/contest/175/submission/1534688

C. Geometry Horse

これもやたら問題文が分かりにくかった。値p_tよりもフィギュアの総数の方が大きい時の処理ができてなくて何度かpretestで落ちた。最終的に通ったものの見返す気にもならない酷いコード。

http://codeforces.com/contest/175/submission/1536793