hotpepsiの練習帳

SRM 685

00:50

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

Div1 Easy (250) MultiplicationTable2

問題

• [0,n)の数の集合Sがある
• Sの任意の要素i,jに対して演算(i $ j)を定義する
• Sの部分集合をTとする
• Tの任意の2要素の(i $ j)が常にTの要素となるとき、Tの最小の大きさを求める

方針

• 任意の数xを選び、xと(x $ x)を計算用の集合sに足す
• sの任意の2要素a,bの(a $ b)がsに含まれなければ足していく
• [0,n)のそれぞれについて上記を試す
• sの最小値が答え
• Passed System Test
• (解き直し)
• https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_685/MultiplicationTable2.cpp

結果

o-- + 1 117.41 + 50 = 167.41pt 219th/421 rating 1474 -> 1489 (+15)

dfsという関数名で書いたが、足せるものがなくなるまで足すのはDFSではない気がした。

http://togetter.com/li/951927