問題概要 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区間しか移動できない…

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

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

問題概要 N個のマスがあり、各マスにはL個の一回休みのマスと、B個のふりだしに戻るマスがある。 1〜6までの目のサイコロを降り出た目の数だけ進む。 このときTターン以内にゴールに到達するための確率を求めよ。 ただし、ゴールを超えるような目が出た場合…

問題概要 縦A × 横Bのノートがある。 箱がN個あり、各箱の大きさは縦C × 横Dである。 それぞれの箱にノートが入るかどうかを判定し、入る場合は"YES"を入らない場合は"NO"を出力せよ。 ただし、ノートを回転させたり平行移動させてもよい。 制約 1 ≤ A , B ,…

問題概要 n個のサイコロがあり、それぞれのサイコロには1〜mまでの目がある。 サイコロをn個振ったときの和をSとするとき、S-kの期待値を求めよ。 ただしS-kが0以下になる場合はS-kを1と見なす。 制約 1 ≤ n 2 ≤ m 0 ≤ k < nm nm × mn < 100000000 解法 全探…

問題概要 パネルの初期状態と最終状態が与えられるので以下の条件の下で最終状態にするための最小コストを求めよ。 パネルは'W'と'B'で構成されており、'W'が白いパネル、'B'が黒いパネルを表す。 パネルを交換するmachineがあり、このmachineは任意の場所を…

問題概要 H&timesWの二次元グリッドが与えられる。 二次元グリッドは以下の要素で構成されている。 '@' : スタート位置 ' '.' : 何もないマスで移動可能 '#' : 壁マスで移動不可能 [A-Z],[a-z] : 英大文字と英小文字のマスがあり、これは、英小文字のマスを…