2013-01-21
Codeforces 162
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倍した値とする
- スコアの最大値を求める
方針
結果
ooxo- 2874pt 173rd/1525 1674 -> 1673 (-1)
Dが解けたのはなかなか会心。ただCが落ちたためratingほぼ変わらず。
CがTLEした。MSVCの100万回endl出力はGCCのより遅く、GCCだと1secだったがMSVCだと全く間に合っていなかった。endlはバッファをフラッシュするので遅いということだが、GCCも仕様は同じだと思うので優秀である。遅いらしいというのは知っていたが全く気にしていなかった。
改行でなくスペースで区切ってもOKだったっぽい。