二段階単体法のデバッグに苦労しました。 問題概要 初期状態が全要素が 0 であるような N 次元ベクトルに対し、 以下のような Q 個の区間クエリを実施して得られる結果が 全要素が等しい N 次元ベクトルとなるようにしたい。区間クエリ i: 閉区間 [ L[i], R[…

難しく考えすぎてしまった。 文字列問題をみてもひるまずに解けるようになりたい。 問題概要 m 文字からなる文字列が n 個与えられる。 {0, 1, 2, …, m-1} の部分集合 bit のうち、 どの 2 つの文字列を選んでも、それらの文字列の bit に対応する部分文字列…

いい問題だった。 問題概要 0 以上 255 以下の整数が n 個与えられる。 この n 個の整数を 3 組に分ける方法のうち、各組の xor 和の総和が最大となるものを求めよ。(制約) ・3 解法 dp[ i+1 ][ j ][ k ] := i 番目までみたとき、二組の和がそれぞれ j, k の…

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0115 三次元幾何 問題概要 三次元空間上で、線分 s と三角形領域 t が与えられる。 s と t とが交点をもつかどうか判定せよ。 解法 まず、sを延長した直線と、tを延長した平面との交点 p を求める…

# 問題概要 無向グラフ (頂点数 n, 枝数 m) が与えられる。 このグラフの頂点集合を互いに disjoint な 2 つの集合 A, B に分割して、 A, B がともに vertex cover となっているようにせよ。 そのようなものが存在しなければ -1 をリターンせよ。 # 制約 2 ≤…