AtCoder の問題を解くために必要な実力を付けるために作られた「典型問題」を解いていく企画として、「典型90」があります。
今回は、その内、の81問目である「Friendly Group（★5）」を解説していきたいと思います。
なにか、間違っているところなどありましたら、@EitaSugiまで、ご指導ご鞭撻の程、よろしくお願い致します！
問題名 【081 – Friendly Group（★5）】
考察
考えた内容の概要
この問題は、典型高校の生徒たちを特定の条件下でグループ化するというものです。条件は、グループ内の生徒間で身長と体重の差がK以下であることです。この制約を満たしつつ、グループの最大人数を求める必要があります。
考えたことの内容
この問題を解く鍵は、生徒の身長と体重の差を効率的に計算する方法を見つけることです。全ての生徒のペアを比較すると計算量が多くなりすぎるため、より効率的な方法を考える必要があります。
解法のポイント
- 2次元配列の活用
生徒の身長と体重を2次元配列にマッピングします。これにより、身長と体重の組み合わせごとに生徒の数をカウントすることができます。 - 制約条件の活用
身長と体重の差の絶対値が K 以下である制約を利用して、2次元配列上での探索範囲を絞り込むことができます。 - いもす法の利用
いもす法を利用して、2次元配列上での累積和を計算します。これにより、任意の範囲内の生徒の数を効率的に求めることができます。
いもす法による解法
この問題を解くためには、「いもす法」というテクニックを利用します。いもす法は、ある範囲に一定の値を加算するという操作を高速に行うための手法です。
1次元のいもす法
まず、1次元のいもす法を理解することから始めましょう。例えば、体重だけを考慮した場合を考えます。ある生徒の体重が5kgでK=2の場合、この生徒が含まれるチームのメンバーの体重は3kg~5kg or 5kg~7kgの範囲になります。
1次元のいもす法では、この範囲に+1を行い、その後累積和を取ることで、各体重に対して何人の生徒が該当するかを計算します。
2次元への拡張
この考えを2次元に拡張します。生徒の身長と体重を2次元配列上にマッピングし、\((Ai,Bi),(Ai+1+K,Bi+1+K)\)に+1、\((Ai+1+K,Bi),(Ai,Bi+1+K)\)に-1を加算します。
その後、横方向と縦方向に累積和を取ることで、任意の範囲に対する生徒の人数を計算できます。
実装した内容
この問題の解決策として、2次元配列といもす法を用いることにしました。2次元配列を使って生徒の身長と体重をマッピングし、いもす法を用いて範囲内の生徒数を効率的に計算します。これにより、身長と体重の差がK以下である生徒のペアを効率的に数え上げることができます。
コード
N,K = map(int, input().split())
leng = 5001
two_dimension_arr = [[0]*(leng+1) for i in range(leng+1)]
for i in range(N):
A,B = map(int, input().split())
mx_x,mx_y = min(leng,A+K+1),min(leng,B+K+1)
# print(111111111,mx_x,mx_y)
two_dimension_arr[A][B] += 1
two_dimension_arr[mx_x][B] -= 1
two_dimension_arr[A][mx_y] -= 1
two_dimension_arr[mx_x][mx_y] += 1
#横方向への累積
for i in range(1,leng+1):
for j in range(1,leng+1):
two_dimension_arr[i][j] += two_dimension_arr[i][j-1]
#縦方向への累積
for j in range(1,leng+1):
for i in range(1,leng+1):
two_dimension_arr[i][j] += two_dimension_arr[i-1][j]
# for x in two_dimension_arr:
# print(x)
maxv = 0
for i in range(leng):
for j in range(leng):
maxv = max(maxv,two_dimension_arr[i][j])
print(maxv)まとめ
この問題は、2次元配列といもす法を活用して、効率的に解くことができます。身長と体重の差がK以下である制約を利用して、探索範囲を絞り込むことで、計算量を削減することができます。この方法は、範囲内の要素の数を効率的に計算する必要がある他の多くの問題にも応用することができます。
コメント