hotpepsiの練習帳

SRM 584

02:24

Div2 Easy (250) TopFox

問題

• TopFoxに参加するためにハンドルネームを決めたい
• 姓と名のそれぞれ先頭から1文字以上取って連結する
• 何通り作れるか求める

方針

• 先頭からしか取れないぽい
• 重複する可能性がある
• setに突っ込む
• Passed System Test
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_584/TopFox.cpp

Div2 Medium (500) Egalitarianism

問題

• N人の市民がいる
• 友達かどうか与えられる
• 直接の友達の財産はプラスマイナスd以内
• 任意の二人の市民の財産の差の最大値を求める

方針

• グループが2つ以上あると差が計算できなくなる
• union findでグループの数を数える
• 友達の場合、最大の距離を求める
• Warshall-Floyd
• Failed System Test
• (終了後)
• 単純なWFでよかった
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_584/Egalitarianism.cpp

Div2 Hard (1000) Excavations2

問題

• N個の遺跡があり、それぞれの種類が与えられる
• それらのうちK個だけ発見され、種類が与えられる
• 元の遺跡の組み合わせの総数を求める

方針

• 種類ごとに建物がいくつあるか数えておく
• 与えられた種類の建物は必ず含まれている
• が、いくつ発見されたかは任意
• 1個の場合、2個の場合...を数え上げるので場合の数
• dp[使った種類][残りの発見数] みたいな感じでいける
• Failed System Test
• (終了後)
• メモ化を忘れた
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_584/Excavations2.cpp

結果

oxx -1 246.67 -25pt = 221.67pt 392nd/932 rating 1180 -> 1132

間抜けなミスで落としてもったいなかった。