問題リンク Huge Family 解法 ある人物からは必ず2本辺が出ています。図に起こすと、グラフは閉路がいくつか散らばっているような図になります。人物AとBの間に家族割引があったならば、clanの中でも繋がっていなければならないので、この閉路の中に登場する…

問題リンク Time Trial 概要 W*Hのマップがある。 マップには岩とパネルが3つずつあり、全ての岩をパネルの上に運びたい。 人は1ステップにつき、上下左右に動ける。進んだ先に岩があった場合、その先が壁や別の岩でなければ押すことができる。 このパズルを…

問題リンク Deadly Dice Game 概要 長さNの円形のボードがある。ボードの各マスは黒色か赤色である。 初期位置を任意に選ぶことができる。サイコロを振って出た目の数だけ時計回りに進む。サイコロをT回振ったとき最終的に赤色のマスに停まる確率の最大値を…

問題リンク Left Hand Rule 概要 W*Hの長方形の壁の状態が与えられる。長方形の周囲には1か所だけ長さ1の穴が空いているが他の箇所は全て壁になっている。この穴が入口となる。入口から入って左手伝いに進んで行ったとき、目標のマス目に到達するのは何ステ…

問題リンク Luigi's Tavern 概要 H人の勇者、W人の戦士、C人の僧侶、M人の魔法使いがいる。彼らを招いてパーティーを開きたい。パーティーが成立するための条件は以下の通り ・勇者は必ずいなければならない ・パーティーに参加している勇者と戦士は親しくな…

問題リンク Strange String Manipulation 概要 N個の整数Ii(1 ここで、擬似乱数Riを次のようにとる。 R0 = S Ri = (A * R_i-1 + C) MOD M (1 入力数列Iから次の数列Oを得る。 Oi = (Ii + Ri) MOD M 数列OのエントロピーHを最小にするようなパラメータS, A, C…

問題リンク Ninja Legend 概要 H*Wの大きさのマップがある。マップは '%': 出入り口 '#': 壁 '.': 床 '^': 落とし穴 '*': 宝 で構成されている。忍者は出入り口から侵入し、出入り口から脱出する。 忍者は1単位時間に1マス進むことができる。落とし穴に進入…

問題リンク Erratic Sleep Habits 概要 長さTの起床時間tiのサイクルとN個の仕事リストが与えられる。仕事はDi日にMi時から始まる。Di日にMi時以前に起きればこの仕事をすることができる(ti 薬を飲むことで起床時間のサイクルを強制的に最初に戻すことができ…

問題リンク Adaptive Time Slicing Quantization 概要 N個の[0.0, 1.0]の実数値列と整数M, Lが与えられる。 実数値列をM個の区間に分割する。ただしどの区間も最低2つ以上の要素を持たなければならない。更に、各区間毎に以下のようにして二乗誤差を計算する…

問題リンク Infected Land 概要 N*Nのグリッドがある。グリッドのマスは '.': 何もない '#': 感染している '@': 車 の3種類からなる。各ステップにつきグリッドの状態は次のように遷移する。 '#'マスは、周囲8マスにある感染マスの個数が2個が3個のとき次の…

問題リンク A Way to Invite Friends 解法 X人の友達を誘える ⇔ X+1を含む区間[ai, bi]がX個以上ある となるので、区間の重なりの個数に注目します。 aiとbi+1の値でソートして重なっている区間をカウントします。aiの値なら+1、biの値なら-1となります。カ…

問題リンク KULASIS 解法 DPです。形はかなり複雑になりました。 あるボタンは0〜3回押す場合を考えれば十分です。4回以上押す場合を考えるのは無駄です。 すると、i段目のボタンについてボタンの押し方は4^4 = 256通りあることになります。 i段目のボタンの…

問題リンク Bitwise Kingdom 概要 [0, 2^N)の整数を表すN文字のビット文字列の中でM番目に小さいものを求めよ。 ただし、文字列の比較順序は次の順序で行われる 1. 文字列中に含まれる1の数が多い方が大きい 2. 1の数が同じならば辞書式で大きい方が大きい 1…

問題リンク Girls' Party 概要 ある整数Nと円形に並んだBチームとGチームの人たちが入力で与えられる。時計回りに数えていき、N人目の人が輪から外れる。輪から外れた次の人から再びN人目が輪から外れる。円がBチームのみ、もしくはGチームのみになるまでこ…

問題リンク Private Teacher 概要 N人の学生と期間W(週間)が与えられる。学生にはtiの勉強量が必要であり、勉強できる曜日のリストが決まっている。 1日につき、学生1人だけに勉強を1教えることができる。 期間内に全ての学生に対して必要としている勉強を教…

問題リンク Petoris 概要 h*wのブロックと、H*Wのボードが与えられる。ブロックには1個以上のタイルが、ボードには0個以上のタイルがはまっている。ボードにブロックをはめ込み、全てがタイルで埋まった行の数が得点となる。得られる得点の最大値を答えよ。…

問題リンク Repeated Subsequences 概要 アルファベット大文字のみからなる文字列Sが与えられる。Sのlongest repeated subsequenceを求めよ。 Sのlongest repeated subsequenceとは、Sを2つの部分文字列FとRに分け、それらのLCSの内で、最も文字数が長いもの…

問題リンク Mysterious Dungeons 概要 W*Hのマップがある。人('@')と出口('>')が1つずつある。人は隣接する4マスへ移動できる。 アルファベット大文字は岩を表す。岩は消えている状態と消えていない状態の2つの状態を持つ。消えている状態ならば人はこのマス…

問題リンク Turn Left 概要 M個の交差点とN本の双方向道路がある。交差点にはそれぞれ名前Sがついており、座標(x, y)にある。 交差点srcとdestが与えられる。道路を走る際、右に曲がることはできない、Uターンもできない。この条件のもとで、srcからdestへ最…

問題リンク Black Force 概要 H*Wのグリッドで表される凹凸の土地が与えられる。(i, j)の高さはH(i,j)である。 ここに容量C以上の水を蓄えるダムを建てたい。グリッドの中からダムにするための土地を連続領域として選ぶ。連続領域とは、領域内の任意の2マス…

問題リンク Flame of Nucleus 概要 N個のドームと、M本の双方向の道がある。ドームにはそれぞれPi人の人と、Ki人収容可能なシェルターがある。M本の道はドームiとドームjを結んで通行にD日の時間がかかる。 L日後に核が落とされる。L日目より早くシェルター…

問題リンク Goofy Converter 概要 N, MとN個のLiが与えられる。全ての i (0 Li = Σ(i が成り立つような長さN+M-1の{0,1}ビット列Kが存在するか。存在するならばそれのうちいずれか1つを、無ければGoofyと答えよ。 1 1 0 解法 Kはつまり、インデックスiから始…

問題リンク Compress Files 概要 N個のファイルがあり、それぞれ、圧縮前のサイズBと圧縮後のサイズAが決まっている。作業領域の初期サイズはMである。 圧縮が済んでいないファイルの集合を選び、1つの圧縮ファイルにまとめることができる。この圧縮ファイル…

問題リンク Dance Dance Revolution 概要 DDRの譜面が与えられる。これが「自然な」譜面かどうかを判定せよ。「自然な」とは ・左足と右足が交互に出る ・同じ矢印が連続しない ・体は常に前を向く ・足が交差しない を満たすことをいう。 譜面の長さ 解法 …

問題リンク First Experience 概要 コンピュータのシミュレータの動きをシミュレートし、演算結果を表示せよ。 シミュレータはR1, R2, R3の3つのレジスタがある。 R1: 最も新しい演算結果が入っている R2: 最も新しい入力値が入っている R3: 入力された演算…

問題リンク Greedy, Greedy. 概要 N種類(c1, ... ,cN)の価値を持つ硬貨がある。この硬貨の群に対して以下の2点を調べよ。 1. 任意の金額をこれらのコインで表せる 2. 任意の金額を表すのに必要な最小枚数が常に貪欲的に求まる 1 0 解法 適当な金額の範囲[1, …

問題リンク International Party 概要 N個の言語が飛び交うパーティーがあり、M個のグループがある。i番目のグループはki個の言語だけ使うことができる。パーティー全体で使用できる言語を最も小さくし、なおかつ任意の2グループ間でおしゃべりができるよう…

問題リンク Tetrahedra 概要 N本の棒のうち、6本を選んで四面体を作ったとき、作ることのできる四面体の体積の最大値を答えよ。誤差は10^-6未満にせよ。 6 長さ 解法 全探索です。 棒を6本選んで(nC6)、四面体のどの辺に使うか(6!)の組み合わせになるので、…

問題リンク Restaurant 概要 レストランのコックの動きをシミュレーションせよ。 コックは1人しかいない。レストランにはN個のメニューがある。メニュー i を調理するのにtiの時間がかかる。 注文は先着したものが優先的に処理される。コックは作らなければ…

問題リンク Moduic Squares 概要 3*3のセルと1つのmoduic cellがある。これら10マスに1〜10の数字を1回ずつ当てはめる。 3*3の中の全ての列について(垂直、水平、対角)のそれぞれの総和がmoduic cellの値を法にして等しい時、パズルが完成する。 入力に盤面…