問題リンク Beehives 概要 2人の人物がハチの巣の中を調査する。2人はセルを移動した方向を'a'〜'f'で表す。方向'a'〜'f'は反時計回りの順でつけるということは統一されているが、'a'の向きがどこを向いているかは統一されていない。2人の人物が調査した軌跡…

問題リンク Numoeba 概要 ヌメーバと呼ばれる、細胞が木構造の生物がいる。木の根になっている細胞をリーダーと呼ぶ。 木は単位時間毎に構造を変え、リーダーもそれに合わせて変わる。 ヌメーバの各細胞はnumbosomeと呼ばれる奇数の整数値(1〜12345677)を持…

問題リンク Colored Cubes 概要 サイコロがN個あり、各面に色が塗られている。どのサイコロのどの面も任意の色に書きかえることができる。N個のサイコロを全て同じサイコロにするために必要な色の塗り替え回数の最小値を求めよ。 1 解法 全探索です。 サイコ…

問題リンク Manhattan Wiring 概要 H*Wのナンバーリンクのパズルがある。0は空白マス、1は壁、2と3同士が結ぶべきマスである。このパズルを解くために必要な線の長さを最小化せよ。解が無い場合は0とせよ。 1 解法 DFS+枝刈りが方針です。 2を結ぶ線をDFSで…

問題リンク Super Star 概要 3次元上の点がN個与えられる。点を全て包含するような球の最小の半径を答えよ。 4 0 点は互いに0.01以上離れている 解法 いわゆる最小包含球を求める問題です。ココにすごく分かりやすい解説がまとまっているのでこれを参考にし…

問題リンク Digits on the Floor 概要 床にN本の線分で書かれたデジタル数字がある。0〜9の数字がいくつずつあるか答えよ。 線分の置かれ方には以下のような制約が保証されている。 線分同士は交差しない 2本の線分が接している時、その角度は直角 ある1点を…

問題リンク True Liars 概要 P1人の正直者とP2人の嘘つきがいる。正直者は常に真実を言って、嘘つきは常に嘘を言う。 P1+P2人のうち、正直者はどの人物達かを特定したい。 X番の人物に問いかけ、「Y番の人は正直者か」という質問をN回する。X番の人物の返答…

問題リンク Search of Concatenated Strings 概要 N個の文字列Ei と文字列Sが与えられる。Eiの各要素を1回ずつ連結した文字列が現れる箇所はSの中にいくつあるか答えよ。Eiの連結する順番は任意でよい。例えば、Eiが"a"と"b"であれば、"ab"もしくは"ba"が探…

問題リンク Concert Hall Scheduling 概要 コンサートホールが2つある。N個の利用申請があり、各申請の内容は、ホールを1つ期間[i, j]の間だけ費用wで借りたいというものである。ホールを[i, j]の間貸し出している期間中、他の利用者はそのホールを一切利用…

問題リンク The Morning after Halloween 概要 W*Hの大きさのオバケ屋敷がある。オバケはN匹存在する。 オバケはアルファベット小文字で表され、それぞれ定位置へ移動したい。各オバケの定位置は対応するアルファベットの大文字で表される。オバケは1ステッ…

問題リンク Geometric Map 概要 N本の線分で表現された平面の地図がある。 線分には道路の意味を持つものと標識の意味をもつものがある。 道路はその両端点が交差点となっており、他の道路と接続している。道路同士が交差したり、オーバーラップすることはな…

問題リンク Cubic Eight-Puzzle 概要 図3のようなサイコロと、3*3のグリッドがある。グリッドの初期状態は図4のような形であり、空マスとなる座標は入力で与えられる。1ステップにつき、サイコロを1つだけ空マスへ転がすことができる。入力で与えられる目標…

問題リンク Pipeline Scheduling 概要 ユニットが5個あり、1つのタスクを処理するための手順表が与えられる。表の長さはNである。 処理を行うクロックに衝突が生じないように10個のタスクを処理するための最小クロック数を答えよ。 N 解法 深さ優先探索+枝刈…

問題リンク Power Calculus 概要 x^nを求めるための最小乗除回数を答えよ。最初x^1から始まり、計算の途中で表れたx^kを使ってx^iから、x^(i+k)もしくはx^(i-k)を得ることができる。 1 解法 反復深化法を使って解きました。自分がこの方法を使うのはこの問題…

問題リンク Swimming Jam 概要 2レーンからなるプールがあり、それぞれ一方通行で往路と復路である。N人の水泳者がいて常にそれぞれ決められたスピードで泳ぐ。レーン内で人を抜く泳ぎ方は禁止されている。レーンに入るときに同時に入る人が複数いた場合、飛…

問題リンク Repeated Substitution with Sed 概要 N個の文字列のペア(αi, βi)と、文字列γ、δが与えられる。N個のペアの置換を行ってγからδを得るための最小ステップ数を答えよ。δが得られない場合は-1とせよ。ここで1ステップは次のように定義される。 ペア(…

問題リンク Cubist Artwork 概要 1*1*1の立方体を積んでアートを作る。作ろうとするアートを正面から見たシルエットと側面から見たシルエットが与えられる。このシルエットの形になるようなアートを作るために必要な立方体の最小個数を答えよ。 正面から見た…

問題リンク Bug Hunt 概要 簡単なプログラム言語の構造がBNFで与えられる。このプログラムは配列の宣言文と代入文のみで構成される。 配列はアルファベット1文字の名前がついており、宣言の時に配列の大きさが指定される。配列内の初期値は未定義値である。 …

問題リンク Slim Span 概要 N個の頂点とM本の重み付き辺からなるグラフが与えられる。このグラフのある全域木Tのsilmnessとは、辺の最小重みと最大重みの差で定義される。与えられたグラフ中の最小のslimnessを答えよ。全域木が存在しない場合は-1とせよ。 2…

問題リンク Minimal Backgammon 概要 0〜NマスのBackgammonをする。0がスタート地点でNがゴールである。サイコロを振って出た目の数だけ進む。ゴールを飛び越す場合、超過分だけマスを戻る。マスにはloseマスとbackマスがある。loseマスは停まると1ターン休…

問題リンク Prime Gap 概要 整数kのprime gapとは、k以下の最大の素数をp、k以上の最小の素数をp+nとしたときのnである。与えられる整数kのprime gapを答えよ。 2 解法 エラトステネスの篩で1299709までの素数表を作り、kから出発して、pとp+nに相当するもの…

問題リンク And Then There Was One 概要 1〜Nの人が円形に並んでいる。番号Mを消し、残った人の中でK番目の人間を消すことを繰り返す。最後に残るのは何番の人か答えよ。 2 1 1 解法 LinkedListを使えば、次に消す人物が(現在インデックス+K-1)%List.size()…

問題リンク Sum of Different Primes 概要 整数NをK個の異なる素数の和で表す方法は何通りあるか答えよ。3+5と5+3などは重複して数えてはならない。 N K 解法 メモ化再帰で解くことができます。 dp[i][j][k]: 整数iをj番目以降の素数をk個使って表す方法の個…

問題リンク How I Mathematician Wonder What You Are! 概要 与えられるN角形が星型であるとは、N角形内の任意の点Pとの線分CPが全てN多角形内に入っているような中心点Cが存在することをいう。与えられるN多角形が星型であるかどうかを判定せよ。入力の座標…

問題リンク How I Wonder What You Are! 概要 N個の星の3次元座標とM個の望遠鏡の置かれている座標と視野角φが与えられる。これらの望遠鏡を使って見ることができる星はいくつあるか答えよ。星 i が望遠鏡 j を使って見えるとは、それらの位置ベクトルの成す…

問題リンク Network Mess 概要 コンピュータがN台ある。コンピュータはスイッチハブに繋がれたケーブルを経由して、全てのコンピュータと繋がっている。コンピュータ同士をケーブルで繋ぐことはできない。また、1つのコンピュータに2つ以上のスイッチハブを…

問題リンク Atomic Car Race 概要 無限のエネルギーを持つ車でレースをする。車はいつまでも走ることができるがタイヤが擦り減ると速度が落ちる。直線状にN個のチェックポイントがあり、タイヤを交換することができる(交換には少し時間がかかる)、交換を行わ…

問題リンク Mobile Computing 概要 モビールというものは以下のように再帰的に定義される。 1つの石をヒモで吊り下げたもの 長さ1の棒の両端にモビールを吊り下げたもので、棒の重心の位置にヒモをつけて吊り下げられる 今石がS個あり、それぞれの重さはwiで…

問題リンク Organize Your Train 概要 X本のparking lineとY本のexchange lineがある。parking lineにはそれぞれ文字列で表された列車が停まっている。列車がない状態は"-"となっている。exchange lineは異なるparking lineの端と端を結ぶ。parking lineの初…

問題リンク Book Replacement 概要 図書館の書庫にはM個の台と1つの棚がある。台には入口から近い順にD1〜DMと番号がついている。台には一度にC冊の本が置ける。 図書館の司書は客からリクエストを受け取るたびに、リクエストされた本を書庫から取ってきて、…