問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2726 問題概要 N 人の従業員がいて，それぞれ成果を c(i) あげたとする．成果に応じて，報酬 p(i) を分配する． ただし，それぞれの従業員には親しい人が何人か存在する． 従業員 i が j と…

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2680 解法 メモ化再帰．memo[l][r] で，s[l..r]の取りうる最大値，もし無ければ "invalid" を入れていく． 完全に数字に置き換えられるならそうして(当然それが最適)，そうじゃないならLかR…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2710 解法 区間DP（メモ化再帰）． ある演算子に注目して，左と右に分けて，再帰的に処理していくとよい． 演算子が + であれば，左も右も最大値を取るようにすればよい．-であれば，左を…

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2741 解法 メモ化再帰で解ける． memo[si][sj][i][j][turn][pass] := a(si)からa(i-1)，b(sj)からb(j-1)までスタックに積まれていて，手番がturnかつパスの状態がpassであるときの最大値．(p…

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0575 解法 実装できなかったので，eagletmt さんの解法を参考にした． AOJ 0575 - Festivals in JOI Kingdom - プログラミングコンテストの記録使うアルゴリズムとしては，DijkstraとKruskal…

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0519 解法 a が b に勝利したことを，a -> b と有向辺で表現することにすれば，この問題はトポロジカル順序を求める問題になる． トポロジカル順序が求まったら，その頂点列のなかで隣り合っ…

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0526 解法 基本はワーシャルフロイドだが，それだと間に合わないので工夫する． 仮に島a, b間の船舶が更新された時，グラフ上の異なる2つの島u, vの最短経路は， u -> a -> b -> v つまり d[…

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0562 解法 まず，各頂点がショッピングモールからどれだけ離れているかを求める． これは，ショッピングモールの頂点をあらかじめ全てpriority_queueに突っ込んでおいたダイクストラを解けば…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0623 解法 危険な街を列挙さえすれば，あとはただの単一始点最短路問題． 危険な街を列挙するには，ゾンビに支配された街を全て，最初にqueueにプッシュしておくだけで十分である．計算量…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0616 解法 まず，0を始点としてダイクストラで，各点への最短路重みを求めておく． そして，その重みで頂点をソートしておく．また，あらかじめ辺全体の重みの総和を求めておく． Xの候補…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0600 解法 累積和と二分探索． まず，バウムクーヘンの累積和を二周分求めておく． その後，左端を適当に定め，そこから始めて長さが (lb + ub) / 2 以上になるところを2分探索で求める．…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0509 問題概要 平面座標に n 個の長方形がある．重なっていることもある． それらがつくる図形の面積と，周の長さを求めよ．・制約 1 長方形の左下，右上の座標の x, y 座標は，共に 0 以…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0517 解法 しゃくとり法でやった． 与えられた k 枚のカードをソートしておく． 0が含まれていれば1つだけ飛ばせるので，それは場合分けで処理． 行けるところまでいったら，左端をカード…

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0302 解法 星を輝度でソートする． 輝度の最小（つまり左端）を決めて，しゃくとり法でできる． 座標の最大最小は，priority_queueでもmapでもmultisetでもなんでもよい． 自分は最初 priori…

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0299 解法 d(i) をソートし，かつ p が 0 となるようにずらしておく． ちょっと考えると，解の候補としては d(1) まで反時計回りで一周する d(M) まで時計回りで一周する d(i) まで時計回り…