hotpepsiの練習帳

SRM 593

21:42

Div2 Easy (250) RaiseThisBarn

問題

• 牛舎に何頭かの牛がいる
• 壁をつくって二つの部分にわけたい
• 同じ数だけ牛がいるようにしたい

方針

• (長さ-1)通りのわけかたがある
• 分割してから牛を数える
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_593/RaiseThisBarn.cpp

Div2 Medium (500) WolfDelaymaster

問題

• 数nを選び、n個のwとn個のoとn個のlとn個のfを連結する
• そのような文字列を1回以上連結する
• 上記の操作でできる文字列かどうかを判定する

方針

• がんばって4つの状態ごとに数える
• Passed System Test
• (書き直し)
• 4つの文字が連続していると仮定して数える
• 全てが同じ個数ならOK
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_593/WolfDelaymaster.cpp

Div1 Easy (250) HexagonalBoard

問題

• ヘックスの升目のボードがある
• Xの印がついているところに色を塗る
• 隣接していれば違う色を塗る
• 最低何色必要か求める

方針

• DFS
• 最大3色っぽい
• 周りが塗られていなければ色1で塗る
• 周りが色1のみで塗られていれば色2で塗る
• 周りが色2のみで塗られていれば色1で塗る
• 周りが色1と色2で塗られていれば色3で塗る
• 最大の色番号が必要な色数
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_593/HexagonalBoard.cpp

結果

oo- 228.43 + 274.65 = 503.08pt 406th/1314 rating 1161 -> 1141 (-20)

mediumは最初がwでないときみたいに場合わけになってしまい、いまいちな書き方だった。

数えるのと判定するのを分離すべき。