じゃんけんの手の出し方 (paizaランク A 相当)をJavaScriptで解きました

by .

　こちらはコード公開が可能なpaizaのレベルアップ問題集の「じゃんけんの手の出し方」というAランク相当の問題をFITSの代表である藤浦が挑戦した記録です。読み進めるとJavaScript版の解答コードが載っているのでご注意ください。

問題へのリンクはこちら

問題のルールを読み違えてハマる

　例題として出ている手が「例えば、あなたが 4 回のじゃんけんで グー、パー、チョキ、グー と出したとすると、出した指の本数の合計は、0 + 5 + 2 + 0 = 7 」となっていて、続く入力のサンプルが

4 7
CGPC

という全勝パターンだったので（引き分けや負けについて言及されてないし、勝った場合の指数のみカウントすればよいのか）と勘違いしました。実務でもそうですが、ソロでのコーディングで思い込みが発生してしまうとリカバリに苦労しますね。

なお、続く入力例2は

5 10
GPCPC

でした。なので普通に考えると5回のじゃんけんで出した指数の合計が10になるのは「パー2回、グー3回」あるいは「チョキ5回」の二通りしかありません。ここで（あいこや負けも考慮した指の数になるのだな）と気づくべきでした。

　ここが思い込みの怖いところで（この問題では、どのような組み合わせで勝っても、勝った際の指数の合計が10になることがない。パーで2回勝つことができない）の後の発想として（本来はGPCPGとするところをGPCPCとしてしまったのかな？）と考えました。この時点で一発クリアの目は消えたのですが、自戒も込めてここからの四苦八苦も記載します。

勝ち負けを順列再帰で網羅する？（組み合わせ爆発）

　N回のじゃんけんに対し、相手の手が固定されているため１回目が価値、2回目が負け・・・N回目が負け、というように勝ち負けの順列のパターン網羅による回答を出そうとしました。その中で全ての手の指数が前提条件と同じものを抽出すれば一応は回答となります。

　（勝ちの場合の指数のみカウントしようと勘違いしているのでこの段階でクリアは出来ないのですが）これは少し考えただけで組み合わせ爆発となる事がわかります。N=1000回であれば再帰で確実にスタックがあふれますし、このアプローチだと解けそうにないことは分かったまま、いったん休憩しました。競技プログラミングでは休憩は敷居が高いですが、業務プログラミングであれば休憩中に回答を思いつくことがままあります。

順列ではなく組み合わせの問題であることに気づく

　少し思考を整理して、そもそも1回目にパーで勝つことと3回目にパーで勝つことを問題の性質上区別する必要はない（どちらも指数+5となるだけ）ため、何回目に何を出したか、という順列の問題ではなく、単純にじゃんけんの総回数N回に対してグーをG回出したとき、かつ、パーをP回出したとき、といった組み合わせの問題であることにようやく気付きました。（ここにいたってもまだ、勝ち手の指の数のみを数えてます）

　この段階で書き上げたコードが下記です。

  // 勝ち手の合計の指数
  [,finger] = lines.shift().split(" ").map(i=>Number(i));
  hands = lines.shift().split("");
  // 勝ち手（相手がチョキなら勝ち手はグー）の最大数をカウント
  gCount = hands.filter(h => h == 'C').length;
  pCount = hands.filter(h => h == 'G').length;
  cCount = hands.filter(h => h == 'P').length;
  win = 0;  
  for (i = 0; i <= pCount; i++) {
      for (k = 0; k <= cCount; k++) {
          if (i * 5 + k * 2 == finger) {
              win = Math.max(win, i + k)
          }
      }
  }
  // グーによる勝ちはそのまま勝利数に加算
  win += gCount;
  console.log(win)

　当然このコードでは、偶然にも解答が全勝時のパターンである入力例1は通過しますが、提出後の問題は1問目から不正解（0点）となりました。

paizaの機能で入力をオープンして勘違いに気づく

　paizaのレベルアップ問題集には、スキルチェックの本番問題にはない機能として、実際の入力値を確かめる機能があります（チケット消費が必要）。そこで入力をオープンしてようやく気付きます。これ、勝ちだけじゃなく「あいこ」も「負け」も指数をカウントしないとダメなやつじゃないか・・・。

コードを修正して再提出、100点通過へ

　これで回答にたどり着くための条件はすべて揃いました。まず、ループはじゃんけんの回数 total 内でグーの回数（G回）、チョキの回数、パーの回数（P回）を網羅できるよう、2次元ループとします（GとPが分かればチョキの回数は求まるため、3次元ではなく2次元ループです）。

　また「あなたは最高で何回じゃんけんに勝つことができるでしょうか」の一文から、指数が同じでも多く勝てる組み合わせがあれば、そちらを採用します。また、グーで何回勝てるか？パーで何回勝てるか？は相手の出した手による制限が掛かります。例えばトータルの指数 finger が10であれば、パーを2回か、チョキを5回出す必要があるのですが、相手がパーを3回しか出してないのであればこのチョキ5回のうち3回までしか勝ちにカウントできません。これはMath.min で（自分がチョキを出した回数、相手がパーを出した回数）の小さいほうを採用することで、相手の手を超えて勝つことを防ぎます。

　グーチョキパーのそれぞれについてこの矛盾しない勝ち数を計算してwinに代入した上で、前回計算した win を上回る場合は win を更新していきます。

  // 合計じゃんけん数、合計の指数
  [total, finger] = lines.shift().split(" ").map(i => Number(i));
  hands = lines.shift().split("");
  // 各手で勝てる最大数をカウント
  gMax = hands.filter(h=>h=='C').length;
  pMax = hands.filter(h=>h=='G').length;
  cMax = hands.filter(h=>h=='P').length;
  win = 0;
  // グーの数とパーの数をループで網羅し、チョキの数はじゃんけん数から導かれる
  for (g = 0; g <= total; g++) {
    for (p = 0; p <= total - g; p++) {
      c = total - g - p;
      if(p * 5 + c * 2 == finger) {
        // 指の数が問題と一致なら、勝ち数の多いほうを採用
        win = Math.max(win, Math.min(g, gMax) + Math.min(p, pMax) + Math.min(c, cMax));
      }
    }
  }
  console.log(win)

　上記のコードで100点となりました。楽しかったです！レベルアップ問題集は、難易度自体は高ランクのものもありますが、期限が切られてないためのんびりと対応できるのが素晴らしいですね。いざとなったら入力そのものを確認できますし、ネットで解説記事も検索することもできるため、高ランク問題を確実に解いて考え方を身に着けたい、という場合には重宝するのではないでしょうか。

最後に（宣伝）

　FITSは仙台にあるシステム開発会社です！社長が趣味でpaizaを解いていたり、役職が全撤廃されているほか、地方のIT会社には珍しくしっかりとしたインセンティブ制度があります。インセンティブ制度により年収ベースで社長を超える社員も居ます。

　また、働きやすさを追求したリモートワーク制度やスーパーフレックス制度も整備されています。自分の実力に対して見合う報酬が支払われていない、柔軟に働けずもやもやしている、という方は、是非FITSでエンジニアとして働いてみませんか？アルバイトも募集しています。

　採用情報はこちらです。