hotpepsiの練習帳

SRM 697

23:20

https://competitiveprogramming.info/topcoder/srm/round/16776/div/1

Div1 Easy (300) DivisibleSetDiv1

問題

• N個の正の整数からなる配列bが与えられる
• 以下の条件を全て満たす配列aが存在するかどうかを求める
• aの要素a[0],a[1],...a[N-1]は全て異なる
• 各要素は1以上の整数
• a[i]^b[i]は、a[i]以外の全てのaの要素の積で割り切れる

方針

• ぜんぜんわからず
• (終了後)
• hamayanhamayanさんの解説を読む
• 2の累乗だけで考える
• 2^(a[i] * b[i])が2^p[i]で割り切れることが必要
• a[i] * b[i]がp[i]以上であること
• 両辺にa[i]を足してみる
• a[i] * (b[i] + 1)がaの総和以上なら条件を満たす
• 各a[i]について、aの総和未満なら1を足してみる
• aを1〜Nに仮設定して、条件を満たすまで100万回くらい試せばわかる
• https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_697/DivisibleSetDiv1.cpp

結果

--- +1 50pt 80th/319 rating 1523 -> 1582 (+59)

復習したらなるほどという感じだった。

https://togetter.com/li/1013630