yukicoder No.374 コイン - mayoko’s diary

人類なので解くのが難しかった…

問題

解法

今回のゲームは離散的じゃないので, 動的計画法的 something は使えそうにないです。問題が解けるらしいことを考えると, (どちらかが必ず勝つための)戦略があるはずです。

そこでわかんねーと思いながら蟻本を見ると, 「対称な状況を作り相手の真似をする戦略」が書かれています。今回の問題にこれを適用すると,

S が最初に真ん中にコインを置く
S は後は K が置いた場所に対称な位置にコインを置く

ということをやれば, A >= B である限り必ず勝てます。

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll A, B;
    cin >> A >> B;
    if (A < B) cout << "K" << endl;
    else {
        cout << "S" << endl;
    }
    return 0;
}