トップページ -> AOJの解答例 -> DSL_5の解答例

DSL_5の解答例(Python)

直線・平面上にシールを張ることを考え，シールの重なりが最大になっている場所の枚数を求めるような問題です．

1. DSL_5_A: The Maximum Number of Customers

入店時間と退店時間が与えられます．最も店内に人が多いときの人数を求める問題です．


# DSL_5_A
N,T = map(int,input().split())

time_table = [0 for _ in range(10**5+1)]
for _ in range(N):
    l,r = map(int,input().split())
    time_table[l] += 1
    time_table[r] -= 1

pre_num = 0
current_num = 0
ans = 0
for i,t in enumerate(time_table):
    current_num = pre_num + t
    pre_num = current_num
    ans = max(current_num,ans)
    
print(ans)

2. DSL_5_B: The Maximum Number of Overlaps

二次元の領域にシールを張り，重なっている枚数が最大になっている場所の枚数を求める問題です． Aを二次元に拡張して考えます．これでは間に合いませんが，やりたいことはAを1000行分処理したいだけです．(0 0 1000 1000 などは縦方向に1を並べる操作に1000回かかってしまいます)


# DSL_5_B
# これでは間に合わない
N = int(input())

time_table = [[0]*1001 for _ in range(1001)]
add_dict = {}
minus_dict ={}
for _ in range(N):
    x1,y1,x2,y2 = map(int,input().split())
    # 縦方向に1を並べる
    for y in range(y1,y2):
        time_table[y][x1] += 1
        time_table[y][x2] -= 1

# Aと同じことを1000行分やる
ans = 0
for table in time_table:
    pre_num = 0
    current_num = 0
    for i,t in enumerate(table):
        current_num = pre_num + t
        pre_num = current_num
        ans = max(current_num,ans)

print(ans)

(0 0 1000 1000)をN回入力されるとN*1000かかってしまい上のコードでは終わりません．入力に関わらず1000*1000で終わるように横方向だけでなく縦方向にもAの考え方を用いることで計算量を減らしました．


    # DSL_5_B
N = int(input())

table = [[0]*1001 for _ in range(1001)]
add_dict = {}
minus_dict ={}
for _ in range(N):
    x1,y1,x2,y2 = map(int,input().split())
    table[y1][x1] += 1
    table[y1][x2] -= 1
    
    table[y2][x1] -= 1
    table[y2][x2] += 1
    
# 縦方向に1が並ぶようにする
for i in range(1000):
    for j in range(1001):
        table[i+1][j] += table[i][j] # -1が出てくるまでは1が並ぶ
        
# 横方向に1が並ぶようにする
ans = 0
for i in range(1001):
    for j in range(1000):
        table[i][j+1] += table[i][j] # -1が出てくるまでは1が並ぶ
        ans = max(ans,table[i][j])

print(ans)

<- 前へ戻る【目次に戻る】