久しぶりに更新しました。お久しぶりです。
本当はもっと多い頻度でこのブログを使っていけるといいんだけど、どうもいいコンテンツがないのと、一度書き始めるとなんだかんだ長い時間かけてしまうので億劫だったのとですっかり放置してしまいました。
ブログが有効活用できる人は素晴らしいですよね。
私なんかTwitterも使い道が良くわかりません。
Topcoder SRM529に参加しました。３日ほど前のことですが。
こういう感じの記事を書くのは初めてですね。後、今回ソースコードを載せるにあたってSyntaxHighlighterを導入しました。いぇい。
あ、ソースコードは長いので追記の方に載せます。SyntaxHighlighterの設定をいじればどうにかなる気もしますが。
250 KingSort
王様の名前が与えられるから、それらを辞書順に並べよ ただし例えば "Louis XIII" は "Louis XIV"の前に来るように、名前が同じ場合は世代順に並べよ
というような問題。
うひゃー、面倒くさそうーと思いつつ、そして使い方のあやふやなstring.substr()についてググりつつコーディング。スペースの前後で区切って、後ろのローマ数字部分はintに直して、自前の構造体に入れてソートさせた。
これ色々血迷った結果30分ぐらいかかった気が。。。。
そして、Challengeで落とされました。。。IXの存在を忘れてたってのもあるけどなんか他にバグある気がする。ていうか全体的に私がグダグダすぎましたね。ってか構造体定義する必要もなくpair<string,int>で事足りたし。色々と反省の多い問題でした。
600 MinskyMystery
バッグが５つある。最初に全てのバッグを空にして、bag0にN個おはじきをいれた後以下の作業を行う。
Add a marble into bag 1.
Repeat forever:
Add a marble into bag 1.
Empty bag 4.
While there are marbles in bag 0:
While there are marbles both in bag 0 and in bag 1:
Remove a marble from bag 0.
Remove a marble from bag 1.
Add a marble into bag 2.
Add a marble into bag 3.
End While
Add a marble into bag 4.
If bags 0 and 1 are both empty:
Move all marbles from bag 3 to bag 4.
TERMINATE THE GAME
End If
Move all marbles from bag 3 to bag 1.
End While
Move all marbles from bag 2 to bag 0.
End Repeat
この作業が終わった時、何回おはじきを追加or箱間移動したか。
というような問題。
この意味あんのかよく分からんアルゴリズムに従って手を動かす感じ、センター試験を想起させましたね。時期も時期でしたし。あれ本番に「数値計算とコンピュータ」選んだはいいけど解答欄間違ってたんだよなあぁぁぁ
とりあえず7〜11行目をbag0->bag2、bag1->bag3の移動と考えて、じーっと上記のアルゴリズムを眺めていたら
・bag0はbag2としかやりとりしてない
・bag1はbag1としかやりとりしてない
・bag4が他のbagと絡むのは一番最後だけ
・End Repeatの時点でbag0のおはじきはN個にもどっている
・一番外側のEnd Whileの時点でbag1のおはじきはWhileに入る前の個数にもどっている
・一番外側のWhileに差し掛かった時点でbag0のおはじきの数がbag1のおはじきで割り切れる時そのターンで作業は終了する
等のことが順々に分かっていって、最終的に求めるべき値は
4N(km - 1) + km - N + Σ(k=2to km) ceil(N/k)
kmは1でないNの最小の約数、ceil(X)はXの切り上げ小数点以下切り上げ
であることまで突き止めた。
けれどもNの最大値が大きいので単純にΣ計算したΟ(N)では間に合わないからどーしよー となっているところでタイムアップ。
後から考えてみて、ceil(N/k)の値が等しいkの範囲が求まるから適当に掛け算を使っていけば計算量小さくなるなあということでやってみたら通った。
y=N/xのグラフ描いてみて適当に長方形を描いてみたら計算量はどうやらΟ(√N)になるっぽい。
900は600の解析中に途中で嫌気がさしてちょっと覗いたくらいでやってません。
結果チャレンジも一回ミスして全問不正解だったためレートがガクンと落ちて緑色になってしまいました。
続きを読む
