結果

問題 No.43 野球の試合
ユーザー yukirinyukirin
提出日時 2016-03-03 16:09:13
言語 Go
(1.22.1)
結果
AC  
実行時間 7 ms / 5,000 ms
コード長 1,324 bytes
コンパイル時間 13,559 ms
コンパイル使用メモリ 238,172 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-10-10 23:27:46
合計ジャッジ時間 11,871 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 1 ms
6,820 KB
testcase_02 AC 1 ms
6,816 KB
testcase_03 AC 1 ms
6,816 KB
testcase_04 AC 1 ms
6,820 KB
testcase_05 AC 1 ms
6,816 KB
testcase_06 AC 1 ms
6,820 KB
testcase_07 AC 7 ms
6,820 KB
testcase_08 AC 1 ms
6,820 KB
testcase_09 AC 2 ms
6,816 KB
testcase_10 AC 1 ms
6,816 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

package main

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

var sc = bufio.NewScanner(os.Stdin)
var rdr = bufio.NewReaderSize(os.Stdin, 1000000)

func main() {
	sc.Split(bufio.ScanWords)
	n := nextInt()
	table := make([][]rune, n)
	for i := range table {
		s := nextLine()
		table[i] = []rune(s)
	}

	wins, games := make([]int, n), make([][2]int, 0, 15)
	for i, v := range table {
		for _, r := range v {
			if r == 'o' {
				wins[i]++
			}
		}
	}

	for i, v := range table[:len(table)-1] {
		for j, r := range v[i+1:] {
			if r == '-' {
				games = append(games, [2]int{i, j + i + 1})
			}
		}
	}

	fmt.Println(solve(games, wins))
}

func solve(games [][2]int, wins []int) int {
	var f func(int, []int) int
	f = func(i int, wins []int) int {
		if i == len(games) {
			return check(wins)
		}

		wins[games[i][0]]++
		rank1 := f(i+1, wins)
		wins[games[i][0]]--
		wins[games[i][1]]++
		rank2 := f(i+1, wins)
		wins[games[i][1]]--

		if rank1 < rank2 {
			return rank1
		}
		return rank2
	}
	return f(0, wins)
}

func check(wins []int) int {
	w, m, rank := wins[0], make(map[int]bool), 1
	for _, r := range wins {
		if m[r] {
			continue
		}

		m[r] = true
		if r > w {
			rank++
		}
	}
	return rank
}

func nextLine() string {
	sc.Scan()
	return sc.Text()
}

func nextInt() int {
	i, _ := strconv.Atoi(nextLine())
	return i
}
0