1904 King's Quest 王様にはN人の息子がいる(1息子iをS(i)、少女iをG(i)として、息子iが少女jを好きなときS(i)->G(j)のリンクを、リストに息子iと少女jの関係が書かれているときG(j)->S(i)のリンクを張った有向グラフを作り、強連結成分分解。各息子について…

3140 Contestants Division 学校がいくつかあって、各学校には何人か生徒がいる。学校同士はリンクがあって、リンクをみると木構造になってる（？）。２つのリンクで結ばれてる集合に分けたい。生徒数の差を最小にするとき、その最小値は？普通に木DPやるだ…

250 木がたくさん、地面に垂直に植えてある。いくつかの木を縮めて（縮めるっていうか時間を巻き戻すらしいけど）、木のてっぺんが一直線上に並ぶようにしたい。いくつの木を縮めたらいい？やるだけ。double使うときは誤差に注意 550 重みつき無向グラフ状の…

250 1からNまでの数を立方体に書いて、サイコロを作る。向かい合う目の和はどれも等しく、K以上じゃなきゃいけない。同じ数を2回以上使っちゃいけない。回転させて同じになるものは1通りとして考える。何通りできる？やるだけ。同じ目の組み合わせで、回転を…

時間が数分足りなくてだめだったのでPracticeで解き直してみた #include <vector> #include <cstring> #include <algorithm> using namespace std; #define MOD 1000000007 class AppleTrees { long long dp[40][2][1600]; int N; public: int gcd(int p, int q) { while(q>0){ int tmp =</algorithm></cstring></vector>…

うさぎさんがでてきた回。 300 N種類の球があって、そのうち2つを同時に入れると2つの球によってある決まった球を返してくる装置がある。与えられた装置が、「どんな球の集まりに対しても、どうやって装置に球を入れて１個になるまで繰り返したって結果同じ…

3025 Rings 太さが限りなく0に近いとしていいリングがたくさん撒いてある。重なっているリングはひとつながりになっている。ひとつながりのリングの集まりで、最も多くのリングを含むものが含むリングの数を出力せよ。DFSやるだけ 2425 A Chess Game サイク…

またまたひさしぶりのPKU

集積回路ができる前はトランジスタが演算素子だったんだってね。その前は真空管、もっと前は歯車か。 ということで、Nビット入力 -> Mビット出力 の対応表が与えられたとき、その回路をトランジスタだけで実装する回路を設計するプログラムを作ってみた。 こ…

死にました（詐欺に非ず）。 250 簡単。 550 知らない 950 組み合わせ 結果 250も落とされたし550も落ちた -25点 Rating: 2254 -> 1989

11/6-7に、会津大学で開催されたパソコン甲子園に参加してきました。 本選競技 後ろの方の問題は難しいので簡単な問題をさっさと解く方針。 １問目。ヒットアンドブロー。少しだけわかりやすいコードを書いて少しだけ清書して送る。 ２問目。ソートして足し…

1916 Rat Attack 1025*1025のグリッドからなるフィールドがある。そこのいくつかの点にはネズミがいる。ネズミ駆除会社は、威力dの殺鼠剤を使って駆除をしたい。殺鼠剤は、それが置かれた地点と、ネズミの座標のx,y座標の差がともにd以下であるような位置に…

ひさしぶりにPKU

300 いきなりぶっ飛んだ配点。 レジスタ1つで、+,-,*,/の処理しかできないコンピュータがある。それぞれの処理は、レジスタの内容を演算子の両側にぶち込んで実行してレジスタに戻す。プログラムは処理を書き並べたものである。ある値から、目標の値にすると…

1609 Tiling Up Blocks それぞれ属性(l, m)を持つブロックを積み上げる。ブロック(l, m)はブロック(l', m')の上に、l >= l' かつ m >= m' が成り立つとき、積み上げられる。何段まで積める？lでソートして最長部分列。mが高々100なのでO(100*N)で通る。

2417 Discrete Logging 離散対数問題。整数B,N,P(Pは素数)が与えられたとき、B^L mod P = Nなる最小の整数Lを求めよ。Pが2^31ぐらいあるので普通にやるとTLEするが、だいたいO(√P log P)ぐらいで計算できる方法がある。 P

1659 Frogs' Neighborhood 蛙が何匹かいる。何組かの蛙はお互いに隣人であるらしい。各蛙の隣人の数が与えられるので、条件を満たす関係を1つ出力せよ、という問題。2 2311 Cutting Game 長方形を切っていくゲーム。１回に１枚を、X軸かY軸に平行に切ること…

3228 Gold Transportation ある国にはいくつかの町があり、それぞれ金鉱と倉庫がある。金鉱でとれる金の量と、倉庫の容量は決まっている。金を輸送する必要があるが、輸送には道路を使う。道路はある長さを持ち、２つの町を双方向につなぐ。ドライバーが疲れ…

意味不明な問題セット←罠。 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安定ｗｗｗ」って思ったらP 3211 Washing Clothes リア充が服を洗おうとしている。本人か彼女かのどちらか…

ひさしぶりのするめ 250 予言者が「鳥と卵どっちが先にあったの」という問に対してN人の人に答えた。でも何人かにはでたらめな答えを言ったらしい。そのN人の人に質問したら、いくつか「卵」って答えが返ってきたけど、ある人数だけ嘘つきがいるらしい。鳥？…

1214 "Accordian" Patience 「Accordian」というトランプゲームで遊ぶらしい。 ルールは、「カードの山（最初は各山１枚ずつ）が横に並んでいて、山の一番上のカードが、その左もしくは３つ左の山の一番上のカードとマッチするとき移動できる。２枚のカード…