Hatena::Grouptopcoder

hotpepsiの練習帳

2014-09-18

SRM 632

| 23:09

Div1 Easy (300) PotentialArithmeticSequence

問題

  • N個の正の整数からなる配列aがある
  • aの各要素を2進表現したときの末尾のゼロの個数の配列dが与えられる
  • 1個以上の連続する要素が1ずつ増加する等差数列になっている部分集合の総数を求める

方針

  • 規則性はありそうだが式が出せない
  • とりあえず全部出力して眺める
  • 大きな数は64個毎に、6→7→6→8→6→9...と出現し、それ以外の部分は6未満で周期性がある
  • 7以上の数を全部7に置換すれば、0~256の範囲内の数値だけで比較できそう
  • 全部の位置について、全部の長さを比較する
  • Passed System Test
  • https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_632/PotentialArithmeticSequence.cpp

結果

o-- 133.09pts 265th/600 rating 1536 -> 1557 (+21)

最近黄色率が高くて好調。

agwさんと同室だった。4回目らしい。(535,597,603,632)

http://togetter.com/li/715618

トラックバック - http://topcoder.g.hatena.ne.jp/firewood/20140918

2014-06-11

TCO 2014 Round 2A

| 23:38

Easy (250) SixteenBricks

問題

  • 16個の積み木がある
  • それぞれの大きさは1×1×Hである
  • 4×4のグリッド状かつ縦に並べたとき、最大の表面積を求める

方針

  • 低いものと高いものを交互に並べるのが良さそう
  • 高いもの8個と低いもの8個を市松模様に並べる
  • それぞれの配置をnext_permutationで全部調べればいけそう
  • 高いものの配置は2つ試したら変化がなかったのでとりあえず固定する
  • Passed System Test
  • https://github.com/firewood/topcoder/blob/master/tco_2014/SixteenBricks.cpp
  • 高いものについては、低いもののうち一番高いものよりも必ず飛び出しているので、どういう配置でも同じだった

結果

o-- 152.30pts 381st/1338 rating 1504 -> 1585 (+81)

TCOボーナスではあるけど、割と好調。


http://togetter.com/li/668654

トラックバック - http://topcoder.g.hatena.ne.jp/firewood/20140611

2014-05-06

SRM 614

| 22:11

Div1 Easy (250) MinimumSquare

問題

  • N個の座標がある
  • それらのうち、K個以上の座標を含むように正方形で囲む
  • ただし辺の上にあるものは含めない
  • 最小の面積を求める

方針

  • 範囲を愚直に全て調べるのは無理なので、どこかを決めうちする
  • どういう範囲であっても、左下は存在するはず
  • 左下を決めて、その位置より右かつ上のものを覚えておく
  • 条件を満たすものがK個以上になる場合、距離でソートして、K番目のものを使う
  • 左の座標と下の座標は、それぞれ別の点の可能性がある
  • XとYそれぞれのかけあわせで試せばいい
  • Passed System Test
  • https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_614/MinimumSquare.cpp

結果

o-- 159.79pt 239th/748 rating 1354 -> 1439 (+85)

図に描いたら思いついた。

xとyを独立で試すの割とよくあるかも。


http://togetter.com/li/648607

トラックバック - http://topcoder.g.hatena.ne.jp/firewood/20140506

2014-05-05

SRM 613

| 00:53

Div1 Easy (250) TaroFriends

問題

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

方針

結果

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

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

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


http://togetter.com/li/645181

トラックバック - http://topcoder.g.hatena.ne.jp/firewood/20140505

2014-04-19

SRM 609

| 01:58

Div1 Easy (250) MagicalStringDiv1

問題

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

方針

結果

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

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


http://togetter.com/li/630121

トラックバック - http://topcoder.g.hatena.ne.jp/firewood/20140419