きままにものづくり

日々の気付いたことなんかを書いてます。

2015-07-01から1ヶ月間の記事一覧

SRM581Div1Easy

問題 N個のコンテナとM個の監視カメラを考える。監視カメラは連続したL個のコンテナを監視できる。コンテナが空の場合は"-"となり、何か入っている場合は"X"となる。カメラの位置は分からないが、カメラが監視している空でないコンテナの数は与えられる。 こ…

SRM582Div1Easy

問題 N人の戦士が与えられ、それぞれの戦士の強さはs[i]である。また、M種類の強さes[j]を持つec[j]匹のモンスターも与えられる。戦士は自身より強さの小さいモンスターを討伐できる。戦士は一匹のモンスターを倒すと疲労度が1増える。すべてのモンスターを…

SRM583Div1Easy

問題 N個の街がひとつの輪となるようにつながっている。各街からは電車が出ており、それぞれの電車は最大range[i]個の街を移動できる。startからendまで行くのに必要な電車に乗る回数の最小値を求めよ。 解法 最短路問題に帰着できる。 ダイクストラで解いて…

SRM584Div1Easy

問題 ある国にはN人の国民がおり、それぞれ貯金を持っている。この国のルールとして貯金額の差がdより大きい人同士では友達になることはできない。 友人関係を示す情報とdが与えられた時、国民間での貯金額の最大値を求めよ。有限値でない場合は-1を返す。 …

SRM585Div1Easy

問題 高さNの二分木が与えられる。すべてのノードに車が通るようにするためには、最小でいくつの車が必要か求めよ。 ただし、車は他の車も含め一度通ったノードをもう一度通ることはできない。 解法 動的計画法で求まる。 一番外側のノードを一台の車に走ら…

SRM586Div1Easy

問題 サイズNの配列Yが与えられる。配列の要素は座標を示しておりインデックスをxとした時、(x, Y[x])となる。隣り合う点どうしを直線で結びグラフを作成する。 x軸と平行な線と作成したグラフとの交点の最大数を求めよ。 解法 yに小数点をとることも可能な…