問題
あなたのビンゴカードと、主催者によって呼び上げられた M - 1 個の整数が与えられます。最後の整数が自分の思い通りに呼び上げられたとしたとき、そのときのビンゴ数の最大値を答えてください。
入力
N M
b_{1, 1} b_{1, 2} ... b_{1, N}
b_{2, 1} b_{2, 2} ... b_{2, N}
...
b_{N, 1} b_{N, 2} ... b_{N, N}
a_1
a_2
...
a_{M-1}
・1 行目にビンゴカードの縦・横のサイズを表す整数 N と、主催者が数字を呼び上げる回数 M がこの順で半角スペース区切りで与えられます。
・続く N 行のうちの i 行目 (1 ≦ i ≦ N) には N 個の整数が半角スペース区切りで与えられます。i 行目の j 番目 (1 ≦ j ≦ N) の整数 b_{i, j} は、あなたのビンゴカードの i 行 j 列目に書かれている整数を表します。
・続く M - 1 行のうちの k 行目 (1 ≦ k ≦ M - 1) には、主催者によって k 番目に呼び上げられた整数 a_k が与えられます。
・入力は合計で N + M 行となり、入力値最終行の末尾に改行が 1 つ入ります。
入力例
入力例1
5 17
1 18 4 19 14
17 3 25 11 6
23 12 16 2 21
10 24 22 8 9
5 20 7 13 15
11
19
14
15
12
22
13
23
24
7
20
5
18
9
4
25
出力
期待する出力
最大のビンゴ数を整数で出力してください。
条件
すべてのテストケースにおいて、以下の条件をみたします。
・3 ≦ N ≦ 50
・1 ≦ M ≦ N × N
・各 i, j (1 ≦ i ≦ N, 1 ≦ j ≦ N) について
・1 ≦ b_{i, j} ≦ N × N
・b_{i, j} はすべて相異なる。すなわち, 各 i', j' (1 ≦ i' ≦ N, 1 ≦ j' ≦ N) について i ≠ i' または j ≠ j' のとき b_{i, j} ≠ b_{i', j'}
・各 k (1 ≦ k ≦ M - 1) について
・1 ≦ a_k ≦ N × N
・a_k はすべて相異なる。すなわち、各 k' (1 ≦ k' ≦ M - 1) について k ≠ k' のとき a_k ≠ a_k'
回答コード
input_lines=gets.split(" ").map(&:to_i)
N = input_lines[0] # N x N
nums=N*N #1 ~ N x N
bingo_num=[*(1..nums)] # 扱いやすいように配列を用意
selected_cnt=input_lines[1]
row=Array.new(N).map{Array.new(N,0)} #横
col=Array.new(N).map{Array.new(N,0)} #縦
naname=Array.new(2).map{Array.new(N,0)} #斜め それぞれ二次元配列で初期化して準備
N.times {|i| row[i] =gets.split(" ").map(&:to_i) } # 先に標準入力で単純な横の列を配列に入れ込んだ
N.times do|i|
N.times do|j|
col[i][j] = row[j][i] # 横の配列から縦と斜めをそれぞれ抽出
naname[0][i] = row[i][j] if (i==j)
naname[1][i] = row[i][j] if (i+j == N-1)
end
end
retu =[]
retu << row << col << naname #全組合せを後ほど使いやすいように一つにぶち込んで一段階平坦化して縦横斜めの概念の無い配列
retu.flatten!(1)
#-----ここまででたてよこななめの配列それぞれ完成-------
selected=[] #呼ばれた数の配列
selected_cnt.times {|i| selected[i] =gets.to_i } #標準入力から
non_selected=[] #呼ばれて無い数の配列
selected.each do|i| #全数から呼ばれた数を引いた
bingo_num.delete(i)
end
non_selected = bingo_num
#ビンゴメソッド・・・呼ばれていたらカウント+1、カウントがN個溜まったらBINGO リターンで1
def bingo(retu , selected)
count=0
bingo = false
N.times do|i|
selected.size.times do |j|
count += 1 if retu[i]==selected[j]
end
if count == N
bingo = true
end
end
return 1 if bingo == true
end
ans=0 #答の初期化
non_selected.each do |n| #これから呼ばれる最後の数をそれぞれ
bingo_cnt=0
selected << n
retu.each do |r| #全組合せの検証 bingoメソットで1が帰ってきたらビンゴ数+1
if bingo(r,selected) == 1
bingo_cnt += 1
end
end
ans = [ans , bingo_cnt].max #答えに代入して一番ビンゴ数が多いのが答最終的に一番多いのがansに代入されるはず
selected.delete(n)
end
p ans