キングが中心にいる場合、キングから周囲のマスまでの移動は 22222 21112 21012 21112 22222 のようになっている。距離1のマスは45度回転すると のようになる。 すべて整数で表すために√2を掛けると 座標は(2, 0), (1, 1), (0, 2), (-1, 1), (-2, 0), (-1, -…

素朴に考えると dp[i][j] := i個の要素を使って、前の部品のprofit factorがjのときの最大profit のようなDPを得る。 例えば、サンプルの入力で6, 8を使うと dp[2][8] = 6*8 のようになる。 この方法には問題が3つあるが、どれも対処できる。 (1) profit fac…

左から要素を見ていく。 a[i] > a[i+1]であるような隣接する2つの要素を見つけた場合、対処は2種類ある。 (1) a[i]の値を小さくする。 これができるのは i = 0の場合、もしくはi>0かつa[i-1]<=a[i+1] の場合のみ (2) a[i+1]の値を大きくする。 具体的にはa[i…