ACM-ICPC JAG Summer Camp 2010, Day 4

Algorithm

オンライン参加できるらしいので参加。10問中5問解けた。暫定3位(→USAGI Codeが真にぱないことになって結果は4位でした)。昨日のも3位だったらしい。

A

グラフにして連結成分を1つの頂点にまとめてDAGにしてからDP

DPは、ある頂点 v について、頂点 v とそれよりも上(何と言えばいいのかわからないけど木でいうと先祖みたいな感じ)の部分において、指 v が畳まれてる場合の数を a[v]、立ってる場合の数を b[v] とする。すると入次数0の頂点では a = b = 1 で、それ以外の部分では a[v] = 1,

で計算できる。(u は v への辺があるような頂点)

B

探索するだけ

C

最初見たときに双対グラフの最小全域木とか無理ゲーだと思ったけど、普通に最大全域木するだけだった。

D

やるだけ

E

問題文が読めない

F

状態遷移が書けたら余裕だけど幾何無理

G

幾何無理

H

和としてありうる範囲を持ちながら順番にやっていく。問題文読めなくてWAしまくった。

I

読んでない

J

わからない

ACM-ICPC JAG Summer Camp 2010, Day 3

Algorithm

オンライン参加できるらしいので参加。10問中6問解けた。

A

やるだけだが壮絶にバグる。

B

rが小さくて座標が整数なので答えは必ず10000以下になることがわかる。あとは dp[i][j][k] := ニンジンをk個貰っていて、現在いる都市が j、その前にいた都市が i という状態へ行くための最短の経路の長さ でDP。

C

数学臭がやばいので逃亡

D

無理ゲー臭が漂うので逃亡

E

それぞれの敵について T[i] = 敵iを倒すのにかかるターン数、 A[i] = 敵iから1回の攻撃で受けるダメージ とする。あとは敵を A/T の昇順に並べておわり。

F

DP。ただし加速しないと死ぬ。

G

幾何なので逃亡

H

a = b = 1 のときはチケットの番号は関係なくて、とりあえずチケットを x 枚使うと (p+q)*x だけ進めるので x について二分探索する。

そうでないときは実際に使えるようなチケットは少ないので、p*a^k + q*b^k が m を超えないような k を列挙して貪欲に使う。

I

六角形見て逃亡

J

n = 1 に気をつけてやるだけ。

IOI 2008 Egypt過去問 PYRAMID BASE

Algorithm IOI

問題概要

横M、縦Nの二次元フィールドに辺がx軸y軸とそれぞれ平行な長方形の障害物がP個ある。i個目の障害物はCiの金で撤去可能であり、与えられた予算はBである。このフィールド上にできるだけ広い正方形の土地を確保せよ。

  • 1 <= M <= 1,000,000
  • 1 <= N <= 1,000,000
  • 1 <= Ci <= 7,000

次の3つのテストグループがある。

35点分
  • B = 0 (障害物は撤去できない)
  • P <= 1,000
35点分
  • 0 < B <= 2,000,000,000
  • P <= 30,000
30点分
  • B = 0 (障害物は撤去できない)
  • P <= 400,000

解法

まず最初に共通の性質として、答となる最大の正方形の辺は必ずどれかの長方形に接している。よって長方形に接するところだけを調べれば良い、というのが基本。

2つ目の35点分の解法

つまり障害物を撤去できるとき。基本的には正方形の一辺の長さについて二分探索を行う。ある長さ L の正方形がフィールド上に確保できるかどうかを現実的な時間で判定できればこのケースは解けることになる。

答となる正方形の辺が長方形に接することを利用すると、全ての長方形について、それに接する一辺の長さ L の正方形を置いたときに、その正方形と重なる長方形を撤去するためのコストが B 以下ならばよい。しかし、これをそのまま実装すると時間がかかりすぎる。

そこでまず問題を変形する。長さ L の正方形をフィールド上にそのまま確保するのではなくて、全ての長方形の横の長さを左に、縦の長さを下に、それぞれ L だけ伸ばしたフィールド上において一辺の長さが 1 の正方形を確保すると考える。(このときの一辺の長さが 1 の正方形は、目的とする一辺の長さ L の正方形の左下端になっている)

するとこの問題は次のようにして解ける。最初に要素数 N の配列 S を用意し、全要素を 0 で初期化する。そして走査線を左から右に走らせつつ、次の操作を行う。

  • 走査線が長方形の左端に達した場合、その長方形の下y座標(y1とする)から上y座標(y2とする)まで、S[y1..y2] にそれぞれこの長方形を撤去するためのコスト(cとする)を加算する。
  • 走査線が長方形の右端に達した場合、S[y1..y2] からそれぞれ c を引く。
  • いずれの場合でも、上記の2操作が終わった後に S[1..N-L+1] から最小の要素を見つける。その最小の要素の値が B 以下であれば、フィールド上に一辺の長さ L の正方形を確保することは可能であると判定する。そうでない場合は走査を続ける。

これをそのまま実装すると当然遅いので、Sをsegment treeで実装してやれば一回の操作(範囲に対する加算、減算、最小値)はそれぞれ O(log N) で済む。また、走査線は長方形の左右両端のみに興味があるので、そこだけ操作するようにすればこの判定は全体で O(P log N) で動く。

あとはこれを使って二分探索をするだけで、その範囲は 1 から min(M, N) までなので、全体の計算量は O(P log N log min(M, N)) となる。segment treeの実装は慣れていれば優しいし、他の実装も軽めなので辛くはない。

1つ目の35点分および3つ目の30点分の解法

つまり障害物を撤去できないとき。ここで考えるのは、「正方形の左端のx座標を固定したとき、とりうる最大の右端のx座標は何か？」ということである。この値が左端のx座標について広義単調増加であることから、次のアルゴリズムを開発できる。

最初に要素数 N の配列 S を用意し、全要素を 0 で初期化する。また、答となる値を sol とし、最初は0にしておく。そして走査線を2本、左から右に走らせつつ、次の操作を行う。ここで2本の走査線のうち1本は、上記の問における「左端のx座標」に対応し(左走査線とする)、もう1本は「とりうる最大の右端のx座標」に対応する(右走査線とする)。

  • 右走査線が長方形の左端に達した場合、S[y1..y2] にそれぞれ(正の値ならなんでもよいが) 1 を加算する。
  • 左走査線が長方形の右端に達した場合、S[y1..y2] からそれぞれ 1 を引く。
  • いずれの場合でも、min(右走査線のx座標 - 左走査線のx座標, S[1..N]の中で0が連続する最大の区間の長さ)と sol を比較し、その値がsolより多ければ sol をその値にする。

ここで「右走査線のx座標 - 左走査線のx座標」がその時にとりうる正方形の一辺の最大の長さの上界になってることは言うまでもないとして、「S[1..N]の中で0が連続する最大の区間の長さ」というのが「走査線に挟まれた部分において、左走査線から右走査線までの間に、障害物が占めるマスがひとつもないようなy座標が連続する最大の長さ」であることを考えれば、これで最適解が出せることに納得がいくはずである。

この場合もそのままの実装では当然遅いので、Sをsegment treeで実装してやれば一回の操作が O(log N) で済む。この走査も同じく長方形の両端だけを走査するので時間計算量は全体で O(P log N) である。

実装に関しては、segment treeの実装はそこまで難しくない(とはいっても、やや応用的な範囲になるのかな？)。ただ走査の部分が(少なくとも僕は)バグバグでどうしようもなく手間取った。まあこれは単に僕がSweep-line系のアルゴリズムの実装が死ぬほど苦手だというだけかもしれない。

続きを読む

壮行会というプレッシャーを与えるだけの儀式に参加してきました

Diary

司会「これより壮行会を行ないます。時間短縮のため拍手は最後にまとめてお願いします。」

司会「まず陸上部のうんたらかんたら」

司会「陸上部のみなさんはx月y日に開催されるなんたらかんたら」

司会「次に新体操部のうんたらかんたら」

司会「次にレスリング部のうんたらかんたら」

司会「次にコンピュータ部のJAPLJ君」

ざわ……ざわ……コンピュータ部……ざわ……

俺「(なんだこのアウェー感……)」

司会「JAPLJ君は8月14日からカナダで開催される」

…ざわ……カナダ……ざわ……

俺「(おい黙れお前ら)」

司会「国際情報オリンピックに日本代表として」

ざわ……日本代表……ざわ……

俺「(もうやだ)」

司会「出場します」

(拍手と歓声)

俺「(拍手は最後にまとめてって言われただろ……あと黙れお前ら……)」

俺「(プレッシャー = Ω(2^拍手数))」