問題概要 横x×縦yのマップが与えられ、マップは以下のもので構成される。 S : スタート位置 G : ゴール位置 1 : 火属性のモンスター 2 : 氷属性のモンスター 3 : 木属性のモンスター 4 : 土属性のモンスター 5 : 水属性のモンスター モンスターを手に入れる…

問題概要 4×4の紙があり、最初この紙には色は塗られていない。今、N個のスタンプを持っていて、各スタンプの大きさはそれぞれHi×Wiである。紙にスタンプを押すと押された部分が全てそのスタンプの色に変わる(既にスタンプが押されていたら更新される)。スタ…

問題概要 a,b,cが与えられるので、 ax2+bx+c = (px+q)(rx+s)を満たすp,q,r,sを求めよ。 そのような組み合わせがない場合は、"Impossible"を出力する。 制約 0 < a ≤ 10000 -10000 ≤ b ≤ 10000 -10000 ≤ c ≤ 10000 0 < p 0 < r (r < p) or (p == r and s ≤ q)…

問題概要 縦4×横8にカード(または何もない)が並べられている。カードに書かれている数字は11~17,21~27,31~37,41~47(カードの合計枚数は28枚)である。最初、各行の1列目にはカードが置かれていない。まず、(縦,横) = (1,1),(2,1),(3,1),(4,1)にそれぞれ11,21,…

問題概要 2つのコンサートホールがある。N個の予約のリストがあり、これは[開始時間,終了時間]とそれに対するコストで表される。このとき、予約リストから時間の重複がないように選び、2つのコンサートホールに分けて(別々のコンサートホールであれば時間の…

問題概要 N段のピラミッド構造が入力として与えられ、これは下図のようなノードとエッジの関係がある。 各ノードには0〜9の数字が書かれている。このとき、入力として与えられた値Cを任意の値が0のノードに上書きしたとき、次のルールに従い、得られる得点の…

問題概要 10枚の板があり、各板には5つの切り口があり、切り口は長いものと短いものがある。 5枚の板を切り口を上にして縦に並べ、その他の5枚の板を切り口を下にして横に並べ、縦の5枚の切り口にはめ込む。このとき、はめ込むことのできるパターン数(同じ組…

問題概要 H行に空白(' ')またはアスタリスク('*')が与えられる。そしてアスタリスクは、いくつかの四角形(長方形または平行四辺形または台形)を構成している。任意の2つの四角形は接することはなく、辺を共有することもない。ある四角形の中に別の四角形が存…

問題概要 T日の睡眠サイクルがある。これはi日目に深夜12時からti時間睡眠を取ることを意味する。N個の組が与えられ、各組ではDi日目にM時から仕事が始まることを意味する。 睡眠サイクルは、1日に1つ進み、T+1日目には1日目に戻る。また、カフェインを摂取…

※ 未提出なので結果は不明。-> AC(2015/12/31) 問題概要 A,B,Cの3つの会社がある。それぞれの会社にはN人の社員がいて、各社員iにはスループットtiが与えられる。以下の三つの条件のより上の条件を満たすように出力せよ。 会社の全ての社員を使わなければな…

問題概要 主婦の琴子が家を出てn個のスーパー内いくつかをまわり、買い物リストにあるq個の品物を全て買い、家に戻ってくるための最小コストと最短距離を出力せよ。各スーパーにはki個の品物の名前と価格が与えられる。 制約 n ≤ 10 q ≤ 15 解法 今いるノー…

問題概要 n個の文字列が与えられる。これらを連結させてできる最小の文字列の長さを出力せよ。連結とは、例えば、ABCとBCDを連結するならばABCDとなる。なお、ある文字列が他の文字列の中に完全に含まれていても良い。 制約 n ≤ 14 解法 任意の二つの文字列…

問題概要 洞穴がいくつか存在する。そのうち中央の洞穴の番号を1とし、そこから渦巻き状にm個の番号がつけられている。ある洞穴からは左下、下、右下のいずれかに移動できる。また、洞穴のうちその番号が素数のものを素数洞穴という。スタート地点の番号をn…

問題概要 4×4の二次元グリッドがありプレイヤーは最初(0,0)にいる。そしてプレイヤーは壁に右手をついて歩くので元の位置に戻ってくるまでの経路を出力せよ。 解法 シミュレーションする。 入力が特殊なので工夫しないといけない。 感想 入力には対応できて…

問題概要 N個の変数があり、それぞれの変数は[si,fi]の期間でレジスタに割り当てられる。[si,fi]∩[sj,fj]=Φならば同じレジスタを使うことができる。この条件の下で使用するレジスタの個数を最小化せよ。 制約 1 ≤ N ≤ 10000 1 ≤ si ≤ 10000 2 ≤ fi ≤ 30000 …

問題概要 N個のノードがある。各ノードには座標(x,y)がある。ノードuからノードvへのコストは２点間のpathの中の距離pij=(xi-xj)2+(yi+yj)2の最大値である。srcからdstへのpathのコストを最小化せよ。 制約 1 ≤ N ≤ 1000 0 ≤ xi, yi < 215 解法 全てのエッジ…

問題概要 N個のエッジがあり、M個のLPGというpetroleum gasのガソリンスタンドがある。中村さんが運転するタクシーはcap[liter]のpetroleum gasの容量がある。最初これは満タンである。N個のエッジの情報は、aからb(bからa)に行くために距離dかかるというも…

問題概要 座標(x,y,z)に半径rのスペースステーションがN個ある。このN個全てのスペースステーションを行き来するための最小距離を求めよ。なお、2つの距離はoverrapしている場合は0と見なす。 制約 1 ≤ N ≤ 100 0 < x, y, z < 100 解法 全ての2頂点間の距離…

問題概要 Jackが崖を登る。崖はH×Wの二次元グリッドで表される。Jackは両足を交互に動かし崖を登る。つまり、左足を置いた後は右足を動かし、右足を置いた後は左足を動かす。グリッドは以下の要素で構成される。 'S' : スタート位置(必ず崖の一番下のH-1行目…

問題概要 H×Wの二次元グリッドがあり、グリッドは、障害物(0)、移動可能なマス(1)、スタート位置(2)、ゴール位置(3)、回復地点(4)で構成されている。蟻がスタート位置からライフポイント6の状態でスタートしライフポイントが0にならないようにゴール位置へ到…

問題概要 H×Wの二次元グリッドがあり、グリッドの要素としてプレイヤーの初期位置(4)、箱の初期位置(2)、ゴールの位置(3)、障害物(1)、何もないマス(0)が与えられる。プレイヤーは箱を押すことができる。ただし、プレイヤーも箱も障害物のマスやグリッド外に…

問題概要 W本の縦棒、H段のあみだくじの状態とスタートとゴールが与えられる。与えられた状態でスタートからゴールへ到達できる場合は0、d段目のjからj+1へ横棒を一つ加えることでスタートからゴールへ到達できる場合はdとj、どのように横棒を加えても到達で…

問題概要 N個の都市とM本のエッジがあり、各エッジには距離dと制限速度cが与えられている。出発地sから速度1で出発し、目的地gへ速度1で到達するための最短時間を求めよ。ただし、ある都市に速度vで到達した場合、その都市から次の都市へは速度v-1, v, v+1の…

問題概要 V個の駅とE本の区間があり、駅には1からVの番号が与えられている。E本の区間には距離が与えられており、その距離の総和を最大化せよ。ただし、同じ区間は1度しか訪れることができない。さらに最大距離の中で経路が辞書順最小になるようにせよ。 制…

問題概要 最初ライフポイントがMであり、これは道を歩くことで単位時間あたりに1減少する。L個の町にはライフポイントの回復地点があり、ここでは単位時間あたりに1のライフポイントを回復でき最大Mまで回復することができる。K本の道があり、そこには時間が…

問題概要 町1から町NまでのN個の町があり、町と町の間には道路がある。道路はK本あり、すべての道路は異なる2つの町を結んでいる。N台のタクシーがあり、町iではi番目のタクシーに乗車でき、i番目のタクシーの運賃はCiで連続して最大Ri区間しか移動できない…