hotpepsiの練習帳

SRM 519 Div2

01:05

Easy (250) WhichDay

問題

• 6つの曜日が与えられるので、残った1つを答える。

方針

• 連想配列のある言語なら一発でできる
• std::map<string, int>に突っ込む
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_519/WhichDay.cpp

Medium (500) ThreeTeleports

問題

• 始点 (xMe,yMe) から終点 (xHome, yHome) までの最短コストを求める。
• ワープできるポイントが3つある。
• ワープするとコストが10かかる。
• ワープする2点は、どちらも始点として使える。

方針

• 本番では全探索した
• ダイクストラっぽく書き直してみたが、全てのノードからゴールに直接行けるので結局全探索している
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_519/ThreeTeleports.cpp

Hard (1000) BinaryCards

問題

• 0から63まで番号のついた64枚のカードがある。
• 番号xのカードは、片面に2^x個のドットが描かれている。
• ドット数の総和がAからBまで、1ずつ増加する様子が見えるように最小の手順でめくっていく。
• ZからZ+1に遷移させるとき、複数のカードをめくる必要がある場合には最大のカードからめくる。
• 途中経過で見える最大の和を答える。

方針

• 異なる最上位のビットと、それ以下の全てのビットを立てる
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_519/BinaryCards.cpp

結果

oo- 243.50+258.65=502.15 rating 1154 -> 1174

mediumのきれいな書き方がわからず力業で埋めたため遅かった。