hotpepsiの練習帳

SRM 554

07:36

Div1 Easy (250) TheBrickTowerEasyDivOne

問題

• 二種類のブロックを交互に積む。
• 各ブロックの高さと個数が与えられる。
• 何通りの高さが作れるか求める。

方針

• 個数の少ない方の種類をA、多いほうをB、個数をaとbとする
• ABとBAで積んだときは同じ高さ
• ABAとBABは、AとBの高さが異なる場合には異なる
• 使用する個数は最大でa*2+1個
• Passed System Test
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_554/TheBrickTowerEasyDivOne.cpp

Div1 Medium (500) TheBrickTowerMediumDivOne

問題

• 0からN-1までのN本の塔があり、高さはばらばらである。
• 塔と塔の間を、それらの高いほうだけ離して一直線上に並べる。
• 全体の距離が最小で、塔の番号が辞書順最小の並べ方を求める。

方針

• ソートして並べるとだいたい最小解になる
• 単純に並べると、辞書順最小にならない
• 何か違うけど、とりあえずswapしてみるか
• Challenge Succeeded
• (終了後)
• どれを先頭にしても最小解は作れるっぽい
• つまり先頭はindex 0に固定してよい
• 置ける中で最小のものを貪欲に置いていけばよいらしい
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_554/TheBrickTowerMediumDivOne.cpp

結果

ox- +1 198.86+0+50.0=248.86 302nd rating 1344 -> 1421 (+77)

easyは、考え方は合っていたのだが、自分の手書きの例がぐちゃぐちゃで混乱した。twitterでみなさんがアップロードしていた図と比べてだいぶ汚いので反省した。

a*2+b>aと書いたら1になってしまい焦った。やはりいつもくくったほうが安全。

三項演算子のミス a > b ? a+1 : b を撃墜できたのは良かった。

mediumは、ほぼ全員が提出＆赤い人だけ通って面白かった。みんな提出するけど間違いがちというのは良い問題だと思う。