Problem B
Hyper Rock-Scissors-Paper
～ハイパーぐうちょきぱぁ～
講評担当 : 野田
概要
• ジャンケンで勝った手を出力せよ
• 引き分けのときはDrawと出力せよ
• ただし出せる手は15種類
• Rock Gun Lightning Devil Dragon Water Air Paper
Sponge Wolf Tree Human Snake Scissors Fire
解法
• 辞書を作る
• 全勝利パターンをハードコーディング
– 却下
• グラフと見なしてグラフの根を探索
– 面倒・・・
• フラグ配列(orビット列)に落として勝つ手を固
定して調べる
– ジャッジの想定解法
解答例(1)
const string HAND[] = {"Rock", "Fire", "Scissors", "Snake", "Human", "Tree",
"Wolf", "Sponge", "Paper", "Air", "Water", "Dragon", "Devil", "Lightning",
"Gun"};
～中略～
map<string, int> dic;
for (int i = 0; i < 15; ++i){
dic.insert(make_pair(HAND[i], i));
}
～中略～
int state = 0;
for (int i = 0; i < n; ++i){
string hand;
cin >> hand;
state |= (1 << dic[hand]);
}
～中略～
解答例(2)
～中略～
//stateに出された手を代入
int answer = -1;
for (int hand = 0; hand < 15; ++hand){
if (state & 1){
if (!(state & ((1 << 15) - (1 << 8)))){
answer = hand;
break;
}
}
state = ((state >> 1) | ((state & 1) << 14));
}
～中略～
結果
• 初Accepted(予想)
– 30分
• 初Accepted(実際)
– 13分 kitsune-
• 結果
– 24/54 全チーム正解
間違いの例
• 全部同じ手の場合はDrawです
– “A player is said to win the game if the
player’s hand defeats at least one of the other
hands, and is not defeated by any of the other
hands.”
» 審判団も同じ間違いをしました
• O(N^2)で全探索
» 想定外の範囲
– 結果はTLEでした
• ギリギリ回る可能性もあります
皆さんのコード拝見
int mat[15][15] ={
0,-1,-1,-1,-1,-1,-1,-1,1,1,1,1,1,1,1,
1,0,-1,-1,-1,-1,-1,-1,-1,1,1,1,1,1,1,
1,1,0,-1,-1,-1,-1,-1,-1,-1,1,1,1,1,1,
1,1,1,0,-1,-1,-1,-1,-1,-1,-1,1,1,1,1,
1,1,1,1,0,-1,-1,-1,-1,-1,-1,-1,1,1,1,
1,1,1,1,1,0,-1,-1,-1,-1,-1,-1,-1,1,1,
1,1,1,1,1,1,0,-1,-1,-1,-1,-1,-1,-1,1,
1,1,1,1,1,1,1,0,-1,-1,-1,-1,-1,-1,-1,
-1,1,1,1,1,1,1,1,0,-1,-1,-1,-1,-1,-1,
-1,-1,1,1,1,1,1,1,1,0,-1,-1,-1,-1,-1,
-1,-1,-1,1,1,1,1,1,1,1,0,-1,-1,-1,-1,
-1,-1,-1,-1,1,1,1,1,1,1,1,0,-1,-1,-1,
-1,-1,-1,-1,-1,1,1,1,1,1,1,1,0,-1,-1,
-1,-1,-1,-1,-1,-1,1,1,1,1,1,1,1,0,-1,
-1,-1,-1,-1,-1,-1,-1,1,1,1,1,1,1,1,0
};
出典
• オリジナル
• 元ネタ
– RPS-15
• http://www.umop.com/rps15.htm
– pya!集まれ！じゃんけんぽん
• http://pya.cc/pyaimg/pimg.php?imgid=18091
終わりに
• ジャンケンやったことありますか？
© Copyright 2024 ExpyDoc
