問題概要 N個の要素をもつ数列が与えられる。 この数列において、K個の要素をもつ区間それぞれについて、最小値・最大値を求めよ。 解法 セグメントツリーを使って、区間の最小値・最大値をO(log n)で求めてしまいましょう。 セグメントツリーは、プログラミ…

問題概要 文字列が入力される。 この文字列の順列全てを辞書順で出力せよ。 解法 next_permutationやるだけで解けました。 プログラム #include <iostream> #include <algorithm> #include <cstdio> using namespace std; int n; char s[1002]; int main(){ while(scanf("%s", s) != EOF){</cstdio></algorithm></iostream>…

問題概要 n, kが入力される。 n個の要素がある数列をバブルソートでソートされることを考える。 このとき、数列が並び終わるまでに、バブルソートの一重ループ目を実行した回数がkであるとする。 このようになる数列の初期配置は、何パターンあるか求めよ。 …

問題概要 nが入力される。 1, 2, ..., nの昇順数列をn, n-1, ..., 1の降順数列にするための最小の操作数と、操作方法を出力せよ。 数列に対する１回の操作では、次のことをできる。 (pos1, length, pos2) まず、数列のpos1番目からlength個を取り出す。 次に…

問題概要 http://poj.org/problem?id=3720 1/2 = .5, 1/3 = .(3), 1/6 = .1(6)... であるとき, 1/2〜1/nの小数点以下に数字kが何回出現するか求めよ.

問題概要 http://poj.org/problem?id=3456「a⋅w + b⋅x + c⋅y + d⋅z」という式のa〜dが入力として与えられる.(a〜dは0以上の整数) w,x,y,zに, 0以上の整数を代入できるとき, この式を使って作ることができない100万以下の整数の数を答えよ. また, 作ることが…

問題概要 http://poj.org/problem?id=3407 球のA地点とB地点が, 緯度と経度で与えられます. このとき, AからBまでの球上での最短距離を求めてください.

問題概要 http://poj.org/problem?id=3414 容量A,Bまで入る2つのポットがあります. 最初の水の量は, 最初2つとも0です. このとき, 次の操作を行いながら, どちらかのポットの容量をCにしてください. FILL(i) : iのポットを満タンにする DROP(i) : iのポット…

問題概要 http://poj.org/problem?id=3421Xが入力として与えられ, 次のようなm+1個の数を含む数列を考えます. 1 = X0, X1, X2, …, Xm = X Xi番目の項は, X_(i-1)番目の項で割り切ることができ, Xi > X_(i-1)が成り立っています.このとき, この数列の最大長と,…

問題概要 http://poj.org/problem?id=3411片方向グラフが与えられます. あるエッジ i を通るときのコストは, ciをすでに訪れたことがある場合 Piかかり, 訪れたことがない場合 Ri かかります. このとき, ノード１からNまでの最短コストを求めてください.