hotpepsiの練習帳

SRM 509 Div2

00:20

Easy (250) PalindromizationDiv2

問題

• 0から100000までの数が与えられる
• 加算または減算で、左右対称にするための最小コストを求める

方針

• 10で割った余りで判定するのをループ

実装

• 本番: 数の範囲が小さいので場合わけして解いた
• 解きなおし: 正順と逆順で格納してから、半分の長さでmemcmp
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_509/PalindromizationDiv2.cpp

Medium (500) LuckyRemainder

問題

• n個の数値が与えられる
• その数を組み合わせてできる全ての数の合計を9で割った余りを求める

方針

• 9の余りは、どの桁にあっても同じ
• それぞれの桁の数を足してから余りを求めればよい
• それぞれの値は、使うか使わないかで2^(n-1)回出現する

実装

• 本番: 総数を数え間違えてsubmitまで至らず
• 解きなおし: それぞれの数を合計してから2^(n-1)倍して、最後にmod 9を求める
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_509/LuckyRemainder.cpp

Hard (1000) NumberLabyrinthDiv2

問題

• 縦R×横Cのマス目があり、空または数字が書いてある。
• 数字が書いてあるコマからは、その数値だけ縦または横にジャンプできる。
• 空のマスには全体でK個だけ数字を書くことができる。
• 始点と終点が与えられるとき、最小のジャンプ回数を求める。

方針

• 基本はBFSで探索
• 数字がない場所は、書けば行ける
• 書いた場合は、次のレベルのキューに突っ込むようにする
• 書かずに行ける場所を全部処理してから、次のレベルを処理する
• 書くことによって最小値が更新されることがあるので、常にK個書く
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_509/NumberLabyrinthDiv2.cpp

結果

o-- 158.15 955 -> 908

Easyしか通らなかったのでrateが微減...