2009-01-01から1年間の記事一覧
青デビュー。 250 ブラックジャックで、21以上になったらカードを取るのをやめるとするとき、今後取る枚数の期待値を答えよ、という問題。 再帰で解けばいいだけなんだけれど、適切にメモしておかないと間に合わなかったりするとかしないとか。 500 見てない…
昨日の話だけれど、結果出たので。 A 長さ固定の文字列データベースに対してクエリが与えられるので、マッチする件数を答える問題。 クエリのフォーマットをちょっと変換して正規表現でマッチさせるだけ。 B 二次元配列上のデータを与えられた規則でグループ…
なんかお金がもらえる可能性のあるヤツ。 250 チェスの馬で、移動できるマスのうち、次に移動できるマスが最小のものを選択するとき、何回移動できるか答えよ、という問題。 通れないマスと、一度通ったマスは通れない。 やるだけ。 500 見てない。 1000 NxN…
良く分からない謎のSRMのようなもの。 250 ある人から見て、友達関係が与えられるのでホップ数を計算しましょう、という問題。 BFSするだけだと思うけれど、文字列ベースなので面倒そう。 550 見てない。 1000 ロボットが壁をのぼる。壁にはつかめる場所がい…
ひよって逃げたら4つほどチャレンジが落ちてきたセット。あと一つ...。 250 各面の中心が緑で、角が赤で、それ以外が青の3x3x3のキューブが与えられる。初期位置が緑色のとき、進むか、左右に向きを変えるか、の命令列が与えられるので、最終的な位置を答え…
やめた方がいいんじゃないの? 275 N個の場所からのマンハッタン距離を考えるとき、K番目に近いものの最小値を求めよ、という問題。 座標が整数なので1/2刻みで全部調べればいいらしい。証明しないで使う気にはなれない...。 マンハッタン距離なので、各二点…
600 整数列を狭義単調増加になるように変形するときに、変形する値の量の最小値を求めよ、という問題に帰着。 狭義単調増加なのを広義単調増加にするために、i番目の要素からiだけ引いておく。後はDPで求める。i番目の要素を移動させるとき、移動する先は他…
250 1からNまでの点数の問題があり、それぞれで得点できたかどうかと総得点が与えられる。このとき問題番号と問題の点数の違いの最大値が最小になるものについて、その値を答えよ、という問題。 英語がだらだら書いてあるので実装するだけ。 600 整数列が与…
順調降下中。意外と落ちなかったので次もまだ黄色ラインかも。 250 三角形と四角形が適当に配置されている状況で、三角形を四角形に変換するという処理を行える回数が与えられる。このとき、三角形と四角形を組み合わせてできる最大の三角形の大きさを答えよ…
二部グラフマッチングだと信じていたのに...。 1000 ボルトの大きさが与えられる。大きさNのボルトには大きさNのナットが存在することが分かっているが、大きさN-1とN+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…
カタツムリが一日に上る量が経過日数との一次関数で与えられ、夜に落ちる量が与えられる。超えないといけない壁の高さが与えられるので、超える最初の日、あるいは地面にめり込む最初の日を答えよ、という問題。 日数がさほど長くないので、逐次実行するだけ…
0点連続中。 250 N個の数字からなるPermutationが与えられるので、それと一番差分が少ないPermutationのうち、Permutationを導出可能なものとの差分の数を答えよ、という問題。導出については式が与えられる。 良くある問題らしいが、初出なので全く分からな…
正整数が複数個重複なく与えられるので、他の要素のうちどれかの二倍になっている要素はいくつあるか答えよ、という問題。 なんとなくプログラム書いてみました、という感じ。上限値が99とのことなので、大きさ100のテーブルを持っておいた。
8角形の板が複数個与えられる。各辺には色が塗られている。好きな順番に好きな角度回転させて一列に並べるとき、隣接する辺は同じ色でなくてはならない。また隣接は循環する。各色に点数が与えられているとき、隣接する辺に塗られている点数の合計値のうち最…
右か下にしか移動できないロボットが左上に複数台配置されている。ゴミの置かれた位置が複数個与えられるので、すべてのゴミを回収するのに必要なロボットの最小数を答えよ、という問題。 右にゴミがある限り右に移動し、なくなったら下に移動する、というgr…
N人の名前と、所持しているものの量が与えられる。最初は全員均等な量を持っていて、一人が別の一人から少し奪った後の状況が与えられているとするとき、誰が誰から取ったか答えよ、という問題。 単に持っている量の最大値と最小値の人の名前を探すだけ。
基数がAの数を基数がBに変換して答えよ、という問題。ただし文字数が7文字を超過したらERRORと答える。 BigIntegerを使えば一瞬。
a^3=b^3+c^3+d^3かつ1
中学生からやり直せ、といわれた感じ。二次方程式が解けなかった。 250 下方向の速度だけ保存する状況で坂を下るボールがある。(なぜか横方向は適当な速度が常に得られる。)坂を下り切るまでの時間と坂の形状が与えられるので、重力加速度を求めよ、という問…
やるべきことはやって、全然ダメだっただけ。すっきりした。 250 N個の1リットルの水の入った容器が与えられる。同じ容量の容器二つは任意にマージすることができるとするとき、K個以下にマージするにはいくつ1リットルの水の入った容器を追加する必要がある…
頭の悪さが良く分かった。何回目か、という問題はさておき。レートの適正化が進んでいくのはいい傾向。 300 [A,B]なる区間について考えるとき、含んではいけない数の集合が与えられる。このとき、各整数について、自分を含む区間の数が少ない順にソートせよ…