#1151527 (Go) No.3471 ジャッジサーバーの負荷分散

• 問題: No.3471 ジャッジサーバーの負荷分散
• ユーザー: yuki2006
• 提出日時: 2026-03-06 20:47:50
• 言語: Go (1.25.7)
• 結果: AC
• 実行時間: 155 ms / 2,000 ms
• コード長: 6,944 bytes
• コンパイル時間: 16,967 ms
• コンパイル使用メモリ: 279,768 KB
• 実行使用メモリ: 22,904 KB
• 最終ジャッジ日時: 2026-03-06 20:51:05
• 合計ジャッジ時間: 12,072 ms
• ジャッジサーバーID （参考情報）: judge3 / judge2

ファイルパターン	結果
sample	AC * 3
other	AC * 15

ソースコード

package main

import (
	"bufio"
	"container/heap"
	"fmt"
	"io"
	"os"
	"strconv"
	"strings"
)

// PriorityQueue を初期化してアイテムを追加
//pq := make(PriorityQueue, 0, len(items))
//heap.Init(&pq)
//for value, priority := range items {
//	heap.Push(&pq, &Item{
//		value:    value,
//		priority: priority,
//	})
//}

// Item はプライオリティキューに格納する要素です。
type Item struct {
	value    interface{} // 格納する任意の値
	priority int         // 優先度（小さいほど高い優先度）
	index    int         // ヒープ内での現在のインデックス（内部利用）
}

// PriorityQueue は heap.Interface を実装するプライオリティキューです。
type PriorityQueue []*Item

// Len はキュー内の要素数を返します。
func (pq PriorityQueue) Len() int {
	return len(pq)
}

// Less は、要素の順序を決めます。
// 優先度が小さいほうを先頭にするため、pq[i].priority < pq[j].priority とします。
func (pq PriorityQueue) Less(i, j int) bool {
	return pq[i].priority < pq[j].priority
}

// Swap は、2 つの要素を入れ替えます。
func (pq PriorityQueue) Swap(i, j int) {
	pq[i], pq[j] = pq[j], pq[i]
	pq[i].index = i
	pq[j].index = j
}

// Push は、新しい要素をキューに追加します。
func (pq *PriorityQueue) Push(x interface{}) {
	n := len(*pq)
	item := x.(*Item)
	item.index = n
	*pq = append(*pq, item)
}

// Pop は、キューから最も優先度が高い（＝値が小さい）要素を取り出します。
func (pq *PriorityQueue) Pop() interface{} {
	old := *pq
	n := len(old)
	item := old[n-1]
	// メモリリーク防止のため、nil を代入
	old[n-1] = nil
	item.index = -1
	*pq = old[0 : n-1]
	return item
}

// Update は、既存のアイテムの値と優先度を変更し、ヒープを再調整します。
func (pq *PriorityQueue) Update(item *Item, value interface{}, priority int) {
	item.value = value
	item.priority = priority
	heap.Fix(pq, item.index)
}

func main() {
	sc := NewScanner(os.Stdin)
	pr := NewPrinter(os.Stdout)
	defer pr.writer.Flush()
	_, M := sc.NextInt(), sc.NextInt()
	T := sc.NextIntSlice()

	servers := make([]int, M)
	pq := make(PriorityQueue, 0)
	heap.Init(&pq)
	for range servers {
		heap.Push(&pq, &Item{value: 0, priority: 0})
	}
	for _, runTime := range T {
		server := heap.Pop(&pq).(*Item)
		value := server.priority + runTime
		heap.Push(&pq, &Item{
			value:    value,
			priority: value,
		})
	}
	for {
		ss := heap.Pop(&pq).(*Item)
		if len(pq) == 0 {
			fmt.Println(ss.value)
			break
		}
	}

}

// Scanner は入力を効率的に読み取るためのカスタム構造体です。
// 内部で bufio.Reader を利用し、1行読み込んだ後に tokens に分割して管理します。
type Scanner struct {
	reader *bufio.Reader
	tokens []string
	pos    int
}

// NewScanner は与えられた io.Reader から Scanner を生成します。
func NewScanner(r io.Reader) *Scanner {
	return &Scanner{reader: bufio.NewReader(r)}
}

// NextString は空白区切りの次のトークンを返します。
// 内部にトークンがなければ新たに1行読み込み、tokens に分割して返します。
func (s *Scanner) NextString() string {
	if s.pos < len(s.tokens) {
		token := s.tokens[s.pos]
		s.pos++
		return token
	}
	// トークンがない場合は新たに行を読み込む
	for {
		line, err := s.reader.ReadString('\n')
		if err != nil {
			// エラー時も部分的に読み込んだ行があれば処理する
			line = strings.TrimRight(line, "\r\n")
			if len(line) > 0 {
				s.tokens = strings.Fields(line)
				s.pos = 0
				if len(s.tokens) > 0 {
					token := s.tokens[s.pos]
					s.pos++
					return token
				}
			}
			panic(err)
		}
		line = strings.TrimRight(line, "\r\n")
		if len(line) == 0 {
			continue // 空行はスキップ
		}
		s.tokens = strings.Fields(line)
		s.pos = 0
		if len(s.tokens) > 0 {
			token := s.tokens[s.pos]
			s.pos++
			return token
		}
	}
}

// NextInt は次のトークンを整数に変換して返します。
func (s *Scanner) NextInt() int {
	token := s.NextString()
	val, err := strconv.Atoi(token)
	if err != nil {
		panic(err)
	}
	return val
}

func (s *Scanner) NextIntSlice() []int {
	split := strings.Split(s.NextLine(), " ")

	n := len(split)
	slice := make([]int, n)
	for i := 0; i < n; i++ {
		slice[i], _ = strconv.Atoi(split[i])
	}
	return slice
}

// NextLine は、未消化のトークンがあればそれらを結合して返すか、
// もしくは新たに1行丸ごと読み込んで返します。
func (s *Scanner) NextLine() string {
	if s.pos < len(s.tokens) {
		line := strings.Join(s.tokens[s.pos:], " ")
		s.tokens = nil
		s.pos = 0
		return line
	}
	line, err := s.reader.ReadString('\n')
	if err != nil {
		return strings.TrimRight(line, "\r\n")
	}
	return strings.TrimRight(line, "\r\n")
}

// Printer は出力を効率的に行うためのカスタム構造体です。
// 内部で bufio.Writer を利用しています。
type Printer struct {
	writer *bufio.Writer
}

// NewPrinter は与えられた io.Writer から Printer を生成します。
func NewPrinter(w io.Writer) *Printer {
	return &Printer{writer: bufio.NewWriter(w)}
}

// Print は引数をそのまま出力します（改行なし）。
func (p *Printer) Print(a ...interface{}) {
	s := fmt.Sprint(a...)
	p.writer.WriteString(s)
}

// Println は引数をスペース区切りで出力し、最後に改行を付けます。
func (p *Printer) Println(a ...interface{}) {
	s := fmt.Sprintln(a...)
	p.writer.WriteString(s)
}

// Printf はフォーマットに従って出力します。
func (p *Printer) Printf(format string, a ...interface{}) {
	s := fmt.Sprintf(format, a...)
	p.writer.WriteString(s)
}

// PrintIntSlice は整数のスライスをスペース区切りで出力し、最後に改行を付けます。
func (p *Printer) PrintIntSlice(slice []int) {
	for i, v := range slice {
		if i > 0 {
			p.writer.WriteString(" ")
		}
		p.writer.WriteString(strconv.Itoa(v))
	}
	p.writer.WriteString("\n")
}

// PrintStringSlice は文字列のスライスをスペース区切りで出力し、最後に改行を付けます。
func (p *Printer) PrintStringSlice(slice []string) {
	p.writer.WriteString(strings.Join(slice, " "))
	p.writer.WriteString("\n")
}

// Ordered は、順序比較が可能な型の制約です。
// チルダ記法(~)を用いて、基底型が同じ型を含むようにしています。
type Ordered interface {
	~int | ~int8 | ~int16 | ~int32 | ~int64 |
		~uint | ~uint8 | ~uint16 | ~uint32 | ~uint64 | ~uintptr |
		~float32 | ~float64 |
		~string
}

// Min は、2 つの値のうち小さい方を返します。
func Min[T Ordered](a, b T) T {
	if a < b {
		return a
	}
	return b
}

// Max は、2 つの値のうち大きい方を返します。
func Max[T Ordered](a, b T) T {
	if a > b {
		return a
	}
	return b
}