Hatena::Grouptopcoder

hotpepsiの練習帳

2013-01-21

Codeforces 162

01:39

Div2 A. Colorful Stones

問題

  • RGB3色の石が並んでいる
  • 色の指示が与えられる
  • 指示と同色なら次の石に移動する
  • 最後にいる場所を答える

方針

  • 一つずつ処理する

Div2 B. Roadside Trees

問題

  • 高さのばらばらの木がある
  • 頂上にクルミがある
  • 移動するか食べるのに時間が1かかる
  • 高さが同じなら木から木へ飛び移れる
  • 全てのクルミを食べるまでの時間を求める

方針

  • 結局のところabsで足す

Div2 C. Escape from Stones

問題

  • 岩が自分めがけて落ちてくる
  • 逃げると、新しい自分の位置に向かって落ちてくる
  • 逃げた方向が与えられる
  • 岩が落ちた位置の順番を求める

方針

  • rだったら左端、lだったら右端に置いて範囲を狭めていく

Div2 D. Good Sequences

問題

  • 連続する2数が互いに素ではない数列を、良い数列とする
  • 与えられた数列の部分数列のうち良い数列の最大長を求める

方針

  • ある数Xに着目する
  • Xより前の数それぞれと素かどうか比べる...のは時間がかかりすぎて無理
  • 素でないというのはすなわち素因数が共通
  • 素因数ごとに、最後に使われた場所だけ覚えておけばよさそう
  • 素因数分解して、最後の素因数の場所の長さ+1の最大値を記録していく
  • 提出

Div2 E. Choosing Balls

問題

  • 何色かのボールがあり、それぞれのボールに値が設定されている
  • ボールを順番に取り出すか使わないかを選ぶ
  • 取り出したボールのスコアは、直前のと同じ色ならa倍、そうでなければb倍した値とする
  • スコアの最大値を求める

方針

  • 単純にDPしてみる
  • 提出
  • wrong answer

結果

ooxo- 2874pt 173rd/1525 1674 -> 1673 (-1)

Dが解けたのはなかなか会心。ただCが落ちたためratingほぼ変わらず。

CがTLEした。MSVCの100万回endl出力はGCCのより遅く、GCCだと1secだったがMSVCだと全く間に合っていなかった。endlはバッファをフラッシュするので遅いということだが、GCCも仕様は同じだと思うので優秀である。遅いらしいというのは知っていたが全く気にしていなかった。

改行でなくスペースで区切ってもOKだったっぽい。

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