paizaラーニングレベルアップ問題集の「じゃんけんの手の出し方」をやってみた

paiza×Qiita記事投稿キャンペーンということで、paizaラーニングレベルアップ問題集の[じゃんけんの手の出し方](https://paiza.jp/works/mondai/a_rank_skillcheck_sample/janken)をやってみました。今回はC言語で書いていきます。
- - -
Aランク問題、Sランク問題となると、計算量を意識しなければなりません。
###### N重ループ
$1$回目のじゃんけんでグーを出す場合、チョキを出す場合、パーを出す場合
$2$回目のじゃんけんでグーを出す場合、チョキを出す場合、パーを出す場合
（中略）
$N$回目のじゃんけんでグーを出す場合、チョキを出す場合、パーを出す場合
として考えてみましょう。全部で$3^N$通りの組み合わせがあります。
```c
#include <stdio.h>

//最大値を更新する
int chmax(int* a, int b){
    if(b>*a)*a=b;
    return *a;
}

/*
 * n重ループを再帰関数で実現する
 * n: じゃんけんの回数
 * enemy: 相手の手の出し方
 * k: じゃんけんが終わった回数
 * player: 自分の手の出し方。先頭k文字がGCPのいずれかで埋まっている。
 * m: 出すべき指の合計数
 */
int janken(int n, const char* enemy, int k, char* player, int m){
    if(k==n){//n回じゃんけんが終わった
        //出した指の本数の合計
        int finger=0;
        for(int i=0;i<n;i++){
            if(player[i]=='P')finger+=5;
            if(player[i]=='C')finger+=2;
        }
        
        //合計が指定本数と一致しなかったら-1を返却する
        if(finger!=m)return -1;

        //勝利回数をカウントする
        int win=0;
        for(int i=0;i<n;i++){
            if(player[i]=='G' && enemy[i]=='C')win++;//自分がグー、相手がチョキ
            if(player[i]=='C' && enemy[i]=='P')win++;//自分がチョキ、相手がパー
            if(player[i]=='P' && enemy[i]=='G')win++;//自分がパー、相手がグー
        }
        return win;
    }

    //k回目に出す手がグー、チョキ、パーそれぞれについて再帰
    int max_win=0;
    player[k]='G';
    chmax(&max_win,janken(n,enemy,k+1,player,m));
    player[k]='C';
    chmax(&max_win,janken(n,enemy,k+1,player,m));
    player[k]='P';
    chmax(&max_win,janken(n,enemy,k+1,player,m));
    return max_win;
}

int main(){
    int n,m;
    scanf("%d %d",&n,&m);
    char s[n+1];
    scanf("%s",s);
    char t[n];
    printf("%d\n",janken(n,s,0,t,m));
    return 0;
}
```
以上のコードを[paiza.io](https://paiza.io/)で実行したところ、$N=16$で約$1$秒かかりました。以降、$N$が$1$増加する毎に処理時間は$3$倍以上になります。$N=1000$では$10^{462}$年以上かかることになります。
- - -
###### 三重ループ
実は、相手が出す手の順番は関係ありません。
相手のグー、チョキ、パーの数をカウントし、
```math
勝利回数=\min(自分のグー, 相手のチョキ)+\min(自分のチョキ, 相手のパー)+\min(自分のパー, 相手のグー)
```
の、自分のグー、チョキ、パーを出す回数についてループさせた最大値を計算します。
```c
#include <stdio.h>

//2つの整数の大きくない方を返す
int min(int a, int b){
    return a<b?a:b;
}

//最大値を更新する
int chmax(int* a, int b){
    if(b>*a)*a=b;
    return *a;
}

int main(){
    int n,m;
    scanf("%d %d",&n,&m);
    char s[n+1];
    scanf("%s",s);

    //相手のグー、チョキ、パーの回数
    int G=0,C=0,P=0;
    for(int i=0;i<n;i++){
        if(s[i]=='G')G++;
        if(s[i]=='C')C++;
        if(s[i]=='P')P++;
    }
    
    int max_win=0;
    for(int g=0;g<=n;g++){//自分のグーの回数を0からnまでループ
        for(int c=0;c<=n;c++){//自分のチョキの回数を0からnまでループ
            for(int p=0;p<=n;p++){//自分のパーの回数を0からnまでループ
                //回数が合わなければスキップ
                if(g+c+p!=n)continue;
                //指の合計本数が合わなければスキップ
                if(2*c+5*p!=m)continue;
        		//勝利回数を計算し、多くなれば最大値を更新する
                chmax(&max_win,min(g,C)+min(c,P)+min(p,G));
            }
        }
    }
    //最大勝利回数を更新する
    printf("%d\n",max_win);
    return 0;
}
```
以上のコードを[paiza.io](https://paiza.io/)で実行したところ、$N=10^3$の時約$1$秒で終わりました。しかし、まだムダが多いプログラムに見えませんか。
- - -
###### 一重ループ
じゃんけんの回数$N$、出す指の合計本数$M$の2つのパラメータが与えられていますので、グー、チョキ、パーのいずれか1つを出す回数を決めれば、他の2つの手を出す回数は一意に決まります。
ここでは、パーを出す回数でループさせることにします。
この時、$M-5\times(パーの回数)$が偶数でないと、チョキを出す回数が整数になりません。そこで、
- $M$が偶数の時…パーの回数が偶数
- $M$が奇数の時…パーの回数が奇数

の時をループさせるようにします。
```c
#include <stdio.h>

//2つの整数の大きくない方を返す
int min(int a, int b) {
	return a < b ? a : b;
}

//最大値を更新する
int chmax(int *a, int b) {
	if (b > *a)
		*a = b;
	return *a;
}

int main() {
	int n, m;
	scanf("%d %d", &n, &m);
	char s[n + 1];
	scanf("%s", s);

	//相手のグー、チョキ、パーの回数
	int G = 0, C = 0, P = 0;
	for (int i = 0; i < n; i++) {
		if (s[i] == 'G')
			G++;
		else if (s[i] == 'C')
			C++;
		else if (s[i] == 'P')
			P++;
	}

	int max_win = 0;
	for (int p = m % 2; p <= m / 5; p += 2) { //パーの回数についてループさせる
		//チョキの回数
		int c = (m - 5 * p) / 2;
		if (c > n)
			continue;

		//グーの回数
		int g = n - (c + p);
		if (g < 0)
			continue;

		//勝利回数を計算し、多くなれば最大値を更新する
		chmax(&max_win, min(g, C) + min(c, P) + min(p, G));
	}

	//最大勝利回数を出力する
	printf("%d\n", max_win);
	return 0;
}
```
以上のコードを[paiza.io](https://paiza.io/)で実行したところ、$N=10^3$の時でも$0.01$秒未満で終わりました。
- - -
ここで、パーを出す回数のループの終了値は、本来は$\min\left(N,\lfloor\frac{M}{5}\rfloor\right)$なのですが、$\lfloor\frac{M}{5}\rfloor$でよいです（プログラムでは$N$,$M$を小文字の`n`,`m`で書いています）。
なぜなら、制約条件より、「$N$回のじゃんけんでちょうど$M$本の指を出すじゃんけんの仕方が少なくとも一通り存在する」とありますので、$M>5N$ならそのような手の出し方は一通りもありません。したがって、$M\le 5N$すなわち$\lfloor\frac{M}{5}\rfloor\le\frac{M}{5}\le N$であり、$\min\left(N,\lfloor\frac{M}{5}\rfloor\right)=\lfloor\frac{M}{5}\rfloor$が成立します。

パーの回数$p\le\frac{M}{5}$より、チョキの回数$c=\frac{M-5p}{2}\ge0$及びグーの回数$g=N-(c+p)\le N$は保証されています。よって、その判定条件は省略しています。
また、ループの$1$ステップで、パーの回数$p$が$2$増加すると、チョキの回数$c$は$5$減少、グーの回数$g$は$3$増加します。$p$の値が小さい間は$c>N$または$g<0$の可能性がありますので、`continue`でスキップするようにしています。$p$がある程度増加すると、$c\le N$かつ$g\ge 0$を満たすようになります。
- - -
`assert`を入れたソースコードを置いておきます。
```c
#include <stdio.h>
#include <assert.h>

//2つの整数の大きくない方を返す
int min(int a, int b) {
	return a < b ? a : b;
}

//最大値を更新する
int chmax(int *a, int b) {
	if (b > *a)
		*a = b;
	return *a;
}

int main() {
	int n, m;
	scanf("%d %d", &n, &m);
	assert(m <= n * 5);
	char s[n + 1];
	scanf("%s", s);

	//相手のグー、チョキ、パーの回数
	int G = 0, C = 0, P = 0;
	for (int i = 0; i < n; i++) {
		if (s[i] == 'G')
			G++;
		else if (s[i] == 'C')
			C++;
		else if (s[i] == 'P')
			P++;
	}

	int max_win = 0;
	for (int p = m % 2; p <= m / 5; p += 2) { //パーの回数についてループさせる
		//チョキの回数
        assert((m - 5 * p) % 2 == 0);
		int c = (m - 5 * p) / 2;
    	assert(c >= 0);
		if (c > n)
			continue;

		//グーの回数
		int g = n - (c + p);
    	assert(g <= n);
		if (g < 0)
			continue;

		//勝利回数を計算し、多くなれば最大値を更新する
		chmax(&max_win, min(g, C) + min(c, P) + min(p, G));
	}

	//最大勝利回数を出力する
	printf("%d\n", max_win);
	return 0;
}
```
- - -
テストデータ作成コードを置いておきます。（定数$N$及び式$m$は適宜変えてください）
```c
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
const int N = 1000;
int main() {
	srand((unsigned int) time(NULL));
	int m = 7 * N / 3;
	printf("%d %d\n", N, m);
	for (int i = 0; i < N; i++)
		putchar("GCP"[rand() % 3]);
	puts("");
	return 0;
}
```