2009-06-01から1ヶ月間の記事一覧
ICFPCが失格なので気分転換にSRMの過去問なぞ...。なのに実装問題とかいう悲しい状況...。 200 暗号化された文字列と曖昧ではない暗号化規則が与えられるので復元せよ、という問題。 単純に暗号化の辞書をなめるだけ。 500 ボードゲームをクリアするのに必要…
6/27の27時から三日間あったのに二人組で参加してました。で、簡単なメモだけ。眠いので適当にしか書かないけれど、多分書き直したりもしなさそう。 問題 物理シミュレータのバイナリコードが与えられるので、その上で衛星を操作してお題をこなしましょう。…
なんとなく解き方が分かったので色々。 300 N個の円があって、いずれも点を共有しない。指定された二点間を移動するとき、跨ぐ必要のある円弧の最小数を答えよ、という問題。 開始点と終了点で円の内外判定が異なるものは絶対跨ぐし、そうでないのは避けられ…
今日も今日とて0行進。で、今回も変則。 300 見てない。 600 0がA個1がB個ある状況で、K個フリップする操作を何回やれば全部1にできるか、という問題。 ちゃんと範囲制限しつつ、BFSすればよさげ?A->BならB->AでA->B->CならC->Aにならない。これはBFSなので…
変則セット。 250 AからBまでの数のうち、素因数分解したときの分解個数が素数個のものを答えよ、という問題。 分解して数えるだけ。 550 タイルが敷き詰められている領域の一部を切り出すことを考える。その部分に含まれる形状を再現するのに必要なタイルの…
古き良き時代のSRM...ってこともないか。 250 隣接要素のスワップがN回まで許可されている状況で、辞書順でもっとも大きい配列を作れ、という問題。 先頭から後ろN個以内で最大のものを先頭に持ってきて、移動した回数Nを減らす。先頭は固定して以下順番に繰…
俳句のような英語文字列が与えられるので、母音の数が575になっているかどうかを検証せよ、という問題。連続する母音は一つとみなす。 正規表現を使ったsplitの練習。aeiouyが母音と認定され得る文字なので、それ以外の文字が一つ以上ある場所でsplitすると…
各桁の数字が2^(i+1)-1の重みを持つものを10進数に変換せよ、という問題。 実装するだけ。
N個の数字が与えられるので、合計がSになるユニークな組み合わせを辞書順で表示せよ、という問題。 Nが高々12なので2^12通り試すだけ。辞書順になるようにするために、大きい数字を優先的に使うように適当にソートする。重複除去をするためには、ソート後にi…
カタツムリが一日に上る量が経過日数との一次関数で与えられ、夜に落ちる量が与えられる。超えないといけない壁の高さが与えられるので、超える最初の日、あるいは地面にめり込む最初の日を答えよ、という問題。 日数がさほど長くないので、逐次実行するだけ…