AtCoder CODE THANKS FESTIVAL 2017 (Parallel) Ｃ - Factory

目次

結論

• 優先度付きキューを使うと最小値を高速で取り出せる．

はじめに

• AtCoderで出題された問題を復習しています．

• 公式解説や上位陣による解説ブログを読んで，自分に足りなかった部分や得られた知見を消化してアウトプットしようと思います．

想定読者

• 解説を読んで解き方はわかったものの，なぜその方法を思いつけるのか？と思った方．

筆者の実力

• AtCoderのレートで茶色．

記事の特徴

• なぜその発想に至ったのか，どうしたら解法を詰められるかといった点について，筆者なりの解釈をつづります．

• 試行錯誤した過程から，得られた前提知識や着眼点を言語化していきます．

• 間違いや勘違いなどがございましたら，ご指摘・ご指導いただけると幸いです（大歓迎です）．

  • 連絡先：@k_hiro1818

問題のリンク

C - Factory (300点)

発想・解法とそれらを引きだすための方法・解釈

この問題の難しいところ

• 操作をすると最小値が変化する可能性があるため，その度に最小値を求める必要がある．この部分の計算量がボトルネックとなって，問題文の通り素直に実装すると実行時間制限を軽く超えてしまう．

考察のキモ（Key Insight）は?

• ある操作の前後の時間管理を優先度付きキューで行うことで，最小値を高速に取り出せる．

どうしたら思いつけそうか?

• ある集合の最小値や最大値を少ない計算量で取得する必要性に気がつく．

• 優先度付きキューを知っていて，言語標準ライブラリを利用するか自作のライブラリを持っている，もしくはコンテスト中に調べて利用もしくは実装する．

実装のポイントは?

• Python3の場合は，管理する集合をリストで初期化するか，heapq.heapify(x)を使用する（xは，リスト）．

• heapqで管理する対象は（少なくとも）2つ．ある要素のインデックスと回使用した後の所要時間．heappushの第2引数に渡すときにタプル型にしておく．

参考資料

docs.python.org

PythonによるAC解の一例

# -*- coding: utf-8 -*-


def main():
    from heapq import heappop
    from heapq import heappush

    n, k = map(int, input().split())
    b = [0 for _ in range(n)]
    hq = list()
    ans = 0

    for i in range(n):
        ai, bi = map(int, input().split())
        b[i] = bi

        # 操作前の所要時間とその要素のインデックスをセット
        heappush(hq, (ai, i))

    for i in range(k):
        # 最小所要時間とそのときの要素のインデックスを取り出す
        time, index = heappop(hq)
        ans += time

        # 操作後に所要時間を更新
        heappush(hq, (time + b[index], index))

    print(ans)


if __name__ == '__main__':
    main()

得られた知識・知見

• ヒープキューの存在とPython3だとライブラリをインポートするだけで使える点．

感想

• 半年ほど前（最小値を取り出すたびに，ソートを繰り返す方法でTLE）と比べると，自分なりに成長していると思います．

• 少し前に覚えた標準ライブラリのdequeと使い方が似ているなぁという印象でした．うまく使い分けていきたいところです．

参考

• 公式解説

記事を執筆された皆さまへ: 掲載不可の場合はお手数をお掛けしますが，@k_hiro1818までご一報ください．

更新履歴

• 2019/07/02 作成
• 2019/0x/xx 更新