プチコン 非公式コミュニティ
トピック
こういち
◆.Id/aHiU36hu
2020/8/2 15:30
2020/8/2 15:30
コンテスト
Alchemy2(難易度上げすぎた)
錬金術師のファンリーアさんは、触媒を使った錬金術を行い、物質0を物質1に変えようと思っています。
物質は0,1を含めてN種類あり、物質を変化させるためのレシピがM種類あります。
また、物質を変化させるために必要な触媒がL種類あり、i番目の素材はV_iのお金で購入できます。
i番目のレシピには物質F_iからT_iに変化させるための方法が書いてあり、変化には触媒C_iを消費せずに使用し、変化時に触媒B_iを生成します。
ファンリーアさんはできるだけ少ないお金で物質1を生成したいです。
ファンリーアさんが物質1を生成するのに最低でどれだけのお金がかかるでしょうか。
ただし、物質0を物質1に変化させるような手順が必ず1つ以上存在し、変化の過程で余った触媒については考えないものとします。
物質は0,1を含めてN種類あり、物質を変化させるためのレシピがM種類あります。
また、物質を変化させるために必要な触媒がL種類あり、i番目の素材はV_iのお金で購入できます。
i番目のレシピには物質F_iからT_iに変化させるための方法が書いてあり、変化には触媒C_iを消費せずに使用し、変化時に触媒B_iを生成します。
ファンリーアさんはできるだけ少ないお金で物質1を生成したいです。
ファンリーアさんが物質1を生成するのに最低でどれだけのお金がかかるでしょうか。
ただし、物質0を物質1に変化させるような手順が必ず1つ以上存在し、変化の過程で余った触媒については考えないものとします。
コメント
こういち
2020/8/2 15:37
◆.Id/aHiU36hu
入力は以下のような形式で与えられます。
N,M,L
V_0
V_1
…
V_(L-1)
F_0,T_0,C_0,B_0
F_1,T_1,C_1,B_1
…
F_(M-1),T_(M-1),C_(M-1),B_(M-1)
制約
2<=N<=15
N-1<=M<=N(N-1)
1<=L<=M
0<=F_i,T_i,<N
0<=C_i,B_i<L
C_i≒B_i
1<=V_i<=10^5
グラフは自己ループや多重辺を含まない。
入力は全て整数で与えられます。
N,M,L
V_0
V_1
…
V_(L-1)
F_0,T_0,C_0,B_0
F_1,T_1,C_1,B_1
…
F_(M-1),T_(M-1),C_(M-1),B_(M-1)
制約
2<=N<=15
N-1<=M<=N(N-1)
1<=L<=M
0<=F_i,T_i,<N
0<=C_i,B_i<L
C_i≒B_i
1<=V_i<=10^5
グラフは自己ループや多重辺を含まない。
入力は全て整数で与えられます。
こういち
2020/8/2 15:41
◆.Id/aHiU36hu
ERRORさんのオリキャラお借りしました。
ツララ
2020/8/5 18:19 ネタバレ
◆ArUdBYOYME1V
高原のな
2020/8/5 21:34
◆bY8RViwvoODw
入力はファイルまたはSLOT1でいいですかね。入力の手間がある程度省けそうなので
（入力読み込みの関数ははやめにここで公開したいですね）
（入力読み込みの関数ははやめにここで公開したいですね）
こういち
2020/8/6 6:58 ネタバレ
◆.Id/aHiU36hu
あきと
2020/8/6 16:14 ネタバレ
◆qGd5dQw2g3a2
高原のな
2020/8/6 17:05
◆bY8RViwvoODw
あきとさん；
（実はこういちさんは毎回解説を書いているのです…… ただ、かなり簡素なまとめ方をするので、ある程度分かっていないと難しいかもしれません）
今回、難易度が高めなので、わたしとしては解き方説明していこうと思ってますし、わたしが解説する元気がなくても読みやすくなるようコメントを多数入れて書いていきます(多少のアルゴリズムの勘所を説明できたらいいなぁと思ってたり、あるいは別解なんかも多数引き出してみたい)。
ぜひともこういちさんにも多数コメントしていただきたいですね
(訂正に関して：いえいえ、お手数おかけしてすみません)
（実はこういちさんは毎回解説を書いているのです…… ただ、かなり簡素なまとめ方をするので、ある程度分かっていないと難しいかもしれません）
今回、難易度が高めなので、わたしとしては解き方説明していこうと思ってますし、わたしが解説する元気がなくても読みやすくなるようコメントを多数入れて書いていきます(多少のアルゴリズムの勘所を説明できたらいいなぁと思ってたり、あるいは別解なんかも多数引き出してみたい)。
ぜひともこういちさんにも多数コメントしていただきたいですね
(訂正に関して：いえいえ、お手数おかけしてすみません)
高原のな
2020/8/6 18:55 ネタバレ
◆bY8RViwvoODw
Na
2020/8/6 22:08
◆QoELVrBXBQCI
物質0は無数にありますか?
つまり、物質F_iからT_iに変化させてもF_iは消費しないですか?
つまり、物質F_iからT_iに変化させてもF_iは消費しないですか?
こういち
2020/8/6 22:21
◆.Id/aHiU36hu
あきとさん
一応次の問題を投稿したあたりで解説は書くようにしています。逆にそれまでは(ネタバレ機能があるとは言え)ネタバレは控えるようにしてるので、無機質に感じるかもしれませんね。
Naさん
変化後F_iは消滅します。
一応次の問題を投稿したあたりで解説は書くようにしています。逆にそれまでは(ネタバレ機能があるとは言え)ネタバレは控えるようにしてるので、無機質に感じるかもしれませんね。
Naさん
変化後F_iは消滅します。
こういち
2020/8/6 22:39 ネタバレ
◆.Id/aHiU36hu
高原のな
2020/8/6 22:41 ネタバレ
◆bY8RViwvoODw
こういち
2020/8/6 22:54 ネタバレ
◆.Id/aHiU36hu
高原のな
2020/8/6 22:58 ネタバレ
◆bY8RViwvoODw
Na
2020/8/8 23:31 ネタバレ
◆QoELVrBXBQCI
こういち
2020/8/17 22:39 ネタバレ
◆.Id/aHiU36hu
こういち
2020/8/26 18:46
◆.Id/aHiU36hu
次の問題投稿してないですが、そろそろ解説書きます。(次の問題は準備中)
こういち
2020/8/26 18:47 ネタバレ
◆.Id/aHiU36hu
こういち
2020/8/26 19:10
◆.Id/aHiU36hu
この解法。間違ってる気がする。
こういち
2020/9/1 10:29
◆.Id/aHiU36hu
コメントを書く
- こちらは「プチコン3号」「プチコンBIG」など、プチコンシリーズに関する話題を扱ったコミュニティです
- プチコンシリーズにまったく関係ない書き込みはご遠慮下さい。削除の対象となります
- こちらにはその他のゲームや雑談のコミュニティはなく、作る予定もありません (ひとりで管理できないため)。ごめんなさい
- ユーザー登録なしで書き込みができます
- 秘密の合い言葉は成りすましの防止 (トリップ機能)、書き込みの編集時の本人認証に使用します
- 秘密の合い言葉に他人に推測されやすい言葉、他サービスと同じパスワードは入力しないでください。
- 書き込むと、投稿時に入力したお名前と秘密の暗号が記憶され、ログイン状態になります