結果

問題 No.43 野球の試合
コンテスト
ユーザー yukirin
提出日時 2016-03-03 16:06:58
言語 Go
(1.23.4)
結果
AC  
実行時間 6 ms / 5,000 ms
コード長 1,438 bytes
コンパイル時間 11,042 ms
コンパイル使用メモリ 241,080 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-10-10 23:27:23
合計ジャッジ時間 11,716 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 7
権限があれば一括ダウンロードができます

ソースコード

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)
	}

	// for i, r := range table[0] {
	// if r == '-' {
	// table[0][i] = 'o'
	// table[i][0] = 'x'
	// }
	// }

	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 := wins[0]
	m := make(map[int]bool)

	rank := 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