問題概要 H×Wの大きさの店がある。店内は、床('.'), 壁('#'), 目的地('t')で構成されている。N個の(x,y)の組が与えられる。これは時間i(1 ≤ i ≤ N)に(xi,yi)のマスが開放される(そのマスが壁('#')ならば床('.')になる)。この条件の下、スタート地点(0,0)から…

問題概要 Claireという女性がいる。彼女がN人の男性のうちの何人かとデートをするプランを立てることを考える。N人の男性にはそれぞれM個のデートをする時間帯(SからE)とその男性とデートしたときの満足度Lが与えられる。彼女は各男性に対して、全ての時間帯…

問題概要 N個の町があり、その中には町sと町tが含まれる。町sでFリットル生クリームが製造され、他の町に運び、町tまで運ぶ。移動の際に移動元の町と移動先の町の気温差の絶対値だけ生クリームが傷む。各町の気温はN元一次連立方程式の解により求められる。…

問題概要 H×Wの二次元グリッドがある。このグリッドは以下の要素で構成されている。 '@' : スタート位置 'E' : ゴール位置 '#' : 壁のマス 'c' : コンテナが存在するマス 'w' : パネルのマス プレイヤーは隣接する上下左右のマスに移動することができる。た…

string str = 文字列; stringstream ss(str); while(getline(ss,部分文字列を代入するための変数,分割したい文字)){} 例えば、カンマ(',')区切りで分割したい場合 string out; string str = "abc,def,ghi,jkl"; stringstream ss(str); while(getline(ss,out,…

問題概要 n個の数値v1,v2,…,vnとwが与えられる。 1区間の範囲をwにしたヒストグラムを作成する。例えば、下図ならば、w = 10で各区間は、0~9,10~19,20~29,30~39のようになる。この各区間の棒グラフに色を塗る。一番左を黒に、それから右に行く毎に色を薄くし…

問題概要 折れ線0,1,….,nのn+1個の折れ線が与えられる。各折れ線はm個の頂点で構成される。折れ線を構成する各線分はx軸またはy軸に平行であり、頂点では必ず90°回転する。xy平面で回転または平行移動をして折れ線0と一致する折れ線iを出力せよ。テストケー…

問題概要 nとpが与えられる。 1~nまでの数字で分子と分母を作ったとき、x/y > √p > u/vとなる最小のx/yと最大のu/vを分数の形で出力せよ。出力する分数は既約分数である必要がある。 制約 n < 10000 p < 10000 解法 √pより大きくなる分数、小さくなる分数そ…

問題概要 w×dの二次元グリッドがあり、その上でサイコロを転がす。サイコロの初期位置は'#'で表される位置であり、サイコロの各面には色が付いていて、初期の状態はtopがred、bottomがcyan、northがgreen、southがmagenta、eastがblue、westがyellowである。…

問題概要 N個の数字(c1,c2,...,cN)が与えられる。Q個のクエリがあり、各クエリでqが与えられる。このときN個の数字の中でqで割った余りの最大値を出力せよ。 制約 2 ≤ N ≤ 300000 2 ≤ Q ≤ 100000 1 ≤ ci ≤ 300000 1 ≤ qi ≤ 300000 解法 まず、入力されたN個…

問題概要 "Chicken"と"egg"のみで構成された文字列がある。 次のルールに従って先に生まれた方を出力する。 異なる2つが並んでいる(chickenegg または eggchicken)場合、後ろのものが先に生まれる。 同じ2つが並んでいる(eggegg または chickenchicken)場合…

問題概要 tとnumが与えられる。numを分割して和を取ったとき、tとのdiffを最小化し、そのときの和と経路を出力せよ。 もしどのように分割してもtを超えてしまう場合は"error"を、最小のdiffが複数ある場合は"rejected"を出力する。 制約 1 ≤ t ≤ 999999 1 ≤ …

問題概要 長さlのトンネルがあり、その中のにn匹の蟻がいる。それぞれの蟻は位置piにいて向きd(dが'L'なら左、'R'なら右)を向いている。全ての蟻は1単位時間に向いている方向に1進む。そして2匹の蟻が同じ位置に到達した場合、それらの蟻の進行方向が反転す…

問題概要 n個のαとβの組が与えられ、これは文字列の中にαがあればβに変換する。文字列を変換する際には左から優先して全てのαをβに変換しなければならない。文字列γから文字列δへ変換するための最小手数を求めよ。もし不可能な場合は-1を出力する。 制約 n ≤…

問題概要 横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 解法 全てのエッジ…