問題リンク Brave Princess Revisited 解法 (町, 残金)をノードにしたダイクストラで解けます。 (i, c)の状態からはお金を払わずに行く進み方 (残金が距離以上あるとき)お金を払って襲われる人数を0にして進む方法の2通りがあります。 ソース

問題リンク Matsuzaki Number 解法 Nより大きな素数の組み合わせの和を十分多く求めてその中でP番目の大きさのものを探す方針です。 大きさ150000程度までの素数を求めておきます(150000は適当です)。 Nより大きい最小の素数がk番目の素数だとします。k 〜 k…

問題リンク The House of Huge Family 解法 まず、入力の制約の「Yiは重複しない」に注目すると辺の数は高々N個だと分かります。さらに、負の重みを持つ辺は取り除いた方が絶対得なので無条件で取り除くことにします。 問題の条件を満たす家の構造を考えたと…