D - Face Produces Unhappiness

  • image
  • 考えたこと
    • 回転によって列の端前後の最大4人にしかスコアの変動はない
    • スコアが最大の状態はみんな同じ方向を向いてる時
    • 端に内側を向いてる番兵を追加する
    • 領域の外側が異なる向きを向いてる時、回転してもスコアは変わらない
    • 領域の内側が異なる向きの時も回転でスコアが変わらない
    • 両方揃ってる時にスコアが2増える、これが最善手
    • 線形オーダーでいくつ領域が取れるか数える(右に揃えるか左に揃えるかで2通りあるので大きい方を取る)
    • その個数とKの小さい方に2を掛けたものがスコアの増分
  • 公式解説
    • おおよそ同じ

ABC140