けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AOJ 2954 串刺し (Skewering) (HUPC 2019 day2-C)

これの原案だった!!
対称戦略」が印象的なゲームの問題を作ろうとして作った

問題概要

1 × 1 × 1 の立方体を  A \times B \times C の直方体形状に積み上げたものがある。これを使って 2 人でゲームする。

  • 交互に、直方体のある面のあるマスを選んで、そこから反対側へ向かって串刺しにする
  • ただし、すでに串が刺さった立方体の部分を貫通するように串を刺すことはできない

串を刺せなくなった方が負けである。双方最善を尽くしたとき、どちらが勝つか?

制約

  •  1 \le A, B, C \le 100

解法

基本的には「対称戦略」を用いる!!!次の 2 つの場合にわけて考える

  • 「奇数 × 奇数」の面があるとき (先手必勝となる)
  • 「奇数 × 奇数」の面がないとき (後手必勝となる)

もし奇数 × 奇数の面が存在したならば、先手は、初手でその面のど真ん中をブッ刺せば OK。その後は後手の手に応じて、それと対称な手を真似していけばよい。

もし奇数 × 奇数の面が存在しない場合は、後手は、先手の手に応じて、それと対称な手を真似していけばよい。

f:id:drken1215:20201014163348p:plain

f:id:drken1215:20201014163443p:plain

f:id:drken1215:20201014163549p:plain

コード

計算量は  O(1)

#include <bits/stdc++.h>
using namespace std;

int main() {
    int con = 0;
    for (int i = 0; i < 3; ++i) {
        int num;
        cin >> num;
        if (num & 1) ++con;
    }
    if (con >= 2) cout << "Hom" << endl;
    else cout << "Tem" << endl;
}