naoya_t@hatenablog

いわゆるチラシノウラであります

JOI - 第11回日本情報オリンピック〈本選〉の問題を解いてみた日曜日

本選問題文・サンプル入出力などこちらから入手可能です。(2012-ho.pdf に問題文があります)

全部で5問&制限時間4時間。
日曜日の退屈しのぎに最適!と思って5問解いてたら4時間掛かっちゃってるのであれだけど…

ちゃんと時間計測してなかったけどファイルのタイムスタンプから推測すると所要時間はこんな感じ:
(オレオレサンプルケースジェネレータの制作時間を含む)

  • 問題1: 20+分
  • 問題2: 50+分
  • 問題3: 55+分
  • 問題4: 20+分
  • 問題5: 100+分

それぞれの解法とか実装については誰かが書いてるんじゃないかなと思うので、ざっくりメモだけ残します。合ってるかどうかは保証しません。

1. JJOOII (JJOOII)

最大100万文字から成る文字列から /J{k}O{k}I{k}/ な文字列を探し、最大のkの値を求める問題。
RLEした後で状態遷移してみた。

  • 振り出し(J待ち)
  • J+ が来た →「長さ1〜kのO待ち」
  • O+ が来た → 「長さk以上のI待ち」or「振り出しに戻る」
  • I+ が来た →「長さkのJOIキタ━(゚∀゚)━!」or「振り出しに戻る」
  • 「長さkのJOI」→ kがこれまでの最大値より大きければ更新。振り出しに戻る。

2. たのしいカードゲーム (Card Game is Fun)

配列Aの部分配列(途中スキップ可)と配列Bの部分配列(途中スキップ不可)の最長一致。DP。

  • f(a, b) で配列Aの[a..$]と配列Bの[b..$]の最長一致の長さが求まるとする。
    • A[a] = B[b] なら 1+f(配列Aでa以降に出てくるB[b+1], b+1)
    • A[a] ≠ B[b] なら max( f(配列Aでa以降に最初に出てくるB[b], b), f(a, 配列Bでb以降に最初に出てくるA[a]) )
  • f(a, B) = f(A, b) = 0
  • 求めたいのはf(0,0)

それぞれの数字の出現位置(集合)を取っておくと捗る。

3. 夜店 (Night Market)

ナップサック問題。ナップサックの内部に1つ仕切りがある感じ。DP。
店番号の小さい順に回るという制約を飛ばしていて、計算量すこし多めの問題を解いてました><

  • メモリ的には 2次元配列が2面あれば行けるので dp[2][S+1][(T-S)+1] で、dp[i%2][花火前に遊んだ時間][花火後に遊んだ時間] が楽しさの総和。
  • 店番号の小さい順 ←→「花火後に遊んだ時間 > 0 なら花火前に遊んだ時間は増やせない」

4. 釘 (Nails)

パスカルの三角形みたいな感じに釘が刺さってて、輪ゴムで色々な形(と言っても上が尖ってるやつだけ)の正三角形に囲まれていて、輪ゴムに囲まれている釘の本数を求める。
これは割とすんなり解けた。DP。
釘が刺さっている三角形の1辺の最大長が5000、ということは釘最大12502500本。
そして輪ゴム50万本。餃子の王将のCMを彷彿とさせる。

  • 輪ゴムがかかってる釘にXiを、かかっていない釘に-1をセット。×500000
    • 同じ釘が上の頂点になる輪ゴムは最大のもので代表できるので本数が減ることがある
  • 上から見ていく ×12502500
  • 釘(Ai, Bi)の値Xiが0以上なら答++
    • 下の2本の釘(Ai+1, Bi), (Ai+1, Bi+1)の値をそれぞれXi-1と比較し、Xi-1の方が大きければ上書き

5. JOI 国のお祭り事情 (Festivals in JOI Kingdom)

やるべき事は

  1. それぞれの街Xiについて、最寄りお祭りタウンからの最短距離(お祭り距離 df[Xi]とでもしよう)を算出しておく。ダイクストラでおk。
    • スタート地点、というか距離0のノードがが複数ある感じ
  2. 各クエリについて、Si から Ti への経路を求めるのだけれど、まあダイクストラの変形なんだけど、
    • Siからの距離を入れる配列d[N]の初期値は-1で、d[Si] = df[Si]
    • お祭りから遠い選択肢から見ていきたいので、降順のpriority_queueで、そこまでの経路のお祭り距離(=通過した街のお祭り距離の最小値)を探索上の距離としながら進める。(経路のお祭り距離は経路を進むと必ず減少していくので、最短距離を求める要領を昇降逆にすればそのまま適用可能)
    • キューの先頭にある街Xiから伸びる道路それぞれについて、道路の行く先Xjと、min(df[Xj], Xiまでの経路のお祭り距離) をqueueに投入
    • Tiに着いたら終了

計算量的にはステップ1(1回だけ)が O(N^2)、ステップ2(クエリの回数だけ)が O((M+N) log N)×クエリ数Q なので実装にミスがなければ問題なさそう。

追記:みんなLCAとか言ってる… 要再考。