hotpepsiの練習帳

2014-08-13

SRM 629

02:05

Div1 Easy (250) RectangleCovering

問題

地面に大きさH×Wの四角形の穴が開いている
何枚かの四角形の板があり、それぞれの大きさが与えられる
板を何枚か使って地面の穴を完全に覆いたい
ただし板の四隅が穴の外側になるように置くこと
最低何枚必要か求める

方針

四隅が外側ということは、はみだす必要があるので、少なくともH+1またはW+1の長さが必要(サンプル3から、+2ではなく+1でよいことがわかる)
H+1の長さの板を縦に並べてW以上を作るか、W+1を並べてH以上を作る2択
Passed System Test
https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_629/RectangleCovering.cpp

Div1 Medium (500) CandyCollection

問題

形がN種類の飴がある
それぞれの形で2種類の味がある
味は全部でN種類
それぞれの種類で、それぞれの味の在庫の数が与えられる
買うときには形しか指定することができない
全ての種類の味の飴を集めるのに買う必要のある個数を求める

方針

kmjpさんのを写経
欲しくない味の個数+1を買えば欲しい味が手に入る
両方の味が欲しいときはそれぞれの味の個数+1の最大値
それぞれの味は2回だけ出現するので、ある形で買わないと、別の形では買う必要がある
同じ味でグラフでつないでいき、買う・買わないでDP
形X(味A,味B) -> 形Y(味B,味C)という遷移で、味Cを買う・買わないを作っていく
味Cを買わない場合は、(Xで味Bを買わない+今回味Bを買う)と(Xで味Bを買った)の最小値
味Cを買う場合は、(Xで味Bを買った+今回味Cを買う)と(Xで味Bを買わない+今回両方買う)の最小値
最終的に、最初に買わなかったかつ最後に買った、と、最初に買ったかつ最後に買わなかった、の最小値
閉路になってるので、閉路がなくなるまでループする
https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_629/CandyCollection.cpp

結果

o-- 222.61pts 128th/627 rating 1520 -> 1613 (+93)

割と好調。チャレンジは速度が足りなかった。

http://togetter.com/li/705603

CandyCollection=かんこれ?

コメントを書く

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

2014-07-30

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

コメントを書く

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

2014-07-13

SRM 627

01:26

Div1 Easy (250) HappyLetterDiv1

問題

文字列が与えられる
2つの異なる文字を取り除いていく
最終的に残る可能性のある全ての文字を結合した文字列を求める

方針

a～zまでのそれぞれについて、残るかどうか試す
残りの文字を出現数でソートして、一番多いものと次に多いものを取り去っていく
minで取るものを提出したが、1ペアずつ取るものと違う結果になった
1ペアのものでも間に合いそうなので提出
Passed System Test
https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_627/HappyLetterDiv1.cpp

Div1 Medium (500) GraphInversions

問題

N個の頂点とN本の辺が与えられる
グラフには自己ループはなく、連結である
それぞれの頂点は値を持つ
異なる頂点をK個以上通るパスについて、通った順に値を並べる
それらのパスのうち、転倒数の総数の最小値を求める

方針

kmjpさんのを写経
DFSで長さKのパスを全列挙する
binary indexed treeで転倒数を数える
kmjpさんのは非転倒数を数えてたっぽい。両方向から数えるため同じ値(正解)になる
torusさんのを写経
蟻本のやり方だと正規化する必要がある
数列Aがあり、i=1～nについて転倒数の和を求めるとき、(全体の和)-(A[i]までの和)を足していく方法だと正規化しなくてもよい
https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_627/GraphInversions.cpp