hotpepsiの練習帳

SRM 506 Div2

01:48

Easy (250) SlimeXSlimeRancher2 育てゲー

問題

• 最大のスライムの値に合わせるために、育てる総和を求める。

考察

• maxだけわかれば、ソートする必要なかった。

実装

• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_506/SlimeXSlimeRancher2.cpp

Medium (500) SlimeXSlimesCity 合併

問題

• 任意の二つの町を合併させるとき、町の名前として残るのは何通りか答える。

考察

• 人口でソートしておく
• X+1番目の町の人口が、X番目の町までの全合計を上回る場合、X番目までの町は残らない。この条件で消していくだけ。
• 全合計を上回らない場合は、残る可能性がある。(判定条件としては上の条件のみでよい)
• 本番では解く早さ優先で個別に合計を求めたが、合計を求めながら判定するだけでいいので二重ループは不要。

実装

• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_506/SlimeXSlimesCity.cpp

Hard (1000) SlimeXResidentSlime ゾンビスライム

問題

• 文字で表された2次元のフィールドがある
• フィールドに勇者(あなた)とゾンビスライムが何匹かいる
• ゾンビスライムは1～9の数字で表され、数字のターン後に復活する
• ゾンビスライムと交差すると倒せる
• 倒されたゾンビスライムに交差すると、復活してその場で倒したことになる
• 全てのゾンビスライムを倒す瞬間が生み出せればOK
• 最小のターン数を求める

考察

• スライムが10匹以上いたら不可能
• 全てのスライムに到達可能でなければ不可能
• 一番値の小さいスライムから、一番値の大きい(または遠い)スライムまでの距離が、一番値の大きいスライムの値を超えていたら不可能
• kusanoさんのを写経
• 初期位置を0番目、スライムの位置を1～9番目とする
• 任意の位置同士の距離を求めておく(不可能なら-1)
• 0番目から最後のスライムまで一筆書きした距離を求める
• 最後のスライムに到達した時点で復活しているスライムがいなければOK
• 復活判定のため、最後のスライムから距離を加算していくと簡単に判定できる
• スライムを一筆書きする順番は1～9でnext_permutationで列挙

実装

• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_506/SlimeXResidentSlime.cpp

結果

oo- 240.35+358.19 864 -> 991

EasyとMediumのシステムテストが通って緑に戻った。

Hardは無理げーなので諦めた。もう少し慣れたら再挑戦するかも。