Cで新人女子に褒めてもらう #paizahack_01 - Qiita

成績 背景や課題の詳細は https://paiza.jp/poh/ec-campaign を参照してください。#paizahack_01 当初のアルゴリズム 普通に全商品の組合せで最適解を求めようとすると、$O(DN^2)$になってしまいます（paiza作成の模範解答はこれなのでcase1しか通らない）。それを避け、$O(DN\log N)$にするため、次のように二分探索を使いました。 ごく普通にscanf()で入力 ごく普通に商品価格リストをqsort()でソート 各キャンペーン価格につき以下を実行 各商品につき、対になる価格をもつ商品を二分探索 それらのうち最適値を表示 しかし、このコードではcase3がタイムアウトしてしまうという恥ずかしい結果に。急遽、性能を手元で定量化できるように、case3相当のベンチマーク用入力を作成し、チューニングを開始しました。 最終形態への道 探索の改