蟻本練習問題埋め3-2

蟻本

しゃくとり法

POJ 2566 - Bound Found

問題

要素数nの数列aが与えられる。
各クエリでtが与えられるので、連続する部分列の中で、和の絶対値がtに最も近いものを求めよ。

制約

n<=100000

ai <=10000

t<=1000000000
クエリの数やデータセットの数の制約は書いてない

解法

しゃくとり法で各クエリO(n)で解く。
しかしそのままでは、区間の和が単調でないことからしゃくとり法を適用できない。
そこで、累積和s(i)=a[0]~a[i-1]の和を取ってソートし、その数列上でしゃくとり法をする。
a[i]~a[j]の部分和は、累積和を使えばs(j)-s(i)で求まる。
そこでs(j)-s(i)が最もtに近づくようなi,jをs(i)上のしゃくとり法で求めれば良い。

POJ 2739 - Sum of Consecutive Prime Numbers

普通のしゃくとり法

POJ 2100 - Graveyard Design

普通のしゃくとり法

反転

POJ 3185 - The Water Bowls

左端を反転させるかさせないか試すだけ

POJ 1222 - Extended Lights Out

蟻本のライツアウト通り

弾性衝突

POJ 2674 - Linear world

問題

長さlの直線上をn人の住人が同じ速度vで歩く。
住人の名前、右を向いているか左を向いているか、初期位置が与えられる。
住人同士がぶつかったとき、その2人の住人は逆向きに方向転換して歩き続ける。
直線の端まで行ったとき住人は落ちる。
最後に落ちる住人の名前と、落ちる時間を求めよ。

制約

n<32000

解法

蟻本のAntsと同じだが、名前を求めないといけない。
ここで、住人が方向転換しても、場所の順番は変わらないことに注目する。
最後に落ちる住人が左から落ちるか右から落ちるか、左から落ちる住人は何人か、右から落ちる住人は何人か、が分かれば、左から何番目の住人が最後に落ちるかを求めることが出来る。
"truncated"は切り捨てという事に注意。

半分全列挙

POJ 3977 - Subset

ただの半分全列挙

POJ 2549 - Sumsets

普通に半分全列挙するだけなんだけど、mapとか使うとTLEするのでハッシュを使う。
チェイン法のハッシュを配列で実装して94msだった。

座標圧縮

AOJ 0531 - Paint Color

蟻本に載ってるのと同じ