Problem G: Philosopher’s stone で、 • Accept：０ • Submit：０ – まぁ、妥当かと・・・。 概要 • 賢者の石を最短時間でつくれ • 与えられるもの – レシピ： • • • • 出来上がるもの 必要なものとその個数 かかる日数 同じものを作るのに複数のレシピはない – 材料 • 種類と個数 • できるなら最小日数を出力。できないとimpossible – できる場合合成回数は15回まで • キャッシュ付き全探査で求まる範囲 – 同時にできる作業は２つまで 解法概要 • レシピがユニークなので、作らなければいけないも の＆その個数は簡単に判定可能 – トポロジカルソートをかけて上位から探索 – Impossibleはこの段階で判定可能 • どういう順でつくるかはわからない • 探索木はDAG • 作れる場合はDFS – 枝刈りとメモ必須 トポロジカルソート • DAG（循環のない有向グラフ）を、親子関係を 崩さないまま全順序化する – AがBの祖先→Bのindex < Aのindex A たとえば B C G D E G F H D B E H F C A トポロジカルソートのアルゴリズム • DFSで帰りがけ順にリストに追加 Impossibleの判定 • トポロジカルソートをかけて、上位から （Philosopher’s-stoneから）生成に必要な個 数を数える。 • 手持ちがあったらその数分使う。 • レシピがなくて、必要数手持ちにない場合は impossible 作れる場合（その１） • トップダウン型 • メモ付き枝狩り全探査 – 作られなきゃいけないものから逆にたどる – メモ化 • 単純全探査では最悪15!程度になるのでおわらない • A→B→・・・とB→A→・・・との探索の後ろは同じ • メモの状態： – – – – 今必要となるものの集合 現在の時刻 現在作っているもの、終了時刻 手持ちの材料と個数 – 枝狩り • 今の最短時間よりも時間がかかることがわかった時点でreturn • 手持ちはとりあえず使ってみる – 使わない場合も探索必須 • レシピがないものは手持ちから使うしかない • 記述量がかなり増えるけど、残りは単なる実装 作れる場合（その２） • ボトムアップ型 – 探索の状態は時刻＋今作っているもの＋残りの 材料＋残りレシピ – 各状態より作れるものを作ったのが次の状態 – 後は記述が多少面倒な探索問題
© Copyright 2024 ExpyDoc
