http://poj.org/problem?id=3411問題文をよく読みましょう。(a,b)は有向辺です。無向辺でやったあとを残しておきました。 ベルマンフォードっぽくbitDPをやればよい。 int N, M; int A[20], B[20], C[20], P[20], R[20]; int dp[1 << 11][11]; int main() { …

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2266箱が1つなら簡単。 箱がmつの時はM-1個の箱がコストを節約するために使えると考えられる。 どれくらいコストを節約できるか考えよう。 あるボールを時刻sに入れ、次に入れる時刻をtとしよう。…

http://poj.org/problem?id=3680解法は蟻本にある。蟻本では負辺にあらかじめ目一杯流すことで対応しているが、ここではベルマンフォードで最初のポテンシャルを求めることによって解いてみよう。ポテンシャルh(v):=(s-v間の最短距離)と基本的にすれば良いが…

http://arc080.contest.atcoder.jp/tasks/arc080_c逆から見ると、列の偶数番目と奇数番目をとって、3つの列に分割して再帰的にまた同じようなことをする問題に言い換えられる。 しかしうまく実装する方法が思いつかず、ひたすらデバッガ使って通した。強い人…

http://arc080.contest.atcoder.jp/tasks/arc080_dまず列の差をとって区間の問題を距離が奇素数の2点を反転させてすべて0にする問題に帰着させる。座標i,jにある1を対応させるときのコストは |i-j|が奇素数→1 |i-j|が偶数→2 |i-j|が奇素数ではない奇数→3 と…

http://arc078.contest.atcoder.jp/tasks/arc078_cまず桁数を特定する。これは1, 10, 100,...と比較するとわかる。 それからは上の位から数字を特定していく。 例えば(10^3,10^4)の区間において49990を投げると、(10^3,5*10^3)でyes,[5*10^3,10^4)でNoとなる…

http://arc078.contest.atcoder.jp/tasks/arc078_d3^Nの形になるdpなんて初めて見た。まず使う辺に注目して、それらのコストの和を最大化する。 dp[S][v]:=(集合Sの点を使う際で0~v間でpathがただ一つ存在するための最大値)とする。遷移は二種類ある。 (1)pa…