hotpepsiの練習帳

SRM 589

01:12

Div2 Easy (250) GooseTattarrattatDiv2

問題

• 文字列が与えられる
• 1文字変更するのに1秒かかる
• 全ての文字を同じにするのにかかる時間を求める

方針

• 全カウント - 最大の文字のカウント
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_589/GooseTattarrattatDiv2.cpp

Div2 Medium (500) GearsDiv2

問題

• N個のギアがある
• 最後のギアと最初のギアはつながっている
• ギアの向きが与えられる
• 全てのギアがまわるようにするために取り除かなければならない個数を求める

方針

• 同じ文字が連続している部分をつぶす
• 先頭の文字を末尾にもコピーして、前の文字と同じなら取り除いていく
• 提出
• Challenge Succeeded
• 先頭を取り除くケースに対応できてなかった
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_589/GearsDiv2.cpp

Div1 Easy (250) GooseTattarrattatDiv1

問題

• 文字列Sが与えられる
• 全ての文字Xを文字Yに1文字ずつ変換する操作ができる
• 左右対称の文字列にするための最小の変更文字数を求める

方針

• わからん
• 変更してみて、一致数-変更数が一番良いものを選んでいく
• 失敗
• 他の人たちの解法を読む
• いったん同じ文字にしたらずっと同じ文字になる
• 対になる場所は同じ文字にしなければならない
• 元々同じ文字の場所もずっと同じ文字
• union findで同じ文字にしなければならない場所をまとめる
• まとめたグループを、同じ文字に変更する
• 変更する手順はdiv2の問題と同じ
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_589/GooseTattarrattatDiv1.cpp

結果

ox- +1 -1 246.03 + 50 - 25 = 271.03pt 255th/1095 rating 1183 -> 1186

例を作るのが下手すぎ。