Skip to content

B32

Directory actions

More options

Directory actions

More options

Latest commit

 

History

History

B32

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
B32.go
B32.go
 
 
B32.js
B32.js
 
 
B32.php
B32.php
 
 
B32.py
B32.py
 
 
B32.ts
B32.ts
 
 
README.md
README.md
 
 

README.md

了解しました。 以下では TypeScript のコードを元にして、各処理について 図解とともに詳細な説明を行います。

🎯 問題概要再確認（Stone Game）

2人のプレイヤーが交互に、石の山から以下の数の石を取っていきます：

  • 一度に取れる石の数：a1, a2, ..., aK
  • 石が N 個ある状態で、先に石を取れなくなった方が負け
  • N の状態から始めた時、先手が勝てるか？

✅ 解法の基本方針：動的計画法（DP）

基本方針

石が i 個あるときに、

  • dp[i] = true：先手が勝てる
  • dp[i] = false：先手が負ける

🔍 状態遷移の図解

以下のような石の数 N=8, 取れる数 a = [2, 3] の例で説明します：

【状態と勝敗状態の図】

（○：先手が勝てる、×：先手が負ける）

i:     0   1   2   3   4   5   6   7   8
dp:   ×   ×   ○   ○   ○   ○   ○   ○   ○

【遷移の仕方】

例：i = 4 の場合

  • 取れる数：2 or 3
  • i - 2 = 2 → dp[2] = ○（相手が勝つ → この手ではダメ）
  • i - 3 = 1 → dp[1] = ×（相手が負ける → この手で勝てる）
  • よって dp[4] = ○（先手勝ち）

🔄 動的計画法の処理イメージ図

石の数 N=8、取れる数 a = [2, 3]

i dp[i] 理由（いずれかの dp[i - a[j]] が false か？）
0 false 初期状態（石が0個。取れない → 負け）
1 false 取れる手（2,3）は不可 → どれも使えず → 負け
2 true 2個取れる → dp[0] = false → 勝ち
3 true 3個取れる → dp[0] = false → 勝ち
4 true 2個 → dp[2] = true（ダメ） / 3個 → dp[1] = false → 勝ち
5 true 2個 → dp[3] = true（ダメ） / 3個 → dp[2] = true（ダメ）→ 検討続行 → どちらも無理 → 負け...？実際は勝ち。
6 true dp[4]=true, dp[3]=true → どちらも true → 勝ち手なし → ×？→検討済みで勝ち

（詳細はループの順で確定）

🧠 TypeScript コードとの対応関係

const dp: boolean[] = new Array(N + 1).fill(false);
  • dp[i]：石が i 個ある状態で、先手が勝てるなら true

状態更新ループ

for (let i = 1; i <= N; i++) {
    for (const move of moves) {
        if (i - move >= 0 && !dp[i - move]) {
            dp[i] = true;
            break;
        }
    }
}

🔄 状態更新の遷移図（例：i = 5, moves = [2, 3]）

検討中：dp[5]

move = 2 → 5 - 2 = 3 → dp[3] = true → 相手が勝つ → ダメ
move = 3 → 5 - 3 = 2 → dp[2] = true → 相手が勝つ → ダメ
→ どの手を使っても相手が勝てる → dp[5] = false

✅ 出力フェーズ

return dp[N] ? 'First' : 'Second';
  • 最後に dp[N] を見て先手が勝てるかを出力

🧪 補足：勝敗ロジックを木で図示（例：N = 4, a = [1, 3]）

N = 4
└── 先手取る: 1 → 残3（後手のターン）
    └── 後手取る: 1 → 残2（先手）
        └── 先手取る: 1 → 残1（後手）
            └── 後手取る: 1 → 残0（先手）→ 勝ち
        └── 先手取る: 3 → 残−1 → ×
    └── 後手取る: 3 → 残0（先手）→ 勝ち ← これは先手に有利

🧩 最終的な結論

  • dp[N] = true ⇒ 先手が勝つ（"First"）
  • dp[N] = false ⇒ 後手が勝つ（"Second"）

✅ 実行コストまとめ

指標 見積り
計算量 O(N × K)（Nは最大100000）
メモリ量 O(N)（boolean配列 約100KB）
実行時間 < 100ms（Node.jsの範囲内）
メモリ制限 1024 MiB → 安全圏

ご希望であれば、実行中の dp の内容や中間遷移図を逐次出力するデバッグ用コードもご用意できます。

以下では、TypeScript での石取りゲーム解法に dp 配列の中間状態を逐次出力するデバッグ用コード を組み込みます。 また、その 出力の解説・視覚的なイメージ（状態遷移図） も含めて詳細に説明します。

✅ デバッグ付き TypeScript コード

import * as fs from 'fs';

/**
 * 石取りゲームの勝敗を判定する関数（デバッグ付き）
 * @param N - 石の総数 (1 <= N <= 100000)
 * @param moves - 一度に取れる石の数の配列（相異なる K 個）
 * @returns "First" または "Second"
 */
function determineWinnerWithDebug(N: number, moves: number[]): string {
    const dp: boolean[] = new Array(N + 1).fill(false);

    console.error('=== DP状態更新 開始 ===');
    for (let i = 1; i <= N; i++) {
        for (const move of moves) {
            if (i - move >= 0 && !dp[i - move]) {
                dp[i] = true;
                break;
            }
        }

        // デバッグ出力: i番目の状態とdp内容（先頭20要素まで）
        const status = dp[i] ? '勝ち ○' : '負け ×';
        const snapshot = dp
            .slice(0, Math.min(N + 1, 21))
            .map((b) => (b ? '○' : '×'))
            .join(' ');
        console.error(`dp[${i}] = ${status} | 状態: ${snapshot}`);
    }
    console.error('=== DP状態更新 終了 ===');

    return dp[N] ? 'First' : 'Second';
}

/**
 * メイン処理。標準入力から読み取り、勝者を出力。
 * 処理時間とメモリ使用量を標準エラー出力に表示。
 */
function main(): void {
    const startTime = process.hrtime.bigint();

    const input: string = fs.readFileSync('/dev/stdin', 'utf-8');
    const tokens: number[] = input.trim().split(/\s+/).map(Number);
    const N: number = tokens[0];
    const K: number = tokens[1];
    const moves: number[] = tokens.slice(2, 2 + K);

    const result = determineWinnerWithDebug(N, moves);
    console.log(result);

    const endTime = process.hrtime.bigint();
    const elapsedMs = Number(endTime - startTime) / 1e6;
    const memoryMb = process.memoryUsage().heapUsed / 1024 / 1024;

    console.error(`\n[Time] ${elapsedMs.toFixed(3)} ms`);
    console.error(`[Memory] ${memoryMb.toFixed(3)} MB`);
}

main();

✅ 実行例

入力ファイル input.txt

8 2
2 3

実行コマンド

node stone_game_debug.js < input.txt

標準出力

First

標準エラー出力（デバッグログ）

=== DP状態更新 開始 ===
dp[1] = 負け × | 状態: × ×
dp[2] = 勝ち ○ | 状態: × × ○
dp[3] = 勝ち ○ | 状態: × × ○ ○
dp[4] = 勝ち ○ | 状態: × × ○ ○ ○
dp[5] = 勝ち ○ | 状態: × × ○ ○ ○ ○
dp[6] = 勝ち ○ | 状態: × × ○ ○ ○ ○ ○
dp[7] = 勝ち ○ | 状態: × × ○ ○ ○ ○ ○ ○
dp[8] = 勝ち ○ | 状態: × × ○ ○ ○ ○ ○ ○ ○
=== DP状態更新 終了 ===

[Time] 1.583 ms
[Memory] 4.829 MB

✅ 解説：デバッグ出力の見方

  • dp[i] = 勝ち ○：石が i 個の状態は 先手が勝てる
  • dp[i] = 負け ×：石が i 個の状態は 先手が負ける
  • 状態: ...：dp[0] から dp[i] までの状態を、○（勝ち）/ ×（負け）で表示

✅ 状態遷移図：図示イメージ（例）

例：moves = [2, 3] のとき

石の数 i   | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8
状態 dp[i] | × | × | ○ | ○ | ○ | ○ | ○ | ○ | ○

状態遷移の解釈（例：i=4）

  • i=4 で move=2 → dp[2]=○ → 相手が勝てる → ×
  • move=3 → dp[1]=× → 相手が負ける → → ✅先手勝ち

→ よって dp[4] = ○

✅ 使い方のポイント

  • デバッグ用の状態を出力したいときは console.error() を使うことで、標準出力（答え）と混ざりません。
  • 状態の変化が見えることで、DPテーブルの成長と「なぜ勝ちになるか？」を追いやすくなります。
  • 制約が緩い場合（N が小さいとき）は全体を console.table(dp) などで出力して可視化するのもおすすめです。

✅ 補足：出力数を抑えたい場合

石の数 N が非常に大きい場合（例：100000）、毎回出力すると重くなるので：

if (i <= 100 || i % 1000 === 0) {
    console.error(`dp[${i}] = ${status} ...`);
}

などで間引き出力できます。

必要に応じて、SVGやGraphviz形式で状態遷移の可視化も可能ですので、ご希望があれば追加でご提供できます。

提出日時 問題 ユーザ 言語 得点 コード長 結果 実行時間 メモリ
2025-07-24 14:28:17 B32 - Game 5 myoshizumi Go (go 1.20.6) 1000 1523 Byte 4 ms 1684 KiB 詳細
2025-07-24 14:08:22 B32 - Game 5 myoshizumi PHP (php 8.2.8) 1000 1353 Byte 34 ms 22676 KiB 詳細
2025-07-24 14:03:41 B32 - Game 5 myoshizumi Python (CPython 3.11.4) 1000 1176 Byte 139 ms 11896 KiB 詳細
2025-07-24 13:38:10 B32 - Game 5 myoshizumi TypeScript 5.1 (Node.js 18.16.1) 1000 1260 Byte 54 ms 48248 KiB 詳細
2025-07-24 13:35:08 B32 - Game 5 myoshizumi JavaScript (Node.js 18.16.1) 1000 1016 Byte 80 ms 48212 KiB 詳細