hotpepsiの練習帳

SRM 526 Div1

00:45

Easy (250) DucksAlignment

問題

• 升目状の盤面にアヒルが何匹かいる
• 位置はばらばらで、列または行に最大でも1匹しかいない
• 水平または垂直に、連続するように並べたい
• 最小の手数を求める

方針

• 全体としては、水平と垂直それぞれで最小手数を求めて、少ないほうを答える
• 盤面を90度回転させて水平判定を呼べば、水平に並べる関数だけでもいける
• なので水平に並べることだけを考える
• マンハッタン距離なので、垂直方向と水平方向の移動は完全に別で考えてよい
• まずY座標をそろえることを考える
• 全試行して通したが、平均値求めればいいだけだった。ただし小数点の扱いはバグりそう
• 次にX座標
• こちらは単純な平均値ではないので全試行。位置を加算したやつで平均とればよさそうだったが落ち着いて書けそうになかったのでやめた

実装

• 書き直した
• 水平と垂直を独立した配列に保持してソートしておく
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_526/DucksAlignment.cpp

Div2 Hard (1000) SumOfLuckiness

問題

• ある数の10進数表記での4と7の個数の差の絶対値を、その数の幸運値とする。
• AからBまでの数の幸運値の総和を求める。

方針

• 3桁単位で足す (ださい)
• ほんとは4と7の個数についてDPすればよいっぽい
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_526/SumOfLuckiness.cpp

結果

o-- 103.10 347th 1227 -> 1243

途中まで壮大に無駄なコードを書いたりしていてとても遅かった。

なんとかdiv1には残れた。

easyは(div2だけど)SRM 509から16連続通っている。これを続けるのとmedium解きたい。