読者です 読者をやめる 読者になる 読者になる

きままにものづくり

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

SRM581Div1Easy

問題

N個のコンテナとM個の監視カメラを考える。監視カメラは連続したL個のコンテナを監視できる。コンテナが空の場合は"-"となり、何か入っている場合は"X"となる。カメラの位置は分からないが、カメラが監視している空でないコンテナの数は与えられる。
この時のコンテナの状態を求めよ。
ただし、コンテナの状態は必ず監視されている場合は"+"、監視されている可能性がある場合は"?"、監視されていない場合は"-"で表す。

解法

各コンテナを監視していないと仮定した時の与えられた条件を満たすかを確認することで、そのコンテナが"+"、つまり、必ず監視されているかどうかを判別できる。
必ず監視されているとは言い切れない場合は、そのコンテナを監視することができるかを調べる。これは、先ほどと逆で監視されていると仮定した時に条件を満たすかを調べればよい。

計算量

 O(N^2)
mapの挿入コストは無視している。

コード

SRM582Div1Easy

問題

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

解法

最大の疲労度に対して二分探索を行う。最大の疲労度を固定することで、モンスターを討伐できるかの判定が可能になる。

計算量

 O(NM log V)
N: 戦士の数
M: モンスターの種類
V: モンスターの数

コード

SRM583Div1Easy

問題

N個の街がひとつの輪となるようにつながっている。各街からは電車が出ており、それぞれの電車は最大range[i]個の街を移動できる。startからendまで行くのに必要な電車に乗る回数の最小値を求めよ。

解法

最短路問題に帰着できる。
ダイクストラで解いているが、コストは1ずつしか増えないのでpriority_queueの代わりにqueueを使用している。

計算量

 O(N)

コード

SRM584Div1Easy

問題

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

解法

最短路問題に帰着できる。
最短路の中での最大値にdをかけ合わせることで答えが求まる。
ワーシャルフロイドを用いているので計算量は O(N^3)だが他のアルゴリズムを用いることで、計算量の削減ができる。

計算量

 O(N^3)

コード

SRM585Div1Easy

問題

高さNの二分木が与えられる。すべてのノードに車が通るようにするためには、最小でいくつの車が必要か求めよ。
ただし、車は他の車も含め一度通ったノードをもう一度通ることはできない。

解法

動的計画法で求まる。
 f(n) = f(n-1) + 2f(n-2)
一番外側のノードを一台の車に走らせると、n-2までの二分木が2個ずつできあがる。このまま、計算すると O(N^2)となってしまうので、一つ前の要素を用いて O(N)にする。

計算量

 O(N)

コード

SRM586Div1Easy

問題

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

解法

yに小数点をとることも可能なので、Yのすべての要素に2をかける。
Y[x]、Y[x]+1、Y[x]-1となる平行線を引き、すべてのxに対して調べることで答えが求まる。

計算量

 O(N)

コード

SRM587Div1Easy

問題

十分に長い階段を考える。整数NとbadStepが与えられた時にN回の操作で、到達できる最大の高さを求めよ。
許される操作は、i回目の操作の時に、i個分の段差を飛び越えるかそのまま動かないかのどちらかである。ただし、badStepの高さに行くことはできない。

解法

badStepはひとつしかないので、もしbadStepを通るようだったら、-1をすれば最大の答えが求まる。

計算量

O(N)

コード