2010-09-01から1ヶ月間の記事一覧
3228 Gold Transportation ある国にはいくつかの町があり、それぞれ金鉱と倉庫がある。金鉱でとれる金の量と、倉庫の容量は決まっている。金を輸送する必要があるが、輸送には道路を使う。道路はある長さを持ち、2つの町を双方向につなぐ。ドライバーが疲れ…
意味不明な問題セット←罠。 250 与えられた小数に最も近い分数を求めよ。分数の分子は上限が指定されている。「最も近い」とは、与えられた小数と、その分数を小数表記したものが、上の位からみてできるだけたくさん一致するようなものをいう。やるだけ。通…
1791 Paper Cutting 名刺を紙に印刷する。名刺を切り出すのに何回切断作業が必要か?やるだけ 1228 Grandpa's Estate 凸多角形状の農地があって、周上に杭が打ってあり、そこにロープがかけられていた。ある日、ロープが外されて、杭もいくつかなくなってい…
2082 Terrible Sets 数式だらけだから問題文見たほうが早い。このままだと意味不明なので図示すると、一辺がX軸に重なり、互いに重なり合わない長方形がたくさん並んだ形になっている。Sの意味は、「その中で辺が軸に平行な最大の長方形の面積」。すると、25…
PKUがfatal error。またディスク容量がなくなったらしい
1848 Tree 木に何本か辺を加えて、すべての頂点がちょうど1つのサイクルに属するようにするには最低何本加える必要があるか、という問題。この問題は、サイクルなどは関係なく、「木を、共通の頂点を持たない長さ2以上のいくつかの鎖に分割する」問題と考え…
1041 John's trip 非常に簡略化して言うと、辺の番号を通る順番に並べたとき辞書順に最小になるオイラー閉路を求めよ、という問題。オイラー閉路が存在することと「各頂点から出る辺の数が偶数で、すべての頂点が連結である」ことは同値である。まず、これで…
ところでパソコン甲子園は無事通りました。 250 最初は「1番目から1個飛ばしに」、次は「1番目から2個飛ばしに」、…というように数字を除去していく。最後に残るのは何?listを構築して(int配列で十分)やるだけ。 500 ハノイの塔で遊んでいる人がいる。一人…
2241 The Tower of Babylon 直方体のブロックを積み上げて塔を作りたい。あるブロックを他のブロックの上に積み上げるときは、そのブロックの底面の辺の長さはそれぞれ下のブロックの底面の辺の長さ未満でないといけない。(同じブロックを大量に積んだりは…
3010 The Genome Database of All Space Life 規則によって圧縮された文字列が与えられるからその文字列のi文字目を求めよ、という問題。圧縮文字列を木構造にして木を適当にたどるだけ 3469 Dual Core CPU デュアルコアCPUがあって、それにN個の処理をさせ…
1631 Bridging signals 左のP点と右のP点を結ぶケーブルがスパゲッティしてる。互いに交わらないようにできるだけたくさん選べ、という問題。最初「DP安定www」って思ったらP 3211 Washing Clothes リア充が服を洗おうとしている。本人か彼女かのどちらか…
ひさしぶりのするめ 250 予言者が「鳥と卵どっちが先にあったの」という問に対してN人の人に答えた。でも何人かにはでたらめな答えを言ったらしい。そのN人の人に質問したら、いくつか「卵」って答えが返ってきたけど、ある人数だけ嘘つきがいるらしい。鳥?…
1214 "Accordian" Patience 「Accordian」というトランプゲームで遊ぶらしい。 ルールは、「カードの山(最初は各山1枚ずつ)が横に並んでいて、山の一番上のカードが、その左もしくは3つ左の山の一番上のカードとマッチするとき移動できる。2枚のカード…
1234 Ball Toss 学生が輪になって並んで規則に従ってボールを投げる。やるだけ。最初に投げる生徒は初めはボールを受け取っていないことに注意!!!
2777 Count Color 線分があって、「ある範囲をある色で塗りつぶせ」というクエリと「ある範囲には何種類の色が使われているか」というクエリが与えられるから処理せよという問題。色は高々30種類。Segment Tree。割と楽に書ける。色の処理はビット演算を使う…
最悪でした。問題についてはパスワードが今ないので書けないのですが。 問題は概して簡単(8,9除く) 開始早々ログインできない。そのおかげで終了が1時間遅延する ログインできても、ろくに送信できない。2〜3問送ったらすぐに繋がらなくなる(ただ、こ…
ちょっと遅いかもだけど。 Day 0 (成田) 成田エクスプレス。速いけど遠い IOIなどの問題の解説。APIOの問題の解答に驚愕 「ルービックキューブみたいなもの」が好評 Day 1(成田−トロント−ウォータールー) ホテルはよかった。朝食に「うどん」があったぱな…
3181 Dollar Dayz 1ドルからKドルまでの品物がある。あなたはNドル持っている。Nドル丁度使って品物を買う方法(同じ品物をいくら買ってもよい)は何通りあるか?という問題。多倍長+DP。 2838 Graph Connectivity 無向グラフに対して、「辺の連結」「辺の削…
1717 Dominoes 1000個以下のドミノがあって、横に並んでる。何個かひっくり返して上下の数の和の差を最小にしたい。最低何個ひっくり返せばいい?DPやるだけ 3041 Asteroids 危険な小惑星があるらしい。それをスターライトブレイカーかレールガンか知らない…
ひさしぶりのPKU。