hotpepsiの練習帳

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だったっぽい。