PKU 3254:Corn Fields [PKU]
問題文 : http://poj.org/problem?id=3254
概要 : 0のところは必ず0で, 1のところは0または1にできる. このとき, 1が隣接しないようなマスの作り方は何通りあるか.
解法とか問題の種類とか:
簡単なbitDPです.
今見ている場所より上がvalidで, 下は今から決める, という考え方で, 考えるべき空間がグッと減るのがbitDPの良い所だなーと思います.
この問題は右と上に隣接することを念頭に置きながら考えないと行けないのですが, 今見ている場所が右端だとすると、右隣が無いことに注意しましょう.
概要 : 0のところは必ず0で, 1のところは0または1にできる. このとき, 1が隣接しないようなマスの作り方は何通りあるか.
解法とか問題の種類とか:
簡単なbitDPです.
今見ている場所より上がvalidで, 下は今から決める, という考え方で, 考えるべき空間がグッと減るのがbitDPの良い所だなーと思います.
この問題は右と上に隣接することを念頭に置きながら考えないと行けないのですが, 今見ている場所が右端だとすると、右隣が無いことに注意しましょう.
PKU 2926: Requirements [PKU]
マンハッタン距離使う問題が解けていないので、類題を探してやってみました.japljさんの記事を参考にしました.
5次元でのマンハッタン距離の最遠点対を求める問題.
普通にやると, O(点の数^2)になる所を工夫します.
5次元で考えるのは面倒なので, 2次元で考えてみます.
当然なようですが,
|x1-x2|+|y1-y2| = max{x1 + y1 - (x2 + y2), x1 - y1 - (x2 - y2), -x1 + y1 - (-x2 + y2), -x1 - y1 - (-x2 - y2)}
と表されます. すなわち, N個の点のなかの最遠の点対(xa, ya), (xb, yb)は
xa + ya ≧ xi + yi (1 ≦ i ≦ N) かつ xb + yb ≦ xi + yi
xa - ya ≧ xi - yi かつ xb - yb ≦ xi - yi
- xa + ya ≧ - xi + yi かつ -xb + yb ≦ -xi + yi
-xa - ya ≧ -xi - yi かつ -xb - yb ≦ -xi - yi
のいずれかを満たしていることとなります. x + yが最大になる点などはO(N)で見つけられるので, O(N)で最遠点対を決定することが出来ます.
k次元のマンハッタン距離でも同じ議論ができ, +-の富豪を考慮して, O(N * 2^k)で最遠点対を求めることが出来ます.
5次元でのマンハッタン距離の最遠点対を求める問題.
普通にやると, O(点の数^2)になる所を工夫します.
5次元で考えるのは面倒なので, 2次元で考えてみます.
当然なようですが,
|x1-x2|+|y1-y2| = max{x1 + y1 - (x2 + y2), x1 - y1 - (x2 - y2), -x1 + y1 - (-x2 + y2), -x1 - y1 - (-x2 - y2)}
と表されます. すなわち, N個の点のなかの最遠の点対(xa, ya), (xb, yb)は
xa + ya ≧ xi + yi (1 ≦ i ≦ N) かつ xb + yb ≦ xi + yi
xa - ya ≧ xi - yi かつ xb - yb ≦ xi - yi
- xa + ya ≧ - xi + yi かつ -xb + yb ≦ -xi + yi
-xa - ya ≧ -xi - yi かつ -xb - yb ≦ -xi - yi
のいずれかを満たしていることとなります. x + yが最大になる点などはO(N)で見つけられるので, O(N)で最遠点対を決定することが出来ます.
k次元のマンハッタン距離でも同じ議論ができ, +-の富豪を考慮して, O(N * 2^k)で最遠点対を求めることが出来ます.
行列累乗と行列分割 (PKU 3734, 3255, etc) [PKU]
繰り返し二乗法を用いた行列累乗, 及び, 行列分割を使った行列の累積和の問題を解きました.
C++ (STL)の使い方を少しずつ覚えてきました. vector配列って, 暗黙的に0で初期化されているのでしょうか.
C++ (STL)の使い方を少しずつ覚えてきました. vector配列って, 暗黙的に0で初期化されているのでしょうか.
PKU 2991: Crane [PKU]
セグメント木の練習です.
一つの角が変化すると, それ以降のクレーンの位置も全て変更するため, セグメント木を使い, 区間ごとに処理をしていくのが最適でしょう.
区間[i, j]には, 始点i, 終点jのベクトルの情報をもたせます.
一つの角が変化すると, それ以降のクレーンの位置も全て変更するため, セグメント木を使い, 区間ごとに処理をしていくのが最適でしょう.
区間[i, j]には, 始点i, 終点jのベクトルの情報をもたせます.
