2/10 PKU

2886 Who Gets the Most Candies?

N人の子供が円状に並んでいる。K番目の子供から始めて、「その子供が自分の数を言い、その子供は円から抜けて、言った数に応じて次の子供を決めてその子供から同じ事を繰り返す」という行為を1人になるまで行う。i番目に抜けた子供はiの約数個のキャンディをもらう。最も多くのキャンディをもらい、その中で最初に抜ける子供は誰か。

各ステップをSegment Treeで高速化する

3016 K-Monotonic

整数列がK-Monotonicであるとは、その数列がK個の連続した部分列に分割でき、各部分列が狭義単調増加もしくは狭義単調減少であることを言う。整数列が与えられる。1回の操作で、1つの数字を1変化させられる。与えられた整数列をK-Monotonicにするために必要な操作の回数の最小値を求めよ。

狭義単調増加とかいうのはうざいので、単調増加の場合はVi[i] = V[i] - i, 単調減少の場合はVd[i] = V[i] + i として、広義単調列について考えるようにする。すると、増加列を考えている場合はVi, 減少列を考えている場合はVd に現れる数以外は考えなくてよくなるので、DPが使える。増加と減少で使いうる数が異なることに注意。

3106 Flip and Turn

各要素が文字である行列に対して、反転、回転などの処理が順に与えられる。最終結果を出力せよ。

変換を行列で表してその積をとると一発ですべての処理をした後の結果が出る。