蟻本

POJ 2441: Arrange the Bulls

概要 牡牛がN頭いて,M個のコートに1頭ずつ割り当てたい. 牡牛はそれぞれ好むコートが決まっている. 割り当て方は何通りあるか. 解法 bitDPやるだけ. ただし,愚直に実装するとMLEを起こすはずなので,配列の再利用をする. int N, M; int P[30]; int B[…

POJ 2886: Who Gets the Most Candies?

POJ100問AC記念. 概要 N人の子供が一枚ずつカードを持っていて,輪になって並んでいる. K番目の子供からスタートする.まず,現在選んでいる子供を輪から除外する.除外した子供が持っていたカードに書かれている番号だけずれた子供を選ぶ.これを繰り返す…

POJ2155: Matrix

概要 N次正方行列があり,初期状態ではすべての成分が0である. T個のクエリが来て,内容は (x1,y1),(x2,y2)で定まる矩形領域に反転操作を行う. (x1,y1)の成分を答える である. 解法 2次元のBITを用意する.これは,(1,1),(x,y)によって定まる矩形領域の値…

POJ 3109: Inner Vertices

概要 2次元格子上においてある黒い石の情報が与えられる. ある格子点において,x方向,y方向共に黒い石に挟まれているならそこにも黒い石を置く. 最終的に格子上においてある黒い石の個数はいくつか? 解法 扱いやすいように座標圧縮をしておく. 各x座標…

POJ 1990: MooFest

概要 一次元座標x[i]と,値v[i]が与えられる.iとjの間の通信コストはmax(v[i],v[j])*|x[i]-x[j]|である.コストの総和を求めよ 解法 座標でソートしておく. 各iについて,BITを用いてv[i]以下であるiより小さい場所の座標の総和とそのような場所の個数を計…

POJ 2674: Linear World

思いがけないところではまったのでメモ. 概要 線分の上を物体がある方向に向かって動く.2つの物体が衝突すると反対に動く. 一番最後に落ちる物体の名前とその時間を求める. 解法 蟻本の蟻と似た考え方.最後に落ちるものを特定するには,左側にどれだけ…

POJ 3185: The Water Bowls

概要 20個のボウルが一列に並んでいて,あるボウルを選ぶとそのボウルと両側のボウルが一緒にひっくり返る.(端っこのボウルを選ぶと2個だけひっくり返る) 全てのボウルを正しい向きにするには,何回の選択が必要になるか? 解法 端っこから地道にシミュレ…

POJ 1222: EXTENDED LIGHTS OUT

ほろ酔いコーディング 概要 5行6列のライトのついたボタンがあって,ボタンを押したらそのボタンと4近傍のボタンが反転する. 与えられた状態からライトを全部消す押し方を求める. 解法 蟻本まんま.幅と高さをいじればそのまま通用する...と思う. 僕は…

POJ 2739, POJ 2100

POJ 2566は,そのままだとしゃくとりできないが,累積和にしてソートするとしゃくとりできるようになる.なぜならば,問題が知りたいのは合計の絶対値であるから,累積和の差だけを考えればよいため.カンニング先→POJ-2566 : Bound Found - komiyamの日記 P…

POJ 1759: Garland

概要 N個の提灯が下がった糸を垂らす.片方の端点はAとし,他方をBとする. このとき,糸は重力にしたがって垂れ下がる. i番目の提灯の高さをH_iとすると, H_1 = A, H_N = B, H_i = (H_(i-1) + H_(i+1)) - 1 が成り立つ. あるAが与えられたとき,全ての提…

POJ 3685: Matrix

概要 N次正方行列があって,その(i,j)-成分はi^2+100000*i+j^2-100000*j+i*jで与えられる. M番目に小さい要素の値はいくつか. 解法 解について二分探索.列を固定してしまえば,値は行について単調増加であることが式からわかる. 2次方程式を解けばO(1)で…

POJ 3662: Telephone Lines

概要 N頂点,辺P本のグラフが与えられる.K本の辺は無料で使うことができ,それ以上使うとK本からはみ出た辺の中での最大の長さだけの料金が発生する. 頂点1から頂点Nまでの経路をできるだけ安い料金で実現したい. 解法 料金(辺の長さの最大値)について…

POJ 2991: Crane

何を血迷ったのか,くっそ忙しいときに取り組んだ.そのうえ,勘違いをただすためにかなり時間を食った.今は反省している.問題文・解法は蟻本まんまのため省略. 多分同じ間違いをする人はいないと思うが,もしも同じ勘違いで頭を悩ませる人が出てきたとき…

POJ 3579: Median

概要 N個の配列が与えられる.この中から2つの要素を取り出し,その差を計算し別の数列とする. 新しく作った配列の中央値を探索する.ただし,この問題において偶数長(m)の配列の中央値はm/2番目に小さい値と定義する. 解法 解を仮定して二分探索.入力さ…

POJ 3111: K Best

概要 n個の宝石があって,k個を残して売り払いたい.その時,残したk個の宝石の単位重さあたりの評価値を最大化したい. 解法 蟻本そのままで二分探索.謎WA連発の末,探索終えた後にもう一回答えを計算したほうがいいという結論に至る. 繰り返し回数が結構…

POJ 3045: Cow Acrobats

概要 牛がN匹いる.i番目の牛は重さがw[i]で,強さがs[i]であることがわかっている. この牛でタワーをつくりたい.タワーは牛が別の牛一頭にのることを繰り返してつくられる. この時,牛iの危険度は (牛iの上に乗っている牛の重さの合計) - (牛iの強さ) で…

POJ 3104: Drying

概要 洗濯物がn個あって,自然乾燥だと1分間に洗濯物の水が1だけ減る.暖房機を使えば,1分間にkだけの水を減らすことができるが,これは1分間に1つの洗濯物についてだけしか使えない. 暖房機を最適に使った時,すべての洗濯物を乾かすのに必要な最小の時間…

POJ 3273: Monthly Expense

概要 要素数Nの数列{a_i}が与えられる.この数列をM個の連続した部分に分け,各部分の要素の合計の最大値を最小化したい. 解法 合計の最大値に対して二分探索を行う. 下限の初期化を間違っていたせいか,WA出した.あと,最近気が付いたんだけど,二分探索…

POJ 3258 : River Hopscotch

概要 スタートの石とゴールの石が川の中にあって,その間の距離がLだけ離れている.スタートとゴールの間には,N個の石が一列に並んでいて,i番目の石はスタートからd_iだけ離れた位置にある. スタートとゴールの石をM個以下だけ取り除いて,石(スタートと…

POJ 3641: Psudoprime numbers, POJ 1995 : Raising Modulo Numbers

解法 繰り返し二乗をやるだけ. POJ 3641 bool isPrime(ll x){ for(int i = 2; i * i <= x; ++i){ if(x % i == 0) return false; } return true; } ll p, a; int main(){ for(;;){ scanf("%lld%lld", &p, &a); if(p == 0 && a == 0) return 0; ll q = 1, s =…

POJ 3292 : Semi-prime H-numbers

概要 H={4N+1|Nは0以上の整数}とする.この時,Hの元xが1とxの組以外の積で表現できないものをHの素数と呼ぶことにする.h \in Hが与えられたとき,2つのHの素数の積で表すことができるh以下の数の個数を計算する. 解法 素数の列挙は篩を使っていい. あと…

POJ 3421: X-factor Chains

概要 2^20より小さい正整数Xが与えられる.長さnのX-factor ChainはX_1 X_i | X_{i+1} であるものをいう. Xの最長のX-factor Chainの長さはいくつか.また,最長のX-factor Chainの個数はいくつあるか. 解法 Xを素因数分解.素因数の冪の合計が長さに,各…

POJ 3126: Prime Path

概要 2つの4桁の素数A, Bが与えられる.Aに対して,「どれか一つの桁を書き換えて別の素数にする(ただし,最上位は0に書き換えてはいけない)」という操作を最小何回行えばBにすることができるか. 解法 素数の表を作り,幅優先探索. bool isntPrime[10000…

POJ 1930: Dead Fraction

概要 小数が与えられる.循環小数と見たとき,分母が最も小さくなる分数表示を求める. 解法 循環する区間を仮定して分数に直すという操作を繰り返す. n桁の循環する小数は,cを循環する部分を表す整数とすると,c/(10^n-1)で得られる. typedef unsigned l…

POJ 2395: Out of Hay

概要 ある頂点から,他の別の頂点へ横切る辺の重みの最大値が最小になるように移動する. この時,横切る辺の重みの最大値はいくつか. 解法 最小全域木を求め,その中でもっとも重みの大きい辺を出力. struct UnionFind{ vector<int> parent, rank; UnionFind(i</int>…

POJ 3268: Silver Cow Party

概要 有向グラフと目標頂点が与えられる. 目標頂点への往復経路が最も大きい頂点を探す. 解法 Dijkstraやるだけ. 復路の計算は与えられたグラフに対してDijkstra法を使えば簡単に求まる. 往路の計算は与えられたグラフの辺を逆向きにしたグラフにDijkstr…

POJ 2139: Six Degrees of Cowvin Bacon

概要 無向グラフが与えられるので,他のすべての頂点への距離の平均が最も小さい頂点を探す. 解法 Warshall-Floydやるだけ. const int INF = 100000000; int N, M; int d[310][310]; int c[310]; int main(){ scanf("%d%d", &N, &M); for(int i = 0; i <= …

POJ 1703: Find them, Catch them

概要 2種類の集合があって,2つの要素が異なる集合に属しているという情報と,2つの要素が同じ集合に属すかどうか問うクエリが来る. 解法 蟻本の練習問題と同様の考え方を用いる.要素vについて,集合Aに属している事象Avと,集合Bに属している事象Bvを用意…

POJ 2010: Moo University - Financial Aid

概要 コストa[i]と評価値s[i]の組の列がある. この中から,N(奇数)個の要素をコストの合計がFを超えないように選び,メディアンを最大化したい. 解法 メディアンはソートしたときの中央値であり,中央の値以外には影響をうけないことを利用する. N = 2K…

POJ2184: Cow Exhibtion

概要 100個以下の要素からなる(S[i],F[i])の列がある.(-1000 この列からいくつかの要素を選び,S[i],F[i]の総和をとる. S[i]の総和とF[i]の総和が0を下回らないという条件のもとで,S[i]とF[i]の総和を最大にする. 解法 S[i]について降順にソート. dp[i…