1.質問

ヒョン市の具在賢(ク・ジェヒョン)市長はこの数年間、ガリマン・デリンを通じて自分の党のために有利な選挙区を画定した.権力を牽制しなかった具在賢の権力行使は不当で、詩の名前まで再現詩に変えた.今度の選挙では、できるだけ公平に選挙区を画定するつもりです.
再生サイズN×N人格で表すことができます.グリッド内の各セルは領域を表し、r行c列の領域は(r,c)と表すことができる.領域は5つの選挙区に分割され、各選挙区は5つの選挙区のうちの1つを含む必要があります.選挙区には少なくとも1つの区が含まれ、1つの選挙区に含まれる区がつながっていなければならない.A区からB区までは、2つの区がつながっているそうです.中間通の隣接領域は0以上で、いずれも同じ選択領域に含まれる領域であるべきである.
選挙区を区切る方法は以下の通りです.

基準点(x,y)と境界長d 1,d 2を決定する.
(d1, d2 ≥ 1, 1 ≤ x < x+d1+d2 ≤ N, 1 ≤ y-d1 < y < y+d2 ≤ N)

次の欄は警戒線です.

(x, y), (x+1, y-1), ..., (x+d1, y-d1)

(x, y), (x+1, y+1), ..., (x+d2, y+d2)

(x+d1, y-d1), (x+d1+1, y-d1+1), ... (x+d1+d2, y-d1+d2)

(x+d2, y+d2), (x+d2+1, y+d2-1), ..., (x+d2+d1, y+d2-d1)

境界線と境界線の奥は第5選挙区です.

5選択領域に含まれない領域(r,c)の選択領域番号は、以下の基準に従う.

1選挙区:1≦r

2選挙区:1≦r≦x+d 2,y

3選挙区:x+d 1≦r≦N,1≦c

4選挙区:x+d 2

以下のサイズは7です.×これは7人再生市を5つの選挙区に分ける方法の例である.

地域(r,c)の人口はA[r][c]であり、選挙区の人口は選挙区内のすべての地域に含まれる人口の総和である.選挙区を区分する方法では、人口が最も多い選挙区と人口が最も少ない選挙区の人口差の最大値を探し出す.

せいげんじょうけん

時間:1秒
メモリ:512 MB
5 ≤ N ≤ 20
1 ≤ A[r][c] ≤ 100

入力

1行目は再生時のサイズNを与える.
2行目からN行にはN個の整数がある.r行c列の整数はA[r][c]を表す.

しゅつりょく

1行目は、人口が最も多い選挙区と人口が最も少ない選挙区の最大差を出力します.

-キーワード

無知に答えたら、答えが出ます.Breutforceを使いましょう

2.解答

初めてこの問題を見たとき、どうやって1秒で解決するか悩んでいました.
5番エリアに現れたすべての状況でしか考えられないのはブルトリーだけだ.
それ以外の方法は思い出せない.
さらに重要なのは、形が正方形ではなく、諸説ある方形なので、論理が思いつかないことです.
他の人の考えを知るために、グーグル圏を回った結果、本当に無知な答えが正解だった.
まず、この問題の核心は、すべての状況の数、すなわち5番地域を基準に評価することである.
5番エリアの警戒線

(x, y), (x+1, y-1), ..., (x+d1, y-d1)

(x, y), (x+1, y+1), ..., (x+d2, y+d2)

(x+d1, y-d1), (x+d1+1, y-d1+1), ... (x+d1+d2, y-d1+d2)

(x+d2, y+d2), (x+d2+1, y+d2-1), ..., (x+d2+d1, y+d2-d1)

と説明していましたが、この問題を初めてやったときに頭がオーバーロードするのは普通・・・
簡単に言えば、x,yは矩形の先端である.
d 1,d 2は左端長、右端長である.
つまり1番は左上、2番は右上、3番は左下、4番は右下です.
次のテストケースを見てみましょう.
8
1 2 3 4 5 6 7 8
2 3 4 5 6 7 8 9
3 4 5 6 7 8 9 1
4 5 6 7 8 9 1 2
5 6 7 8 9 1 2 3
6 7 8 9 1 2 3 4
7 8 9 1 2 3 4 5
8 9 1 2 3 4 5 6
まず,我々が探索する部分は(x,y)を基準とするので,この部分を探索するだけでよい.

赤色部分では,特定のx,yを基準として左下から最大長さを探索する.
例(3,5)で試してみます.
(3,5)できるだけ左下をチェックします.

到着した場所を全部貯蔵する.

そして、最初の場所と訪問先を基準に右下の探索を行います.



到着した場所を順次保存する.
他の場所も同様に探索を行い,訪問した場所を保存する.



最初の赤いエリアから始めて、すべての場所で探求しました.
保存した内容を基准に、地域ごとに人口计算を行います.
たとえば、現在検索されている(3,5)部分を計算します.

これは先ほど探索して貯蔵した警戒線の末端です.
この部分を基準に1、2、3、4地区の人口を計算する.
計算する前に総人口を計算します.
それから地域人口を計算します.

そして第五区の人口を計算します.
総人口-(1号地区+2号地区区+3号地区区+4号地区区)が入手しやすい
このプロセスが繰り返されるすべての5番地域の状況の数だけでよい.本当に無知な方法だ.

3.ソースコード

import sys
input = sys.stdin.readline

# 5번 지역구 구역 찾기
def find_divide(N,board,row,col):
	half = [] # 위 그리고 왼쪽 점 저장
	result = [] # 4점 저장
	for d1 in range(1,N//2+1):
		if 0 <= row+d1 < N and 0 <= col-d1 < N:
			half.append([row+d1,col-d1])
		else:
			break
	for d2 in range(1,N//2+1):
		for i in half:
			r,c = i
			if 0 <= row+d2 < N and 0 <= col+d2 < N and 0 <= r+d2 < N and 0 <= c+d2 < N:
				result.append([(row,col),(r,c),(row+d2,col+d2),(r+d2,c+d2)])
			else:
				break
	return result 

def city1(N,board,u,l): # 왼쪽 위 지역구 계산
	people = 0
	end = u[1]
	for row in range(l[0]):
		if row >= u[0]:
			end -= 1
		for col in range(end+1):
			people += board[row][col]
	return people

def city2(N,board,u,r): # 오른쪽 위 지역구 계산
	people = 0
	start = u[1]+1
	for row in range(r[0]+1):
		if row > u[0]:
			start += 1
		for col in range(start,N):
			people += board[row][col]
	return people

def city3(N,board,d,r): # 오른쪽 아래 지역구 계산
	people = 0
	start = r[1]
	for row in range(r[0]+1,N):
		for col in range(start,N):
			people += board[row][col]
		if start != d[1]:
			start -= 1
	return people

def city4(N,board,d,l): # 왼쪽 아래 지역구 계산
	people = 0
	end = l[1]
	for row in range(l[0],N):
		for col in range(end):
			people += board[row][col]
		if end < d[1]:
			end += 1
	return people

def solution(N,board):
	divide = []
	for row in range(N):
		for col in range(1,N):
			divide += find_divide(N,board,row,col)

	people = 0
	for i in board:
		people += sum(i)

	answer = people
	for i in divide:
		u,l,r,d = i
		
		max_p,min_p = 0,1e9 # 최대 인구수와 최소 인구수
		p1 = city1(N,board,u,l)
		max_p = max(p1,max_p)
		min_p = min(p1,min_p)
        
		p2 = city2(N,board,u,r)
		max_p = max(p2,max_p)
		min_p = min(p2,min_p)
        
		p3 = city3(N,board,d,r)
		max_p = max(p3,max_p)
		min_p = min(p3,min_p)
        
		p4 = city4(N,board,d,l)
		max_p = max(p4,max_p)
		min_p = min(p4,min_p)
        
		p5 = people - (p1+p2+p3+p4)
		max_p = max(p5,max_p)
		min_p = min(p5,min_p)
        
		answer = min(answer,max_p-min_p)
	return answer

if __name__ == "__main__":
	N = int(input())
	board = []
	for _ in range(N):
		board.append(list(map(int,input().split())))
	print(solution(N,board))

4.後期

テスト出力を削除しなかったためエラーと判定されたが,このプロセスはのんびりしているようだ.
Breutforceは使いたくありませんが、標本が小さいので、先に解いてみたいと思います.
実際には、エンタープライズ・エンコード・テストでは表示されませんが、無知に試してみることもあります.
考えてみる必要があると思います.決してこのように出てはいけない.