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

トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/firewood/20140918