2013-10-06から1日間の記事一覧
問題 距離xと値vを持つN個の要素が与えられる。を全ての要素の組み合わせで算出し、その総和を求めよ。 解法 Binary Index Treeを使う。以下の記事を参考にした。 http://d.hatena.ne.jp/komiyam/20110223/1298457263 c1はx以下の数を示し、c2はx+1以上の数…
問題 無限に広い平面を考える。命令セットaが与えられ、T回命令セットを実行した時の原点からのマンハッタン距離を求めよ。 解法 aの総和から、方向の周期fを求める。 周期fの回数だけaを実行し、マンハッタン距離の変化量を計算する。 Tを周期fで割り、上で…
問題 幅W()高さH()の平面を考える。この平面内にN()の矩形が存在する。与えられた平面は、矩形により、いくつに分割されるか求めよ。 解法 座標圧縮を用いて計算量を減らす。与えられる数字は整数だが、分割されているかを判断する際には小数を考慮しなけれ…