hotpepsiの練習帳

SRM 628

01:00

Div1 Easy (250) DivisorsPower

問題

• 数Nの約数の総数をd(N)とする
• Nのd(N)乗をh(N)とする
• 数nが与えられる
• h(X) = NとなるXの最小値を求める

方針

• 賢い解きかたがわからん
• とりあえず因数分解して全部試すことに
• Nの最大値が10^18で、普通に10^9まで因数分解のループを回すとTLEで死ぬ
• 約数の最小個数は2で、Nは少なくとも2乗された数である
• 合成数は少なくとも3乗になるが、その場合には10^6まで因数分解しておけばよい
• 10^6までに素因数がないとき、Xが合成数だと3乗以上で10^18を超えるので、素数の2乗だけが候補となる。X=sqrt(X)として、Xの2乗がNに一致したらXは素数かつ答えで、そうでないときは解なし
• とりうる素因数を1から試してNに一致するか調べる
• powを使ったらX=105で誤差死したので、愚直に乗算するようにして再提出
• Passed System Test
• 因数分解から全探索に書き直した
• https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_628/DivisorsPower.cpp

Div1 Medium (500) CircuitsConstruction

問題

• いくつかの抵抗がある
• 抵抗は組み合わせAまたはBで結合する
• Aは和、Bは最大値
• 組み合わせ方と使用可能な抵抗値の一覧が与えられる
• 構成可能な抵抗値の最大値を求める

方針

• DFSの中でminとmaxでこねこねしたけど失敗
• ぱーぽーさんの記事読んだ
• 抵抗値を1と仮定してDFSすると、最終的に和として結合される抵抗の数がわかるので、大きい順に足せばよいらしい
• https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_628/CircuitsConstruction.cpp

結果

o-- +1 75.00 + 50 = 125.00pts 383rd/633 rating 1537 -> 1520 (-17)

約数の個数の小さい順に、(1)素数=2(2)素数の2乗=3(3)素因数が2つの合成数=4で、(1)だとsqrt(N)を調べればよく、(2)だとNの6乗根だけ調べればよく、(3)は10^18の4乗根で32000くらいまで素因数分解すればよかったらしい。

因数分解しないときはオーバーフローチェックが必要。

チャレンジケース見ていたら、書き方によっては10^9のループでも死なない場合があるようだった。

http://togetter.com/li/696518