ラージろりがぽんぽんついたかみかざりしてるのすきトーナメント
転じて、Large ろり（R）がぽんぽん（P）ついた髪飾りしてるのすき（S）Tournamentの意味。
元ネタの問題名に含まれるRPSは、じゃんけんの英名 ”Rock Paper Scissors”の頭文字を取ってきたものだが、そこに勝手に新しく意味を割り振った。
https://gyazo.com/a0ec6bd4c455e2c286cba1b7e2a07788
ちなみに、watabosi (わたぼし)氏の同人誌「びーうぃずゆぅ！」において、ひーとけろけろつり目ガールのケガした友だちを治療するためのばんそうこう早取り出し対決では、けろけろつり目ガールに軍配が上がっている。 ちなみに、ろりの正しいつづりは"Loli"。語呂合わせを優先するためにLとRを入れ替えるという、だぼだぼレインコートショタと同じ現象が起きている。 ここからは、Large RPS Tournamentの解き方について解説する。
問題概要
参加者が$ 2^{k}人のクソでかじゃんけんトーナメント大会をする。全ての参加者は必ず毎回同じ手を出し、参加者$ iの出す手は、与えられる文字列$ Sの長さを$ nとして、$ Sの$ (i ~mod ~n)番目の文字がRならグーを、Pならパーを、Sならチョキである。あいことなった場合は、どちらか好きな方が次のトーナメントに進出する。
トーナメントの優勝者が出す手はなにか？？？ただし$ kは最大で$ 100となるため、人が多すぎて1試合ずつ計算することはできない。
制約
- 文字列$ Sの長さは最大で$ 100、つまり$ n \leq 100
-$ k \leq 100
考察
問題の意味をつかんだり、キモとなる考え方を見つけるために、具体例を見ながら観察してみよう。
例えば、$ S=RPS、$ k = 2のとき、$ n = 3である。このときのトーナメント表は、
code:example.k2.txt
P
┌─┴─┐
P R
┌┴┐ ┌┴┐
R P S R
となり、優勝者が出す手はPとわかる。
$ Sはそのままに、今度は$ k = 3のときのトーナメント表を見てみよう。
code:example.k3.txt
S
┌───┴───┐
P S
┌─┴─┐ ┌─┴─┐
P R S P
┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐
R P S R P S R P
となり、優勝者が出す手はSとわかる。
同様に、$ k = 4,5のときのトーナメント表も見てみよう。
code:example.k4.txt
S
┌───────┴───────┐
S P
┌───┴───┐ ┌───┴───┐
P S R P
┌─┴─┐ ┌─┴─┐ ┌─┴─┐ ┌─┴─┐
P R S P R S P R
┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐
R P S R P S R P S R P S R P S R
code:example.k5.txt
R
┌───────────────┴───────────────┐
S R
┌───────┴───────┐ ┌───────┴───────┐
S P R S
┌───┴───┐ ┌───┴───┐ ┌───┴───┐ ┌───┴───┐
P S R P S R P S
┌─┴─┐ ┌─┴─┐ ┌─┴─┐ ┌─┴─┐ ┌─┴─┐ ┌─┴─┐ ┌─┴─┐ ┌─┴─┐
P R S P R S P R S P R S P R S P
┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐
R P S R P S R P S R P S R P S R R P S R P S R P S R P S R P S R
これくらいやると、以下の重要な事実に気が付けるはずだ。
その試合が何回戦目であっても、同じトーナメントの階層において、$ n個隣の試合で出されている手は全く同じ。つまり、その試合の勝者も同じ。
例えば、$ k=5の場合、$ n=3であるので、
code:example.k5.txt
R
┌───────────────┴───────────────┐
┌───────┴───────┐ ┌───────┴───────┐
┌───┴───┐ ┌───┴───┐ ┌───┴───┐ ┌───┴───┐
┌─┴─┐ ┌─┴─┐ ┌─┴─┐ ┌─┴─┐ ┌─┴─┐ ┌─┴─┐ ┌─┴─┐ ┌─┴─┐
┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐
[R P S R P S/R P S R P S/R P S R P S/R P S R P S/R P S R P S/R P
という風に。
これは、第1回戦での左から$ i番目の試合は$ 2i-1,2i人目、左から$ i+n番目の試合は$ 2(i+n)-1,2(i+n)人目での
戦いとなり、$ 2i-1 \equiv 2(i+n)-1,2i \equiv 2(i+n) ~(mod ~n)であることから各参加者の出す手が全く同じであることに起因している。
この議論を各階層ごとに帰納的に適用することで、どの階層についても同じことがいえる。
対戦カードが同じということは、各試合について勝者となる手も同じということであり、各階層において左から$ n試合、
つまり左から$ 2n人分の出す手を管理しておけば、それらが繰り返し並んでいると考えればよいので、全ての試合を計算したことになる。この$ 2n人の勝負をシミュレーションするのを$ k回繰り返した後の、左から$ 1番目の人の手が優勝者の手である。
なお、人数が減って$ 2n人以下になった場合でも、存在している人数分へのシミュレートへの影響はないので、$ 2n人いる時と同じように扱って構わない。
この解き方での計算回数は、$ k層のトーナメントそれぞれについて$ n試合をシミュレートすればよいので、大体$ nk回となる。これは最大で$ 10,000回程度で、十分現実的な範囲だ。
よって、この問題を解くことができた。
解答例（C++）
じゃんけんのパートは別の関数に分けて書いてあげると、main関数が簡潔になり見やすい。
code:answer.cpp
using namespace std;
// 各プレイヤーの出す手を受け取って、勝つ方の手を返す関数
char rps(char a, char b) {
string win = "RSP";
if (win.find(a) == (win.find(b) + 1) % 3) {
return b;
} else {
return a;
}
}
int main() {
int n, k;
string s;
cin >> n >> k >> s;
string battle = s + s;
for(int round = 0; round < k; round++) {
string winners = "";
for(int card = 0; card < n; card++) {
}
swap(battle, winners);
battle += battle;
}
}