Submission #67864327

---

Source Code Expand

package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)

// determineWinner は石の総数 N と取り方 moves に基づき、勝者を返す関数です。
// N: 石の総数（1 <= N <= 100000）
// moves: 一度に取れる石の数のスライス（1 <= ai <= 100000, 相異なる）
// 戻り値: "First"（先手勝ち）または "Second"（後手勝ち）
func determineWinner(N int, moves []int) string {
	dp := make([]bool, N+1) // dp[i] = 石i個の状態で先手が勝てるならtrue

	for i := 1; i <= N; i++ {
		for _, move := range moves {
			if i-move >= 0 && !dp[i-move] {
				dp[i] = true
				break
			}
		}
	}

	if dp[N] {
		return "First"
	}
	return "Second"
}

// readInts は文字列の行をスペース区切りの整数スライスに変換する関数です。
func readInts(line string) ([]int, error) {
	fields := strings.Fields(line)
	nums := make([]int, len(fields))
	for i, field := range fields {
		n, err := strconv.Atoi(field)
		if err != nil {
			return nil, err
		}
		nums[i] = n
	}
	return nums, nil
}

// main 関数：標準入力から読み込み、勝者を出力、処理時間とメモリも出力
func main() {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Scan()
	headerLine := scanner.Text()
	header, _ := readInts(headerLine)
	N, _ := header[0], header[1]

	scanner.Scan()
	moveLine := scanner.Text()
	moves, _ := readInts(moveLine)

	result := determineWinner(N, moves)
	fmt.Println(result)
}

Submission Info

Judge Result