yukicoder No.374 コイン
人類なので解くのが難しかった…
解法
今回のゲームは離散的じゃないので, 動的計画法的 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; }