問題概要 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日目に戻る。また、カフェインを摂取…

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

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

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

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

問題概要 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の二次元グリッドがあり、グリッドの要素としてプレイヤーの初期位置(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区間しか移動できない…

問題概要 同じ高さnの二つのビルがあり、忍者であるあつしさんは警備のためビルとビルとの間をジャンプしながら屋上に向かう。各階数には以下の3つの状態が存在する。 普通の壁: これは0で表される。もう一方のビルの同じ階、1つ上の階、2つ上の階に移動する…

問題概要 N個のノードとM個のエッジがあり、各エッジを通るにはそのエッジのコストcがかかる。 ただし、1度だけ連続した2区間をコスト0で通ることができる。 このとき、出発地1から目的地Nへ到達するための最小コストを求めよ。 制約 2 ≤ N ≤ 100 1 ≤ c ≤ 10…