[Baekjoon]私の世界(18111号)

ソース

18111号

質問する

に答える

import sys

N, M, B = map(int, sys.stdin.readline().split())
board = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
ans_height, ans_time = 0, int(1e10)
max_val = 0
for i in range(len(board)):
    for j in range(len(board[0])):
        max_val = max(max_val, board[i][j])
        
for h in range(max_val, -1, -1):
    total_time, block = 0, 0
    for i in range(len(board)):
        for j in range(len(board[0])):
            if board[i][j] > h:
                total_time += (board[i][j] - h) * 2
                block += board[i][j] - h
            else:
                total_time += h - board[i][j]
                block -= h - board[i][j] 
    
    if B + block < 0:
        continue
    
    if total_time <= ans_time:
        ans_time = total_time
        ans_height = h

print(ans_time, ans_height)

最初に作成したコードは以下の通りです.ブロックを除去するのに要する時間はブロックを取り出すのに要する時間よりも長いので,初期的に高い最低点を基準に,完全ナビゲーションにより最小時間を計算した.
このアルゴリズムの時間的複雑度はO(N 2)O(N^2)O(N 2)であり,最悪256 x 500 x 500=6400000回の演算が必要であるため,このアルゴリズムは1秒で問題を通過するのに十分な時間がかかると考えられるが,これはタイムアウトを招く.
Pythonはインタラクティブな言語であるため,原因解析を行うと,他の言語よりも演算時間が長いことが分かった.
So 1 billion * 9 opcodes/112.37 seconds = about 80,092,551 opcodes per second. It’s like we’re in the 1980s!
ソース:https://www.stephanboyer.com/post/38/counting-to-a-billion
この記事は2013年に作成されたため、現在のCPUの計算量は大きくなる可能性がありますが、Pythonの速度は通常のコンパイル言語より20倍以上遅いため、より効率的なアルゴリズムやデータ構造を選択して問題を解決する必要があります.
考えてみると、ディック・シャナリーでコードを修正しました.以前は、同じ高さを1つずつナビゲートして演算していましたが、ディックシーケンスは、バッチ演算を実現するためにkeyとvalue形式で高さと個数を格納するように改良されました.
このため,演算量は256個のバイナリ長で大幅に増加し,時間的複雑度もO(N)O(N)O(N)に著しく向上した.

import sys

N, M, B = map(int, sys.stdin.readline().split())
height_dic = {}
for i in range(N):
    board = list(map(int, sys.stdin.readline().split()))
    for height in board:
        if height in height_dic.keys(): 
            height_dic[height] += 1
        else:
            height_dic[height] = 1

ans_height, ans_time = 0, int(1e10)
for h in range(257):
    total_time, block = 0, 0
    for key in height_dic.keys():
        if key > h:
            total_time += (key - h) * height_dic[key] * 2
            block += (key - h) * height_dic[key]
        else:
            total_time += (h - key) * height_dic[key]
            block -= (h - key) * height_dic[key]
   
    if B + block < 0:
        continue
    
    if total_time <= ans_time:
        ans_time = total_time
        ans_height = h
        
print(ans_time, ans_height)

時間の複雑さ

O(N)O(N)O(N)

実行結果