#724659 (Go) No.1345 Beautiful BINGO

提出ソース

結果

問題	No.1345 Beautiful BINGO
ユーザー	小野寺健
提出日時	2021-12-17 14:48:06
言語	Go (1.23.4)
結果	AC
実行時間	1,832 ms / 2,000 ms
コード長	2,144 bytes
コンパイル時間	11,889 ms
コンパイル使用メモリ	223,540 KB
実行使用メモリ	6,528 KB
最終ジャッジ日時	2024-09-14 15:46:47
合計ジャッジ時間	47,645 ms
ジャッジサーバーID （参考情報）	judge2 / judge3

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	1 ms 5,248 KB
testcase_02	AC	1 ms 5,376 KB
testcase_03	AC	1 ms 5,376 KB
testcase_04	AC	1 ms 5,376 KB
testcase_05	AC	2 ms 5,376 KB
testcase_06	AC	1 ms 5,376 KB
testcase_07	AC	4 ms 5,376 KB
testcase_08	AC	2 ms 5,376 KB
testcase_09	AC	1 ms 5,376 KB
testcase_10	AC	1 ms 5,376 KB
testcase_11	AC	2 ms 5,376 KB
testcase_12	AC	1 ms 5,376 KB
testcase_13	AC	5 ms 5,376 KB
testcase_14	AC	2 ms 5,376 KB
testcase_15	AC	1 ms 5,376 KB
testcase_16	AC	1 ms 5,376 KB
testcase_17	AC	1 ms 5,376 KB
testcase_18	AC	1 ms 5,376 KB
testcase_19	AC	1 ms 5,376 KB
testcase_20	AC	1 ms 5,376 KB
testcase_21	AC	1 ms 5,376 KB
testcase_22	AC	72 ms 6,144 KB
testcase_23	AC	1,807 ms 6,528 KB
testcase_24	AC	806 ms 6,520 KB
testcase_25	AC	33 ms 5,632 KB
testcase_26	AC	358 ms 6,400 KB
testcase_27	AC	1,776 ms 6,528 KB
testcase_28	AC	33 ms 5,760 KB
testcase_29	AC	355 ms 6,528 KB
testcase_30	AC	155 ms 6,400 KB
testcase_31	AC	71 ms 6,144 KB
testcase_32	AC	7 ms 5,376 KB
testcase_33	AC	1,809 ms 6,528 KB
testcase_34	AC	16 ms 5,376 KB
testcase_35	AC	15 ms 5,376 KB
testcase_36	AC	1,819 ms 6,528 KB
testcase_37	AC	15 ms 5,376 KB
testcase_38	AC	354 ms 6,528 KB
testcase_39	AC	1,794 ms 6,528 KB
testcase_40	AC	815 ms 6,528 KB
testcase_41	AC	824 ms 6,528 KB
testcase_42	AC	2 ms 5,376 KB
testcase_43	AC	1 ms 5,376 KB
testcase_44	AC	1 ms 5,376 KB
testcase_45	AC	1 ms 5,376 KB
testcase_46	AC	1 ms 5,376 KB
testcase_47	AC	1 ms 5,376 KB
testcase_48	AC	2 ms 5,376 KB
testcase_49	AC	1 ms 5,376 KB
testcase_50	AC	1 ms 5,376 KB
testcase_51	AC	1 ms 5,376 KB
testcase_52	AC	1,792 ms 6,528 KB
testcase_53	AC	1,810 ms 6,528 KB
testcase_54	AC	1,826 ms 6,528 KB
testcase_55	AC	1,793 ms 6,528 KB
testcase_56	AC	1,811 ms 6,528 KB
testcase_57	AC	1,802 ms 6,528 KB
testcase_58	AC	1,785 ms 6,528 KB
testcase_59	AC	1,807 ms 6,528 KB
testcase_60	AC	1,789 ms 6,528 KB
testcase_61	AC	1,820 ms 6,528 KB
testcase_62	AC	1,832 ms 6,528 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

package main

import (
	"fmt"
	"bufio"
	"os"
	"sort"
	"math"
)

type Row struct {
	row map[int]bool
	diag map[int]bool
	cnt int
	col []int
	size int
}

func (this *Row) new(n int) {
	this.cnt = 0
	this.col = make([]int, n)
	this.size = 0
	this.row = make(map[int]bool)
	this.diag = make(map[int]bool)
}

func (this *Row) SetCol(A [][]int) {
	for i := 0; i < len(this.col); i++ {
		for j, _ := range this.row {
			if !this.ContainDiag(j, i) {
				this.col[i] += A[j][i]
			}
		}
	}
	sort.Ints(this.col)
	for i := 0; i < len(this.col)-1; i++ {
		this.col[i+1] += this.col[i]
	}
}

func (this *Row) SetDiag(row int, col int) {
	i := (row << 16) + col
	if _, ok := this.diag[i]; !ok {
		this.diag[i] = true
	}
}

func (this *Row) ContainDiag(row int, col int) bool {
	i := (row << 16) + col
	_, ok := this.diag[i]
	return ok
}

func Min(a int, b int) int {
	if a <= b {
		return a
	} else {
		return b
	}
}

func main() {
	r := bufio.NewReader(os.Stdin)
	w := bufio.NewWriter(os.Stdout)
    defer w.Flush()
	var N, M int
	fmt.Fscan(r, &N, &M)
	var RowSum []int = make([]int, N)
	var A [][]int = make([][]int, N)
	for i := 0; i < N; i++ {
		A[i] = make([]int, N)
		sum := 0
		for j := 0; j < N; j++ {
			var a int
			fmt.Fscan(r, &a)
			sum += a
			A[i][j] = a
		}
		RowSum[i] = sum
	}
	var ans int = math.MaxInt64
	for i := 0; i < 1 << (N+2); i++ {
		row := new(Row)
		row.new(N)
		for j := 0; j < N; j++ {
			if (i & (1 << j)) != 0 {
				row.cnt += RowSum[j]
				row.size++
			} else {
				row.row[j] = true
			}
		}
		if (i & (3 << N)) != 0 {
			for j := 0; j < N; j++ {
				if _, ok := row.row[j]; ok {
					if (i & (1 << N)) != 0 {
						row.cnt += A[j][j]
						row.SetDiag(j, j)
					}
					if (i & (1 << (N+1))) != 0 {
						if !row.ContainDiag(j, N-1-j) {
							row.cnt += A[j][N-1-j]
							row.SetDiag(j, N-1-j)
						}
					}
				}
			}
			if (i & (1 << N)) != 0 {
				row.size++
			}
			if (i & (1 << (N+1))) != 0 {
				row.size++
			}
		}
		row.SetCol(A)
		if row.size == M {
			ans = Min(ans, row.cnt)
		} else if (row.size < M && M - row.size <= N) {
			ans = Min(ans, row.cnt + row.col[M-row.size-1])
		}
	}
	fmt.Fprintln(w, ans)
}

yukicoder

結果

テストケース

ソースコード