#724659 (Go) No.1345 Beautiful BINGO

提出ソース

結果

問題	No.1345 Beautiful BINGO
ユーザー	小野寺健
提出日時	2021-12-17 14:48:06
言語	Go (1.22.1)
結果	AC
実行時間	1,818 ms / 2,000 ms
コード長	2,144 bytes
コンパイル時間	12,931 ms
コンパイル使用メモリ	213,852 KB
実行使用メモリ	7,348 KB
最終ジャッジ日時	2023-10-12 17:11:36
合計ジャッジ時間	49,443 ms
ジャッジサーバーID （参考情報）	judge12 / judge15

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 4,352 KB
testcase_01	AC	2 ms 4,368 KB
testcase_02	AC	1 ms 4,372 KB
testcase_03	AC	1 ms 4,372 KB
testcase_04	AC	2 ms 4,372 KB
testcase_05	AC	2 ms 4,372 KB
testcase_06	AC	1 ms 4,372 KB
testcase_07	AC	4 ms 4,372 KB
testcase_08	AC	1 ms 4,372 KB
testcase_09	AC	2 ms 4,372 KB
testcase_10	AC	1 ms 4,372 KB
testcase_11	AC	2 ms 4,372 KB
testcase_12	AC	2 ms 4,372 KB
testcase_13	AC	4 ms 4,368 KB
testcase_14	AC	2 ms 4,372 KB
testcase_15	AC	1 ms 4,376 KB
testcase_16	AC	1 ms 4,372 KB
testcase_17	AC	2 ms 4,372 KB
testcase_18	AC	2 ms 4,372 KB
testcase_19	AC	2 ms 4,368 KB
testcase_20	AC	2 ms 4,372 KB
testcase_21	AC	2 ms 4,368 KB
testcase_22	AC	73 ms 6,552 KB
testcase_23	AC	1,799 ms 6,872 KB
testcase_24	AC	793 ms 6,848 KB
testcase_25	AC	33 ms 6,216 KB
testcase_26	AC	361 ms 7,188 KB
testcase_27	AC	1,798 ms 6,864 KB
testcase_28	AC	32 ms 6,228 KB
testcase_29	AC	355 ms 6,860 KB
testcase_30	AC	155 ms 6,804 KB
testcase_31	AC	73 ms 6,552 KB
testcase_32	AC	7 ms 4,372 KB
testcase_33	AC	1,787 ms 6,892 KB
testcase_34	AC	14 ms 4,372 KB
testcase_35	AC	15 ms 4,372 KB
testcase_36	AC	1,790 ms 6,872 KB
testcase_37	AC	15 ms 4,372 KB
testcase_38	AC	354 ms 6,864 KB
testcase_39	AC	1,787 ms 6,872 KB
testcase_40	AC	794 ms 6,852 KB
testcase_41	AC	795 ms 6,848 KB
testcase_42	AC	1 ms 4,376 KB
testcase_43	AC	1 ms 4,368 KB
testcase_44	AC	1 ms 4,372 KB
testcase_45	AC	1 ms 4,376 KB
testcase_46	AC	1 ms 4,368 KB
testcase_47	AC	1 ms 4,372 KB
testcase_48	AC	2 ms 4,368 KB
testcase_49	AC	1 ms 4,372 KB
testcase_50	AC	1 ms 4,376 KB
testcase_51	AC	2 ms 4,372 KB
testcase_52	AC	1,790 ms 6,868 KB
testcase_53	AC	1,818 ms 7,344 KB
testcase_54	AC	1,784 ms 7,324 KB
testcase_55	AC	1,788 ms 6,872 KB
testcase_56	AC	1,783 ms 6,864 KB
testcase_57	AC	1,790 ms 6,860 KB
testcase_58	AC	1,789 ms 7,348 KB
testcase_59	AC	1,788 ms 6,868 KB
testcase_60	AC	1,798 ms 6,864 KB
testcase_61	AC	1,810 ms 6,864 KB
testcase_62	AC	1,799 ms 6,872 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

結果

テストケース

ソースコード