2017-08-05から1日間の記事一覧

Restricted Permutations | CS Academy #40 (Div. 2 only)

値1からNまで順にみていき、もともと空の配列のどこかに1つずつ挿入する。 今、1~K-1の値からなる順列のどこかにKを挿入したい。Kが挿入できる位置は、K-1の位置だけに依存する。(K+1は順列内にはないので) よって、以下のようなDPを考えればよい。 dp[i][j…

Switch the Lights | CS Academy #40 (Div. 2 only)

まず1番目のスイッチを押すかどうか決める。1番目のライトをON/OFFするのは1番目のスイッチだけなので、1番目のライトがONならば押さない。OFFならばスイッチをおす。これで1番目のスイッチを押すかどうか決めて処理した。以後、1番目のスイッチは考えない。…

Move the Bishop | CS Academy #40 (Div. 2 only)

(1) (R1+C1) ≢ (R2+C2) (mod 2) の場合 移動できない。市松模様の同じ色しか移動できない。 以下、(1)でないと仮定する。 (2) (R1,C1) = (R2,C2)の場合 0回 (3) (R1, C1)が(R2,C2)の対角線上にある場合 1回 (4) (R1, C1)が(R2,C2)の対角線上にない場合 まず…