hotpepsiの練習帳

SRM 613

ソート, 全探索 | 00:53

Div1 Easy (250) TaroFriends

問題

• 猫がN匹いる
• それぞれの猫の位置が一次元の座標で与えられる
• 太郎が合図をしたら、全ての猫が右か左にXだけ動く
• 最も左と最も右の猫の距離の最小値を求める

方針

• 位置をソートする
• 左のほうにいるやつは右に、右のほうにいるやつは左にいくべき
• 最小値は、ある位置より左のは右に、そうでないものは左に行く
• 境界の位置を全部試せばいい
• Passed System Test
• https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_613/TaroFriends.cpp

結果

o-- 239.87pt 152nd/727 rating 1209 -> 1354 (+145)

ソートしたら簡単になる系。

悩まなかった。あとちょっとで240点。

http://togetter.com/li/645181

SRM 612

DP | 17:36

Div1 Easy (250) EmoticonsDiv1

問題

• 顔文字をsmiles個送り付けたい
• 入力欄全体をクリップボードへコピー、クリップボードを入力欄へ貼り付け、入力欄から1つ削除の3つの操作が可能
• 入力欄にsmiles個入力するための最小手数を求める

方針

• DFS
• Challenge Succeeded
• DP
• N個ある状態で、コピーしてK回足す -> DP[N*(1+K)]よりDP[N]+1+Kのほうが小さければ更新
• N個ある状態で、1個消す -> DP[N]よりDP[N+1]+1が小さければ更新
• https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_612/EmoticonsDiv1.cpp

結果

x-- 0pt 324/452nd rating 1247 -> 1209 (-38)

NまたはN+1を因数分解して作る感じっぽい。

http://togetter.com/li/641003

SRM 611

math | 01:40

Div1 Easy (250) LCMSet

問題

• 集合Sが与えられる
• Sの全要素の最小公倍数をlcm(S)とする
• Sの全ての部分集合のlcmの集合をLCM(S)とする
• AとBが与えられる
• LCM(A)とLCM(B)が等しいかどうかを求める

方針

• Challenge Succeeded
• BにAの1要素aが含まれていないときは、Bの部分集合からaを作れる必要がある(逆も)
• Bの要素のうち、aの約数になっているもののLCMを取っていって、結果がaと等しいなら、aが作れる。作れないなら、等しくない
• Aの任意の部分集合について考える
• Aの任意の要素p,qについて、pとqそれぞれはBの部分集合で作ることができる。LCMについては、素因数単位で考えると乗数の最大値を取ったものであり、Bの同じ要素を2回以上使う必要はないので、LCMについても作ることができる。つまり任意の部分集合のLCMが作れる
• なので、要素を作れるかどうかだけ判定すればよい
• https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_611/LCMSet.cpp

結果

x-- 0pt 341st/644 rating 1257 -> 1247 (-10)

なぜ要素が作れるかどうかだけで判定できるのか理解するのに時間がかかった。

http://togetter.com/li/637876

SRM 610

DP | 00:32

Div2 Easy (250) DivideByZero

問題

• 何枚かの紙に数字が書いてある
• 任意の2枚を取り出して、大きいほうの数÷小さいほうの数を計算する
• 商が紙にない数なら追加する
• 最終的に紙が何枚か求める

方針

• setに突っ込む
• 追加されなくなるまでループする
• Passed System Test
• https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_610/DivideByZero.cpp

Div2 Medium (550) TheMatrix

問題

• 0か1からなる升目がある
• チェス盤状になっている長方形の面積の最大値を求める

方針

• DP
• 横方向と縦方向それぞれ、一つ前と模様が異なっていたら、網目の長さを+1していく
• 現在位置より前の最大の高さは全て既知
• 現在位置の高さからはじめて、幅を+1、高さをminで求めていく
• 最大の面積が答え
• Passed System Test
• https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_610/TheMatrix.cpp

結果

oo- -1 227.78 + 338.56 -25 = 541.34pt 30th/766 rating 1170 -> 1257 (+87)

典型的なDPが普通に解けた。

http://togetter.com/li/634761

SRM 609

全探索 | 01:58

Div1 Easy (250) MagicalStringDiv1

問題

• '<'と'>'だけからなる文字列がある
• 何文字か削除して、連続するk個の'>'と連続するk個の'<'だけからなる文字列にしたい
• 得られる最大の長さを求める

方針

• 全探索
• kの長さを1から試す
• k個の'>'だけカウンタを進める
• そのあと、k個の'<'を数える
• Passed System Test
• 位置iを決めて、そこより左の'>'と、そこより右の'<'の個数を数える
• 小さいほうの個数の2倍が候補
• https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_609/MagicalStringDiv1.cpp

結果

ox- 199.92pt 679th/777 rating 1227 -> 1170 (-57)

2時の回。ハッカソン中に参加。頭が働いてなかった。

http://togetter.com/li/630121