2017-08-05から1日間の記事一覧
値1からNまで順にみていき、もともと空の配列のどこかに1つずつ挿入する。 今、1~K-1の値からなる順列のどこかにKを挿入したい。Kが挿入できる位置は、K-1の位置だけに依存する。(K+1は順列内にはないので) よって、以下のようなDPを考えればよい。 dp[i][j…
まず1番目のスイッチを押すかどうか決める。1番目のライトをON/OFFするのは1番目のスイッチだけなので、1番目のライトがONならば押さない。OFFならばスイッチをおす。これで1番目のスイッチを押すかどうか決めて処理した。以後、1番目のスイッチは考えない。…
(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)の対角線上にない場合 まず…