hotpepsiの練習帳

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