mayoko’s diary

プロコンとかいろいろ。

2016-01-30から1日間の記事一覧

SRM 481 div1 hard: TicketPrinters

問題 TopCoder Statistics - Problem Statement 解法 2 つ解法があるみたいですが, とりあえず DP 解で書きました。topcoder の 解説に他の解(最大マッチングに持ち込む)があったので, そっちにも少し触れます(書いてないので言ってることが正しいかわかりま…

SRM 481 div1 med: BatchSystemRoulette

問題 TopCoder Statistics - Problem Statement 解法 div2 hard と同じく, 各ユーザーごとに, 合計時間が短いやつ順に並べるのが最適です。 mayokoex.hatenablog.com 合計時間ごとに並べるので, あるユーザー u が使いたい合計時間 total 未満で処理が終わる…

SRM 481 div2 hard: BatchSystem

問題 TopCoder Statistics - Problem Statement 解法 user ごとに, タスクの合計時間が決まります。 合計時間が短いものから順にタスクをこなしていくのが明らかに最適なので, そのように並べましょう。 class BatchSystem { public: vector <int> schedule(vecto</int>…

SRM 481 div1 easy: ChickenOracle

問題 TopCoder Statistics - Problem Statement 解法 落ち着いて状況を整理すると, 以下のような表になります。 表の i を決定すれば, j, k, l は決定されるので, i を全探索しましょう。 真実が egg の時は k+i が eggCount になり, 真実が chicken のとき…

yukicoder No.340 雪の足跡

問題 No.340 雪の足跡 - yukicoder 解法 ある頂点から進むことのできる方向に制限ができるので, それを基に幅優先探索するのが基本です。ただ, 進むことの出来る方向を愚直に決定すると から の間で, 進む方向をメモするのに最悪 O(W) (O(H)) かかって, 入力…