hotpepsiの練習帳

SRM 708

23:30

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

Div1 Easy (250) BalancedStrings

問題

• 文字列中の隣り合う2文字が異なる個数を、文字列のinstabilityとする
• 文字列の配列のinstabilityは、各文字列のinstabilityの合計値とする
• 二つの文字列s1,s2について、s1の各文字s1[i]とs2の各文字s2[j]が同じである個数を文字列のsimilarityとする
• 文字列の配列のsimilarityは、配列の全ての2要素の組み合わせのsimilarityの合計値とする
• 数Nが与えられる
• instabilityとsimilarityが等しくなるよう、要素数がNの文字列の配列を構築せよ
• ただし各文字列は100文字までとする

方針

• similarityは増えやすい
• なのでababab...みたいなのでinstabilityを稼ぎ、残りをe,f,g,h,...のように1文字だけで埋める
• 適当に作って減らすようにしたら効率的に作れなかったので、1から100まで全部力技で作り、埋め込み
• Passed System Test
• https://github.com/firewood/topcoder/blob/master/srm_7xx/srm_708/BalancedStrings.cpp

結果

o-- +2 94.74+100=194.74pt 59th/331st rating 1536 -> 1637 (+101)

元embedded systems engineerなので埋め込んでもOKOK

https://togetter.com/li/1079618