[問題] 2112 -- Optimal Milking牛とミルクマシーン(適当)が辺で接続されている。全ての牛をミルクマシーンに到着させたい。この時もっともたくさん歩く牛の距離を最小化せせよ。ただし、ミルクマシーンはm匹の牛しか処理できない。 [解法] WarshallFloyd + …

[問題文] 1949 -- ChoresN個の仕事がある。それぞれにかかる時間と、その仕事より必ず先に終わらせなければならない仕事k個の情報が与えられる。 仕事は並列で行うことができる。N個の仕事を終わらせるのにかかる時間を最小化せよ。 [解法] トポロジカルソー…

1651 -- Multiplication Puzzle [問題] N枚のカードが与えられる。これらの中から任意の1枚を取り除く。この際、選んだカード * 左のカード * 右のカードのスコアが加算される。ただし両端のカードは選べない。 可能な限りこれらの操作を繰り返した時の合計…

1611 -- The Suspects [問題] いくつかのグループとそこに所属する生徒のメンバーの情報が与えられる。0番の生徒が強力な風邪菌(意訳)を持っていて、同じグループに所属している生徒に感染してしまう。感染は推移的であり、例えば aグループ と bグループ両…

1564 -- Sum It Up [問題] N個の要素からなる集合が与えられます。合計がtとなる任意の部分集合をdecreasing orderで出力してください。(例) Input: t = 400 N = 12 [50 50 50 50 50 50 25 25 25 25 25 25]Output: Sums of 400: 50+50+50+50+50+50+25+25+25+…

3671 -- Dining Cows [問題] 1または2がランダムにN個並んでいる。任意の箇所を1 -> 2 もしくは 2 -> 1と書き換えることで、全ての1が2より前に来るようにしたい。 書き換える回数の最小値を求めよ。 [解法]1グループと2グループをどこで分けるかで全探索。…

2186 -- Popular Cows [問題] M個のペア(A,B): 牛Aが牛Bを人気者だと思っている が与えられる。ただし (A,B) ,(B,C) => (A,C) とする。(関係は推移的) 自分以外の全ての牛から人気者だと思われている牛の数を求めよ ずっと放置していた蟻本の問題。 すべての…

問題文→ 2140 -- Herd Sums[問題] 自然数Nが与えられる。 Nを連続した自然数の和で表すと何通りできるか。(例) N = 15 [7+8 , 4+5+6 , 1+2+3+4+5 , 15] 4通り Sum(b) - Sum(a-1) = Sum([a,b]) みたいなことすると O(n^2)とかになって間に合わない。なので S(…

問題文→ 3041 -- AsteroidsN*Nの格子上にK個の小惑星があります。小惑星iの位置は(R[i],C[i])にあります。縦または横一直線上の小惑星をすべて一発のビームで破壊できる強力な武器があり、これを用いてすべての小惑星を破壊するために必要な最小の発射回数を…

ネット復旧したので休憩がてらPythonでスクリプト書いてみました。 PKUの各問題を.txt形式に変換するスクリプトです。 変換する問題の範囲を指定できますが、あまり多くしすぎるとDOS攻撃に近い動きをするので、変換は間を置いて少しずつするようにします。(…

問題文→2104 -- K-th Numbersort()とか使うと間に合わないので 区間ごとのx以下の個数を二分探索で数えます。しかし二分探索にはソートが必要なのでマージソートの要領でセグメント木を作っておき、必要な区間に対してのみ二分探索を行えば間に合うみたいで…

問題文→2385 -- Apple Catchingりんごが1分ごとに2本の木のいずれかから落ちてくる。2本の木を決められた回数内行き来して落ちてくるりんごをキャッチする。 キャッチできるりんごの合計の最大値を求めよ。とりあえずメモ化再帰を書いてみる。しかしこれでは…