きままにものづくりスマートフォン用の表示で見るきままにものづくり日々の気付いたことなんかを書いてます。この広告は、90日以上更新していないブログに表示しています。2015-07-16SRM581Div1Easy問題N個のコンテナとM個の監視カメラを考える。監視カメラは連続したL個のコンテナを監視できる。コンテナが空の場合は"-"となり、何か入っている場合は"X"となる。カメラの位置は分からないが、カメラが監視している空でないコンテナの数は与えられる。この時のコンテナの状態を求めよ。コンテナの状態は必ず監視されている場合は"+"、監視されている可能性がある場合は"?"、監視されていない場合は"-"で表す。各コンテナを監視していないと仮定した時の与えられた条件を満たすかを確認することで、そのコンテナが"+"、つまり、必ず監視されているかどうかを判別できる。監視されているとは言い切れない場合は、そのコンテナを監視することができるかを調べる。これは、先ほどと逆で監視されていると仮定した時に条件を満たすかを調べればよい。計算量mapの挿入コストは無視している。11:20SRM581Div1Easy広告を非表示にするもっと読むコメントを書く2015-07-15SRM582Div1Easy問題N人の戦士が与えられ、それぞれの戦士の強さはs[i]である。M種類の強さes[j]を持つec[j]匹のモンスターも与えられる。戦士は自身より強さの小さいモンスターを討伐できる。戦士は一匹のモンスターを倒すと疲労度が1増える。すべてのモンスターを討伐する時のN人の戦士の中の最大の疲労度の最小値を求めよ。すべてのモンスターを討伐できない場合は-1を返す。最大の疲労度に対して二分探索を行う。最大の疲労度を固定することで、モンスターを討伐できるかの判定が可能になる。09:01SRM582Div1Easy広告を非表示にするもっと読むコメントを書く2015-07-14SRM583Div1Easy問題N個の街がひとつの輪となるようにつながっている。各街からは電車が出ており、それぞれの電車は最大range[i]個の街を移動できる。ダイクストラで解いているが、コストは1ずつしか増えないのでpriority_queueの代わりにqueueを使用している。10:29SRM583Div1Easy広告を非表示にするもっと読むコメントを書く2015-07-13SRM584Div1Easy問題ある国にはN人の国民がおり、それぞれ貯金を持っている。この国のルールとして貯金額の差がdより大きい人同士では友達になることはできない。友人関係を示す情報とdが与えられた時、国民間での貯金額の最大値を求めよ。最短路の中での最大値にdをかけ合わせることで答えが求まる。他のアルゴリズムを用いることで、計算量の削減ができる。高さNの二分木が与えられる。すべてのノードに車が通るようにするためには、最小でいくつの車が必要か求めよ。外側のノードを一台の車に走らせると、n-2までの二分木が2個ずつできあがる。08:40SRM585Div1Easy広告を非表示にするもっと読むコメントを書く2015-07-11SRM586Div1Easy問題サイズNの配列Yが与えられる。隣り合う点どうしを直線で結びグラフを作成する。x軸と平行な線と作成したグラフとの交点の最大数を求めよ。解法yに小数点をとることも可能なので、Yのすべての要素に2をかける。Y[x]、Y[x]+1、Y[x]-1となる平行線を引き、すべてのxに対して調べることで答えが求まる。十分に長い階段を考える。整数NとbadStepが与えられた時にN回の操作で、到達できる最大の高さを求めよ。許される操作は、i回目の操作の時に、i個分の段差を飛び越えるかそのまま動かないかのどちらかである。badStepの高さに行くことはできない。解法badStepはひとつしかないので、もしbadStepを通るようだったら、-1をすれば最大の答えが求まる。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。