結果

問題 No.90 品物の並び替え
ユーザー seiichiseiichi
提出日時 2021-01-06 15:55:08
言語 Go
(1.22.1)
結果
AC  
実行時間 945 ms / 5,000 ms
コード長 2,217 bytes
コンパイル時間 14,622 ms
コンパイル使用メモリ 223,956 KB
実行使用メモリ 59,008 KB
最終ジャッジ日時 2024-04-24 16:48:18
合計ジャッジ時間 15,356 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 83 ms
8,576 KB
testcase_02 AC 1 ms
5,376 KB
testcase_03 AC 9 ms
5,376 KB
testcase_04 AC 9 ms
5,376 KB
testcase_05 AC 84 ms
8,576 KB
testcase_06 AC 84 ms
8,576 KB
testcase_07 AC 2 ms
5,376 KB
testcase_08 AC 1 ms
5,376 KB
testcase_09 AC 945 ms
59,008 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

package main

import (
	"fmt"
	"strconv"
)

func scan() (N int, M int, scoreMap map[string]int) {
	scoreMap = map[string]int{}
	fmt.Scan(&N, &M)
	for i := 0; i < M; i++ {
		var item1, item2 string
		var score int
		fmt.Scan(&item1, &item2, &score)
		key := item1 + "," + item2
		scoreMap[key] = score
	}
	return
}

func permutaions(arr []int) (res [][]int) {
	var helper func([]int, int)

	helper = func(arr []int, n int) {
		if n == 1 {
			tmp := make([]int, len(arr))
			copy(tmp, arr)
			res = append(res, tmp)
		} else {
			for i := 0; i < n; i++ {
				helper(arr, n-1)
				if n%2 == 1 {
					tmp := arr[i]
					arr[i] = arr[n-1]
					arr[n-1] = tmp
				} else {
					tmp := arr[0]
					arr[0] = arr[n-1]
					arr[n-1] = tmp
				}
			}
		}
	}

	helper(arr, len(arr))
	return res
}

func main() {
	N, _, scoreMap := scan()
	// N, _, scoreMap := 4, 9, map[string]int{
	// 	"0,1": 1,
	// 	"0,2": 2,
	// 	"0,3": 3,
	// 	"1,2": 4,
	// 	"1,3": 5,
	// 	"2,3": 6,
	// 	"3,2": 100,
	// 	"2,1": 100,
	// 	"1,0": 100,
	// }

	// N, _, scoreMap := 8, 4, map[string]int{
	// 	"0,1": 227,
	// 	"0,2": 5525,
	// 	"0,4": 9497,
	// 	"0,5": 4472,
	// 	"0,6": 7066,
	// 	"1,0": 2440,
	// 	"1,2": 181,
	// 	"1,3": 1277,
	// 	"1,5": 3233,
	// 	"1,6": 6134,
	// 	"1,7": 5211,
	// 	"2,0": 7250,
	// 	"2,4": 1445,
	// 	"2,5": 8823,
	// 	"2,7": 3310,
	// 	"3,0": 3114,
	// 	"3,1": 5979,
	// 	"3,2": 6712,
	// 	"3,5": 848,
	// 	"3,6": 9264,
	// 	"3,7": 4941,
	// 	"4,0": 5479,
	// 	"4,3": 5900,
	// 	"4,5": 1677,
	// 	"4,6": 7070,
	// 	"4,7": 432,
	// 	"5,0": 8783,
	// 	"5,1": 7180,
	// 	"5,4": 3333,
	// 	"5,6": 4513,
	// 	"5,7": 7044,
	// 	"6,0": 1823,
	// 	"6,5": 2551,
	// 	"6,7": 4808,
	// 	"7,0": 8413,
	// 	"7,1": 125,
	// 	"7,2": 3497,
	// 	"7,3": 4161,
	// 	"7,5": 598,
	// 	"7,6": 6403,
	// }

	var items []int
	for i := 0; i < N; i++ {
		items = append(items, i)
	}
	perms := permutaions(items)

	var maxScore int
	for _, per := range perms {
		tmpMaxScore := 0
		for i := 0; i < len(per)-1; i++ {
			for j := i + 1; j < len(per); j++ {
				key := strconv.Itoa(per[i]) + "," + strconv.Itoa(per[j])
				tmpMaxScore += scoreMap[key]
			}
		}
		if tmpMaxScore > maxScore {
			maxScore = tmpMaxScore
		}
	}

	fmt.Print(maxScore)
}
0