Hatena::Grouptopcoder

hotpepsiの練習帳

2014-09-02

SRM 631

02:04

Div1 Easy (250) TaroJiroGrid

問題

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

方針

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

トラックバック - http://topcoder.g.hatena.ne.jp/firewood/20140902