htkb-proconの日記

初心者がPythonで問題解いた記録

ARC014 C - 魂の還る場所

C - 魂の還る場所

Submission #3626930 - AtCoder Regular Contest 014

解法が思い浮かばなくて試しにビームサーチ解投げてみたら通ってしまって笑ったのでメモ。ただゲームのルール上筒の中に玉がたくさん詰まった状態で終盤から挽回するのは無理なので、不利な状態をジャカジャカ切っていっても問題ないのは自明かも。

正しい考え方は

  • 筒の中の玉を消せるならば消す
  • 消せない場合、その次に来る色の玉が…
    • 筒の中にあるなら、その玉がどちらかの端に出るように(=次に消せるように)積む
    • 筒の中にないなら(その次を考えて)適当に積む

以上をすると常に筒の中は石が3個以内、同じ色の石が2個以上溜まらないようにできるので、結局奇数個の色の石が残ることになり、奇数個の色の数が答え。