IOI 2008 Egypt過去問 TYPE PRINTER

Algorithm IOI

問題概要

スタックが1個あって、次の3つの操作が許されている。

  • 文字を1つpush
  • 文字を1つpop
  • スタックの底から頂点までをなぞって文字列を印字する

さて、N個の文字列が与えられるので、上の3つの操作をできるだけ少ない回数だけ使ってこれらの文字列を全て印字したい(順番は問わないし、最後の文字列を印字した後にスタックに文字が残ってても構わない)。最適な操作列を求めよ。

  • 1 <= N <= 25000
  • 1 <= 各文字列の長さ <= 20

解法

Trieを作って辿る。一番深い部分木を最後に辿れば操作回数が最小になる。

続きを読む

IOI 2008 Egypt過去問 ISLANDS

Algorithm IOI

問題概要

N個の頂点とN個の辺を持ち、どの頂点も最低1つの辺で接続されているような重み付き無向グラフが与えられる。好きな頂点から出発して、次のどちらかの移動を繰り返す。ただし同じ頂点に2度訪れることはできない。

  • 辺を辿って移動する。
  • どのように辺を辿っても移動できないような頂点にワープする。

このとき、通った辺の重みの和を最大化せよ。

  • 2 <= N <= 1,000,000
  • 1 <= 辺重み <= 100,000,000

解法

まず問題は連結成分ごとに分解できるので、連結成分ごとに最大重みの経路を求める問題を解いてすべて合計すればよい。

ここでグラフに課せられた制約(孤立点が存在しない)から、全ての連結成分は頂点数と辺数が等しい。よってこの連結成分は木に1本だけ辺を追加した形をしている。見方を変えれば、この連結成分にはサイクルが1つだけ存在する。

さて、このサイクルについて考えたい。サイクルの頂点を (v[1], v[2], ..., v[c]) として、ある頂点 v[k] に注目する。v[k] から v[k-1] と v[k+1] への辺を切ると、そこには v[k] を根とする木が残る。つまりサイクルは c 個の根付き木の根同士が繋がってできたものと見なすことができる。

このことから最適解は、次のいずれかになる。

  • サイクルの頂点のうちどれかを根とする木の直径
  • サイクルのある2頂点 s, t を根とする木の高さと、サイクル中における s, t の距離の和

後者のイメージとしては、 s を根とする木の葉から根である s へと辿り、そこからサイクルを s から t へ辿り、最後に t からその木の葉まで辿るという感じになる。

あとは、後者の方を計算するときに愚直に実装するとサイクルの頂点数を c とすれば O(c^2) 時間が必要になってしまうので注意が必要。v[k]を根とする木の高さを height[k] として、v[1]からv[2], v[3], ... と辿ってv[k]まで到達する時の距離を len[k]、そしてサイクル中の辺重みの総和を L とすると後者は

max(i < j) { height[i] + height[j] + max(v[j]-v[i], L-(v[j]-v[i])) }

を計算することで求められるがこの式を変形して

max {
  max(i < j) { height[i] + height[j] + v[j] - v[i] },
  L + max(i < j) { height[i] + height[j] - v[j] + v[i] }
}

とし、さらに

max {
  max(i < j) { (height[i] - v[i]) + (height[j] + v[j]) },
  L + max(i < j) { (height[i] + v[i]) + (height[j] - v[j]) }
}

と考えればi, jが分離できたので O(c) で計算可能になる。

以上を全てまとめると、全て頂点数について線形時間なので全体で O(N)。

続きを読む

IOI 2008 Egypt過去問 LINEAR GARDEN

Algorithm IOI

問題概要

LとPのみからなるN文字の文字列であり、どの連続した区間をとっても一方の文字が他方の文字より3文字以上多いことがないという制約を満たす文字列がひとつ与えられる。与えられた文字列が、この制約を満たす文字列のうち辞書順で何番目かを求めよ。mod Mで。

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

解法

文字列について、次のように走査することを考える。

  • はじめ、カウンタを0に設定しておく
  • 文字Lが現れたらカウンタをインクリメント
  • 文字Pが現れたらカウンタをデクリメント

すると、条件を満たす文字列はカウンタの最大値と最小値の差が2以下におさまる。これを利用する。

dp[i][lo][hi][cnt] := i文字目までが決定している文字列で、そこまで走査したときのカウンタの最小値がlo、最大値がhi、現在の値がcntであるような状況において、ここから先、文字数がNになるようにLとPを付け加えてできる「条件を満たす」文字列の数

とおいてDPするとよい。lo, hi, cnt はそれぞれ-2以上2以下なので5通りの値をとり、iはN通りの値をとるから N*5*5*5 = 125N もの部分問題ができるのでDPでよくあるメモリ節約テクニックを使う。実行時間については、lo, hi, cnt は125通りの組み合わせがあるが、そのうちhi-lo <= 2 であり lo <= cnt <= hi であるものは少ないので問題ない。

最終的な答を求めるには、例えばサンプルにある "PLPPL" なら、 "PLPL?", "PLL??", "L????" (?は任意の文字)に対応する状態のDP表の値を全て合計すればよい。

続きを読む

IOI 2008 Egypt過去問 TELEPORTERS

Algorithm IOI

問題概要

数直線上にいくつかの点のペアが存在し、その片方に乗るともう片方に飛ばされるように(テレポートするように)なっている。全ての点の座標は1以上で2,000,000以下。同じ座標に複数の点は存在しない。

この数直線上で0から出発し、どんどん右へ進んで行く。最終的に座標2,000,001に達した時点でテレポートした回数が得点として得られる。

はじめにあるN個のペアの座標が与えられるので、そこにM個以下の新たなペアを追加して、獲得できる得点を最大化せよ。はじめに与えられるN個のペアの座標は整数だが、新たに追加するペアの座標は0より大きく2,000,001より小さい任意の実数で構わない。

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

解法

座標が出てくるが、実際は点同士の左右の関係だけが必要なことや、点から点へ移るということからグラフに落とせそうな感じがする。しかし普通に点をそのまま頂点としてペアを辺で結んでも何ら嬉しいことはないので工夫が必要。

そこで、2N個の点によって分けられる2N+1個の区間を頂点とし、ある区間から出る辺はその区間の右端点からテレポートした先の点を左端点とする区間へのものとする。そうするとそのグラフは1本の経路と複数(0個かもしれない)のサイクルからなることがわかる。

新たなペアを付け加えるとこのグラフに何が起きるかを観察すると次のようなパターンがあることがわかる。

  • 同じ連結成分に属する「同じ」区間にそれぞれ新たな点を置くと、その連結成分の辺数が1本増え、さらに1本の辺からなるサイクルが1つ新たに生まれる。
  • 同じ連結成分に属する2つの「異なる」区間にそれぞれ新たな点を置くと、その2つの区間の間の辺がすべてスキップされる。
  • 違う連結成分に属する2つの区間にそれぞれ新たな点を置くと、その2つの連結成分が合体する。

すると最初のケースでは獲得できる得点が1増え、2番目のケースではその2つの区間の間の辺の数-1だけ得点が減り、3番目のケースでは新たに合体する連結成分の辺の数+2だけ得点が増える。

よって基本的には3番目のケースになるように新たにペアを加えていけばよいが、そのうち連結成分が全て合体して1つになってしまう。そうなったら今度は最初のケースのように新たにペアを加え、その結果できた辺数1のサイクルを3番目のケースを使ってまた合体させるということを繰り返せば良い。

続きを読む