7月19日のPKU - TopCoderとJ言語と時々F#

今日：9問
今日までの合計：17問

PKU 2696 A Mysterious Function

問題

PKU 2696

問題文中の関数を実装してね。

解法

C言語の % の仕様うぜえええええええええええええ

PKU 3681 Finding the Rectangle

問題

PKU 3681

平面上にN個の点があるので、これらのうち少なくともM個を覆う最小の長方形の面積を求める問題。

ただし 1 <= M <= N <= 200

解法

まず求める長方形のy座標と縦の長さを固定する。この決まった縦の長さの中で、点をM個覆うような長方形を全部見つける。

y座標の組合せは O(N²) 通りあって、その中で作れる長方形は O(N) 通りあるので全体で O(N³)。

PKU 3090 Visible Lattice Points

問題

PKU 3090

x, y座標が 0 <= x, y <= N であるような格子点のうち、(0, 0) から (x, y) への線分の途中が他の格子点とぶつからないような (x, y) の個数を求める問題。

ただし 1 <= N <= 1000

解法

gcd(x, y) == 1 なら他の格子点とぶつからないので数える。計算量はO(N²)。

PKU 3543 iChess

問題

PKU 3543

黒いタイルb個と白いタイルw個を使って作れる最大のチェス盤の大きさを求める問題。ただしチェス盤が作れない時はImpossibleと出力すること。

ただし 0 <= b,w <= 10000

解法

やるだけ。

PKU 2833 The Average

問題

PKU 2833

n個の数値のうち大きい方からn₁個、小さい方からn₂個省いたものの平均値を求める問題。

ただし 1 <= n₁, n₂ <= 10 で n₁+n₂ < n <= 5000000

解法

nが500万と大きいのでメモリをとれない。そこで最大値を格納する要素数n₁の配列と、最小値を格納するn₂を用意しておく。n個の数値の合計値からそれぞれの配列の値を引いてから平均値をとればよい。計算量は O(n(n₁+n₂))。

PKU 2559 Largest Rectangle in a Histogram

問題

PKU 2559

n項目のヒストグラム中の長方形(問題文中の画像参照)のうち面積が最大のものの面積を求める問題。

ただし n <= 100000

解法

ALGORITHM NOTEで解説されている方法を用いる。計算量はO(n)。

PKU 3494 Largest Submatrix of All 1’s

問題

PKU 3494

0と1からなる大きさm * nの行列の中で、全ての要素が1であるような部分行列の大きさを求める問題。

ただし 1 <= m, n <= 2000

解法

まずある場所 (i, j) からその上に続く1の数を記録した行列を計算する。これは動的計画法を用いて O(mn) でできる。

次にこの行列の各行に対してPKU 2559と同じアルゴリズムを適用することで最大の長方形を見つけることができる。m行に対してO(n)なので全体の計算量はO(mn)で済む。

PKU 3646 The Dragon of Loowater

問題

PKU 3646

Loowater国に複数の頭があるドラゴンが現れた。これを殺すために騎士を雇わなければならない。

ドラゴンを殺すにはドラゴンの全ての頭を切る必要がある。ドラゴンの頭の大きさはそれぞれ異なっており、ある頭を切ることができるのはその頭と同じか、それより大きな身長の騎士だけである。騎士を雇うとき、その騎士の身長ぶんお金がかかる。

ドラゴンのn個の頭の大きさとm人の騎士の身長が与えられるので、ドラゴンを殺すことができ、かつ最も賃金が少なくなるような騎士の雇い方をしたときの賃金の合計を求める問題。ドラゴンを殺せない場合もある。

ただし 1 <= n,m <= 20000

解法

n > mの場合は明らかにドラゴンを殺せない。

それ以外の場合は二分探索するだけ。ドラゴンを殺せなくなってしまう場合もあるので注意。

PKU 2591 Set Definition

問題

PKU 2591

集合Sを以下のように定義する。

1は集合Sの元である。
xが集合Sの元ならば2x+1と3x+1も集合Sの元である。
その他のいずれの数も集合Sの元ではない。

整数N (1 <= N <= 10000000) が与えられるので、Sの中でN番目に小さい数を求める問題。

解法

Sを実際に生成すればよい。ただし昇順になるように生成しなければならないので注意。