hotpepsiの練習帳

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

結果

o-- +2 113.72 + 100 = 213.72 rating 1477 -> 1537(+60)

毎回ソートしても通るというのはちょっと新鮮だった。

バグらせやすそうだったので写経がんばった。

集合が消せるかどうかは、過半数のものがあるかで判定できるというのは終了後にやっと理解した。

http://togetter.com/li/696518