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

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

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

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

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

概要 授業でn回のテストを受けた．i番目のテストではb[i]問中a[i]問正解した． 受けたテストのうちk回を取り除き，を最大化したい． 解法 二分探索．蟻本の練習問題まんま． int n, k; int a[1010], b[1010]; double v[1010]; bool C(double x){ for(int i =…

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

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

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

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

解法 繰り返し二乗をやるだけ． 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 =…

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

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

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

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

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

概要 最大全域木を求める． 解法 辺の正負を反転して最小全域木を求める． struct UnionFind{ vector<int> parent, rank; UnionFind(int n) : parent(n,-1), rank(n, 0) { } int find(int x){ if(parent[x] == -1) return x; else return (parent[x] = find(paren</int>…

概要 最小全域木を求める． typedef int Weight; struct Edge{ int from, to; Weight weight; Edge(int f, int t, Weight w) : from(f), to(t), weight(w) { } }; typedef vector<Edge> Edges; typedef vector<Edges> Graph; bool operator< (const Edge &a, const Edge &</edges></edge>…

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

蟻本の問題番号と，問題名の対応が間違ってた． 概要 負閉路検知やるだけ． const int INF = 100000000; typedef int Weight; struct Edge{ int from, to; Weight weight; Edge(int f, int t, Weight w) : from(f), to(t), weight(w) { } }; typedef vector<Edge> </edge>…

概要 無向グラフが与えられるので，他のすべての頂点への距離の平均が最も小さい頂点を探す． 解法 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 <= …

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

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

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

蟻本の練習問題を消化中 概要 K種類のブロックがあって，i番目のブロックは高さhiであり，ci個だけある．また，ブロックの一部がhiを超えるとまずい． ブロックを積み上げていくとき，到達できる高さの最大はいくつか． 解法 ブロックを高さ制限でソート． d…