[CAKA 202]挿入広告

もんだいぶんせき

「Jordie」の動画再生時間はplay time、公益広告の再生時間はadv time、視聴者がこの動画の区間情報logsをパラメータとして再生する場合、視聴者が累計再生時間が最も多い場所に公益広告を挿入したいと思います.このとき,公益広告の開始時刻を要求し,解関数を完了して返す.視聴者の累計再生時間が最も多い場所が複数ある場合は、その中で最も速い開始時間に戻ってください.
すなわち、プレイタイム全体において、視聴者が視聴する開始点と終了点がlogsに格納される.
広告を再生する際に、視聴時間をできるだけ多く蓄積する広告開始時間.

試行錯誤

文字列の時間を

に変換

logsは、開始、終了の順に並べられ、観客の開始時間に応じてadv timeサイズのウィンドウを移動する.

ウィンドウで、対応する他の観客の時間を合わせて、最大露出時間の起点を見つけます.

def change(h, m, s):
    return (h * 3600 + m * 60 + s)

def solution(play_time, adv_time, logs):
    h, m, s = map(int, play_time.split(':'))
    play_time = change(h, m, s)

    h, m, s = map(int, adv_time.split(':'))
    adv_time = change(h, m, s)
    
    temp = []
    for val in logs:
        s_t, e_t = val.split('-')
        h, m, s = map(int, s_t.split(':'))
        s_time = change(h, m, s)
        h, m, s = map(int, e_t.split(':'))
        e_time = change(h, m, s)
        temp.append((s_time, e_time))
    logs = temp
    
    logs.sort(key = lambda x : (x[0], x[1]))
    
    answer = 0
    
    length = len(logs)
    
    max_val = -(1e9)
    for i in range(length):
        s, e = logs[i]
        adv_end = s + adv_time
        if adv_end > play_time: continue
        
        sum_val = 0
        for j in range(i, length):
            s2, e2 = logs[j]
            if s2 > adv_end: break
            if adv_end > e2: sum_val += (e2 - s2)
            else :sum_val += (adv_end - s2)
        if sum_val > max_val:
            max_val = sum_val
            answer = s
    h = answer // 3600
    answer %= 3600
    h = str(h)
    
    m = answer // 60
    answer %= 60
    m = str(m)
    
    s = answer
    s = str(s)
    
    if len(h) == 1: h = "0" + h
    if len(m) == 1: m = "0" + m
    if len(s) == 1: s = "0" + s
        
    return (h + ":" + m + ":" + s)

に質問
1.視聴者の開始時間に正解が保証されない.

この場合、観覧開始時間は90時間になります.90+50は100を超えるので、回答候補に入れないので、私のコードは0:0:0です.
しかし、最後に10時間を含む50時間が正解だ.
そこで、私なりに問題を解決するには、視聴開始時間だけでなく、視聴終了時間も考えなければなりません.

時間の複雑さが高すぎます.
logsは30万の大きさの配列です.
私のコードの時間複雑度は開始時間数n*以降の時間数です
(n-1) + (n-2) + ... 1後Oになります(n^2).実行回数は900億回に達した.
1番によって観客の終了時間を考えれば、千億を超える実行回数がある.

正解

kakao公式ブログで回答を確認しました.

def change(h, m, s):
    return (h * 3600 + m * 60 + s)

def solution(play_time, adv_time, logs):
    #문자열을 숫자로 변경
    h, m, s = map(int, play_time.split(':'))
    play_time = change(h, m, s)

    h, m, s = map(int, adv_time.split(':'))
    adv_time = change(h, m, s)
    
    temp = []
    for val in logs:
        s_t, e_t = val.split('-')
        h, m, s = map(int, s_t.split(':'))
        s_time = change(h, m, s)
        h, m, s = map(int, e_t.split(':'))
        e_time = change(h, m, s)
        temp.append((s_time, e_time))
    logs = temp
    
    #play_time 만큼의 배열 도입해. 시청 시작, 시청 종료 시점 기록.
    visited = [0] * (play_time + 1)
    for s, e in logs:
        visited[s] += 1
        visited[e] -= 1
    
    #각 시점에 시청 중인 시청자 수 기록
    for i in range(1, play_time):
        visited[i] = visited[i] + visited[i-1]
    
    #0부터 해당시점까지의 누적시청자 수 기록
    for i in range(1, play_time):
        visited[i] = visited[i] + visited[i-1]

    most_view = 0
    max_time = 0
    for i in range(adv_time - 1, play_time):
        if i >= adv_time:
            if most_view < visited[i] - visited[i - adv_time]:
                most_view = visited[i] - visited[i - adv_time]
                max_time = i - adv_time + 1
        else:
            if most_view < visited[i]:
                most_view = visited[i]
                max_time = i - adv_time + 1
            
    answer = max_time
    h = answer // 3600
    answer %= 3600
    h = str(h)
    
    m = answer // 60
    answer %= 60
    m = str(m)
    
    s = answer
    s = str(s)
    
    if len(h) == 1: h = "0" + h
    if len(m) == 1: m = "0" + m
    if len(s) == 1: s = "0" + s
        
    return (h + ":" + m + ":" + s)

ぶんせき

すべての文字列を

という数字に変更します.

play timeの配列を導入した後、観客のスタート地点で+1.終了点では-1で表します.

より前の値を現在の値に加算し、現在の時点の視聴者数を表示します.
ex)開始点+1,終了点-1である.その間は1です.終了後はゼロです.

より前の値に現在値をもう一度加算し、現在の時点での累計視聴者数を表示します.
累計視聴者数に変更しない場合は、すべての区間についてadv timeのウィンドウを使用して合計する必要があるため、タイムアウトが発生します.

特定区間のadv timeの視聴者数は、[i]-アクセス[i-adv time]によって得ることができる.最大値のi-adv timeを求めればよい.

区間の開始・終了点に+1,-1を表示した後,区間の内部値を積算して求める.
累積減算により区間内合を求めることができる.