きままにものづくり

日々の気付いたことなんかを書いてます。

PKU

POJ 3264 : Balanced Lineup

問題 要素数N()の数列が与えれる。[a,b]区間の最大値と最小値の差分を求めなさい。 解法 セグメント木を使う。最大値を保持する配列と最小値を保持する配列の2つを持つ。 計算量 更新: クエリ: コード

POJ 2886 : Who Gets the Most Candies?

問題 N()人の名前と値が与えられる。初めにK番目の人(1から始まる)からスタートし、選ばれた人は抜ける。抜ける際に、p番目の人はpの約数だけ飴がもらえる。次の人は、その人の値分だけ時計回りした番号の人になる。マイナスの場合は逆回転となる。飴の最大…

POJ 2155 : Matrix

問題 N*N()の配列が与えられる。各要素は、1か0しか値をとることができない。ふたつのクエリに対する処理を実行せよ。 (x,y)の要素が1なのか0なのか求めよ (x1,y1,x2,y2)の範囲をフリップせよ 解法 二次元のBITを使い、範囲操作をするために4つの二次元BITを…

POJ 3109 : Inner Vertices

問題 無限平面上にN()個の黒点が与えられる。それ以外は白点である。上下左右に黒点がある場合は、その点は黒点になる。黒点の総数を求めよ。 解法 座標圧縮と範囲操作可能なBITを使用する。はじめ、yの値でソートする。その後、逐次xでソートしxに囲まれて…

POJ 1990 : MooFest

問題 距離xと値vを持つN個の要素が与えられる。を全ての要素の組み合わせで算出し、その総和を求めよ。 解法 Binary Index Treeを使う。以下の記事を参考にした。 http://d.hatena.ne.jp/komiyam/20110223/1298457263 c1はx以下の数を示し、c2はx+1以上の数…

POJ 2549 : Sumsets

問題 要素数N()の数列が与えられる。この中でa+b+c=dを満たす最大のdを求めよ。 解法 a+bを全列挙し、d-cを二分探索する。a+bで選んだ要素とd-cで選んだ要素は互いに違わなければならない。値と共に、インデックスを持たせることで同じ要素を使ってる場合を…

POJ 3977 : Subset

問題 要素数N()の数列が与えられる。その数列の中で空でない、総和がの絶対値が最小の部分列を求めよ。 解法 半分全列挙と二分探索。以下、注意点 2つに分割した集合のどちらか片方のみに答えの数値が含まれている場合を考慮する。つまり、集合1と集合2の組…

POJ 2674 : Linear World

問題 一直線上に左右それぞれに進行する物体がある。直線の長さLと物体の速度Vと初期位置Pと進行方向が与えられる。最後に落ちる物体の名称と時間を求めよ。 解法 貪欲法を使う。衝突により方向は変わるが速度は変わらない。注目物体以外に何もないと仮定し…

POJ 3185 : The Water Bowls

問題 要素数20の数列が与えられる。各要素は1か0である。すべての要素を0にする。ただし、注目点と隣接する要素は同時に反転される。 解法 反転される一番左の要素に注目する。各要素を見ていき1なら反転させる。ひとつめの要素に関してはそのままでは決定で…

POJ 1222 : EXTENDED LIGHTS OUT

問題 縦5×横6の配列が与えられる。配列の要素は1か0である。与えられた配列の要素を全て0にする。ただし、注目点と四近傍は同時に反転される。 解法 貪欲法で解ける。ひとつ上の要素が1ならその注目点で反転させる。一番上の要素の状態を全探索し、全て0にで…

POJ 2100 : Graveyard Design

問題 を満たす整数Nが与えられる。連続する数字の二乗和でNとなる数と、その内訳を答える。 解法 しゃくとり法を用いる。入力が大きいのでオーバーフローしないように注意する。long longではオーバーフローしてしまった。二乗和なので、探索範囲の最大値は…

POJ2739 : Sum of Consecutive Prime Numbers

問題 となるNが与えられる。Nとなる連続する素数の部分和の数を答える。 解法 エラトステネスの篩を用いてあらかじめ素数を求める。しゃくとり法を用いてNとなる素数の部分和の数を求める。 計算量 M:入力の数 N:与えられる数 コード

PKU3684弾性衝突

PKU

この問題は、蟻本に載っている問題です。 蟻本はアルゴリズムを問題付きで解説していて非常に良い本なのですが、処理を短縮できる根拠を示してないことが多いです。 今回の記事は、その確認です。 この問題でひっかかったのは、R>0の時は、R=0の場合を計算し…