hotpepsiの練習帳

SRM 631

02:04

Div1 Easy (250) TaroJiroGrid

問題

• N×Nの升目があり、それぞれの升目は黒か白である
• 1回の操作で、1行全部を白に塗るか、または全部を黒に塗ることができる
• それぞれの列について、N/2個より多くの連続する升目がないようにしたい
• 最小の操作回数を求める

方針

• 半分のところを塗れば最大2回なので、1回で白黒ぜんぶ試してOKなら1、そうでなければ2
• ただし最初から条件を満たしていれば0
• Passed System Test
• https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_631/TaroJiroGrid.cpp

Div1 Medium (500) CatsOnTheLineDiv1

問題

• 左から右の直線上に猫が何匹かいる
• 位置と匹数が与えられる
• 時間timeだけ左右のどちらかに移動できる
• 2匹以上が存在する座標の総数の最小値を求める

方針

• 展開すると0、集めると1になる
• 展開したときと集めたときでDPみたいなテーブルを作る
• サンプル通ったので提出
• Challenge Succeeded
• 配列の制限が1000までだったので死んだが、それ直してもバグっていた
• kojingharangさんのところを読む
• 左から処理していく
• 一つ前に一箇所に集めたとき、そこに合流できるなら合流するのが優先
• 1匹に展開できるなら左に寄せる
• どちらも無理なら右に寄せて、答えを+1する
• 展開できる場合、狭いものを優先する必要があるかと思ったが、左詰めでぶつかるのであれば、少なくとも一方は集める必要があるので、幅の小さい(数が少ない)ほうを優先したりする必要はなかった

結果

ox- +1 169.55+50=219.55pts rating 1453 -> 1537 (+84)

SRMらしい問題。

http://togetter.com/li/713244