WUPC の私的解説

550 点しかとれなかった分際で解法の説明をするのはいかがなものかという気はするが，参考にしてくれる人がいるかもしれないので，簡単に解説しておこうと思う．

問題はこちら．コードについては前の記事にリンクがあるので，必要であればそちらを参照いただきたい．

A

俗に言う「やるだけ」．Σ[k=1:n] k^2 = n(n+1)(2n+1)/6 を使っても構わないが，項数はたかだか 100 なのだから素直にループを回そう．大学でプログラミングの講義をひととおり受けたのであれば（時間はかかってもよいから）正答したい．

B

基本的な貪欲法の問題．歩数は関係ないことから，「とにかく前に出たほうが得」という事実に気づくことがポイントになる．

水たまりになっていないマスがあったらすぐさま足をつけて構わない．たとえば，1 歩先と 3 歩先に水たまりではないマスがあるとき，1 歩先のマスを踏んでから 3 歩先のマスに向かおうと，いきなり 3 歩先のマスに向かおうと，水たまりを踏んでいないことに変わりはない．

3 歩先まですべて水たまりのときは，とりあえず 3 歩先に進む．1 歩先，あるいは 2 歩先から行けるマスには，3 歩先にあるマスからでも必ず行けることに注意しよう．

なお，ごく基本的な動的計画法の問題とみなして解くこともできる．

C

ケーキは 30×30 と十分に小さいので，全部のパターンを調べ上げる，というのが基本戦略になる．問題はどうやってパターンを尽くすかである．

こういうときは，項目をひとつずつ「決めうち」しながら考えよう．とりあえずは三角形の位置を固定するところから始めるとよい．そこで直角部分の位置を固定することにすると，三角形の向きは以下の 4 通り存在する．

        o    o
       oo    oo
      ooo    ooo
     ooox    xooo

     ooox    xooo
      ooo    ooo
       oo    oo
        o    o

あとは大きさだけ決めれば，三角形が具体的にひとつ決まって，満足度を計算できる状態になる．これは大きさが 1 の場合，大きさが 2 の場合，…という具合に，三角形の頂点がケーキの端に達するまで順番に調べればよい．なので，まとめると

左下の位置に関してループ → 方向に関してループ → 大きさに関してループ

といった手順になる．雑に見積もって 30×30×4×30 = 10 万回ぐらい，それと満足度を計算するのに 30×30÷2 = 450 回ぐらい，全部で 4500 万回ぐらいループを回すことになるが，今どきの計算機ならば全然平気なので心配する必要はない．なお，ループの順番は入れ替えても本質的に同じなので，実際の実装では位置→大きさ→方向の順番にしたほうが 4 方向のパターンを（ループにしないで）べた書きできるようになって都合がよい．

…というのが基本的な話．実を言うと，私が提出したコードは上の方針には基づいていない．直角でない側の頂点を基準にとったほうがコードは簡単になるからである．その場合，三角形の向きは 8 通りになる．

      oooo    oooo                o          o
       ooo    ooo                 oo        oo
  (a)   oo    oo   (b)        (e) ooo      ooo (f)
         x    x                   ooox    xooo

         x    x                   ooox    xooo
  (c)   oo    oo   (d)        (g) ooo      ooo (h)
       ooo    ooo                 oo        oo
      oooo    oooo                o          o

…はずなのだが，右半分のパターンについては調べる必要がない．これは直角でない頂点はふたつあって，反対側の頂点が基準となったときに左半分のパターンのいずれかとして認識されるからである．たとえば，下図の左側は (e) のパターンに該当するが，右側を見ればわかるように，このケースは別の場所で (d) のパターンとして現れる．同様にして (f)→(c)，(g)→(b)，(h)→(a) の対応関係がある．

    ........    ........
    ..o.....    ..x.....
    ..oo....    ..oo....
    ..ooo...    ..ooo...
    ..ooox..    ..oooo..
    ........    ........

また，大きさに関しては，「ケーキの端に到達したら」ではなく，「切り分ける部分にいちごが入ってしまったら」という条件で打ち切っている．とはいえ，いちごがないと三角形がケーキの外側にはみ出してしまうので，はじめに与えられたケーキの外側をいちごで囲んでいる．

              XXXXX
    433       X433X
    333  -->  X333X
    333       X333X
              XXXXX

ちなみに，上のいちごのように，外側にはみ出ないように便宜的に置かれた邪魔物のことを番兵という．

D

ちょっとした数学パズル．

  • 大きさ 5 のオブジェはどう考えても別々のコンテナに入れるしかないし，そのコンテナにほかのオブジェを詰めることもできない．
  • 大きさ 4 のオブジェも別々のコンテナに入れるしかないが，隙間に大きさ 1 のオブジェを詰めることはできる．詰められるオブジェの数は最大で (5^3 - 4^3) = 61 個．
  • 大きさ 3 のオブジェも別々のコンテナに入れるしかないが，隙間に大きさ 2 のオブジェを詰められる．大きさ 3 のオブジェを左手前下側の隅に置くことにすると，上側にできる高さ 2 の隙間に 4 個，その下側に下図の要領で 3 個，合計で 7 個まで詰めることができる．できた隙間には大きさ 1 のオブジェを詰めて空間を無駄にしない．大きさ 2 のオブジェを詰め切ってしまったときも，大きさ 1 のオブジェが残っていればどんどん詰める．
  • この時点で大きさ 2 のオブジェが残ったときは，それを詰めるためのコンテナを用意する．コンテナひとつにつき 8 個まで入る．もちろん隙間は大きさ 1 のオブジェで埋める．
  • 隙間を全部埋めても大きさ 1 のオブジェが余ってしまったときは，仕方がないので大きさ 1 のオブジェ専用のコンテナを用意する．コンテナひとつにつき 125 個まで入る．
  .aabb    * = 大きさ3のオブジェ
  .aabb    a = 大きさ2のオブジェ
  ***cc    . = 隙間
  ***cc
  ***..

扱う数字が大きいので，C++/Java/C# などでは int だと桁あふれを起こす可能性があることに注意．代わりに C++ では long long を，Java/C# では long を用いること．*1

E

まずは部分点から．閉路がない，ということはグラフは森，要するに木がたくさん（全体が連結であれば単一の木）という状況なので，辺をひとつ消し去ると，その辺が含まれるグループ（連結成分）は必ずふたつのグループに分かれる．つまりどの辺を消しても構わないわけで，よって初期状態で何個のグループに分かれているか（何個の連結成分があるか）を数え上げて，必要数に満たない分だけコストの小さいほうから順番に辺を消去すればそれが答えになる．

あとは閉路をどうするかという話になるが，閉路はひとつしかないので，ここは閉路を解消するか放置するかでとりあえず場合分けする．

閉路を解消する場合．閉路に含まれる辺をひとつ消し去ってしまえば森になる（当然ながらコストが最小の辺を消去する）．あとは部分点のときと同じ．

閉路を放置する場合．閉路とは関係ない辺を消し去ったときは，やはり常にグループがふたつに分かれるので，閉路に含まれない辺の中からコストが小さいものを順に選んで消去するだけでよい．

なお，グループの個数を数えるには Union-Find 法（正確には素集合森）を用いるのが定石だが，頂点数が少ないので以下のような手抜きな方法も通用する．

vector<int> group(n);
for (int i = 0; i < n; i++) {
    group[i] = i;
}
for (const Edge& edge : edges) {
    replace(group.begin(), group.end(), group[edge.u], group[edge.v]);
}

グラフの基本を押さえた良問．

F

（現在位置）×（直前に進んだ方向）×（伝達済みの文字数）が状態になる．「直前に進んだ方向とは違うものでなければならない」という制約があるので，直前に進んだ方向が状態に含まれることに注意したい．

動的計画法が一番素直だと思うが，各状態を頂点とするグラフを形成してダイクストラを走らせても解けるし，幅優先探索をしても構わない（同一の状態を何度も訪れないように注意すること）．どれにしたって本質的には同じである．

「進行中に伝えたい文字が見つかったら，直ちに止まる」という条件を見落とさないように．つまり，a を伝達しようとしていて a のマスに到達したときに，「もっと先にあるマスのほうが都合がいいからこのマスは飛ばす」という選択はできない．

G

どう見ても BIT (Binary Indexed Tree) です．本当に（ry

詳しいことは蟻本あたりでも読んで欲しいのだが，この BIT というのは，長さ n の数値列があったときに，要素の値がちょくちょく変更されるような状況のもとでも任意の範囲の和が O(log n) 時間で計算できるようなデータ構造である．

一応部分点から．与えられた a[i] をすべて配列に格納する．add が来たら配列に要素を追加する．challenge が来たら，下から順に高さを合計していって，(arg - H) と (arg + H) がどのブロックに含まれるかを求める．その結果「go である」とわかったら，そのブロックに対応する要素を配列から削除しよう．ブロックの個数もクエリの個数も 1,000 個しかないから，合計を毎回計算してもループはせいぜい 1000×1000 = 100 万回ぐらいしか回らず，計算時間的には何の問題もない．下面すれすれ，あるいは上面すれすれというパターンがあるので，不等号の選び方には注意すること．

ここで，個々のブロックの高さの代わりに，1 番目から i 番目までのブロックの高さの和を配列に格納することにすれば，(arg - H) と (arg + H) がどのブロックにあたるかを求めるときに二分探索が適用できる．それでも，普通の配列を使っているうちは，ブロックが外れたときに和を全部更新しなければならないから O(NM) の呪縛から逃れられない．そこで，先に説明した BIT を用いれば，10 万個のブロックとクエリがあっても現実的な計算時間で終わりますよ，という寸法である．

BIT では値の削除はできないので，ブロックの高さを 0 に変更するという方法で対応する．ただし，こうすると「一番上だけはハンマーが上に飛び出していても構わない」という例外の判定がかなりトリッキーになる．「ブロックの上面の地面からの高さ」と「すべてのブロックの高さの合計」が等しければ一番上のブロックである，と判定するのが正解．ブロックのインデックスが (N - 1) のときが一番上で，一番上のブロックを叩いたときは N をデクリメントして…なんてやっていると，下のほうのブロックを外してから一番上を叩くというケースで大変な目に遭うので注意しよう．

H

列車を始点，終点の昇順にソートしておく．そのうえで，

dp(k)[u][v] ::= 列車 1〜k を使ったときに，駅 1〜u の全駅に 2 本以上の列車が停車して，駅 (u+1)〜v の全駅に 1 本以上の列車が停車するパターンの個数．（u ≤ v）

をうまいこと計算すればよいのだが，そのための漸化式がまあややこしい．
初期値として便宜的に dp(0)[0][0] ← 1 とする．列車 k の始点と終点をそれぞれ s と t で表すと，

  • とりあえず dp(k)[u][v] ← dp(k-1)[u][v]．
    列車 k を走らせないという選択は常に存在する．当然何も変わらない．
  • s < t ≤ u ≤ v のとき dp(k)[u][v] += dp(k-1)[u][v]．
    駅 1〜u に 2 本以上，駅 (u+1)〜v に 1 本以上という状況に変わりはない．
  • s ≤ u < t ≤ v のとき dp(k)[t][v] += dp(k-1)[u][v]．
    駅 (u+1)〜t が新たに 2 本以上停車するようになる．
  • s ≤ u < v < t のとき dp(k)[v][t] += dp(k-1)[u][v]．
    駅 u〜v に 2 本以上，駅 (v+1)〜t に 1 本以上停車するようになる．

u < s の場合は考える必要はない．というのも，はじめに列車を始点の昇順でソートしているため，この状態になった時点で (u+1)〜(s-1) に 2 本以上の列車を停車させることができなくなるからである．

dp(k)[u][v] という不思議な表記を持ち出したが，これは dp(k) を計算したら dp(k-1) は不要になるので，テーブルをふたつだけ用意してとっかえひっかえ使うこともできる，という意図がある．

とはいえ，このテーブルを二次元配列としてまともに確保しようとすると，40 駅しかないうちはいいが，10 万駅ともなれば 100,000^2×4×2 = ~80GB と今どきでも滅多に見かけないほどの量のメモリが必要になる．満点をとるには，二次元配列の代わりに (u, v) の組をキーとしたマップ（辞書）を使用する．列車が 200 本しかないため入力中に現れる駅数は限られており，そのためキーの個数もあまり大きくならない．座標圧縮という手もあるが，いい加減なことをやって途中の駅を消したりしないように！（出典）

I

10 点は気合いあるのみ，ということで 50 点の解法から．大きさ 500 の巣にはおよそ (500×500/2)×6 = 75 万個の六角形があるので，さすがに六角形のひとつひとつに 1 を加えていたのでは制限時間におよそ間に合わない．

この手の問題では「とりあえず状態が変化する位置だけを記録して，最後にまとめて個々のマスの値を計算する．」という手法をとるとうまくいく．ただし，この問題では行ごとに分けて考えたほうがよい．六角形の数は 75 万ほどになっても，行数ならば 1,000 にも満たないので計算時間的には余裕がある．

この問題で「状態が変化する」というのは，もちろん「糖度が増える」「糖度が減る」ということである．たとえば，

1 0 0 2

という巣があれば，

  • y = 1 → (-1, 1) で増，(1, 1) で減．
  • y = 0 → (-1, 0) で増，(2, 0) で減．
  • y = -1 → (0, -1) で増，(2, -1) で減．

となる．これを最後の入力例に含まれるすべての巣に対して適用すると，y = 0 の行では

  • (-1, 0) で増，(2, 0) で減．(0, 0) で増，(2, 0) で減，(-1, 0) で増，(1, 0) で減．

となる．このままでは個々の糖度を計算しにくいので，座標ごとにまとめて

  • (-1, 0) で +2，(0,0) で +1，(1, 0) で -1，(2, 0) で -2．

という形にすると，あとはそれぞれの行で左から右に向かって六角形をなめながら糖度を計算できる．たとえば，上の例からは

x ... -2 -1 0 1 2 3 ...
差分 ... 0 +2 +1 -1 -2 0 ...
糖度 ... 0 2 3 2 0 0 ...

が得られる．これは問題文の図 3 と一致する．

さて，このままではタイプ 2/3 の巣は扱えない．ここで，巣の糖度は定数，1 次式，2 次式のいずれかである，したがって各々の六角形の糖度は二次関数の部分関数の和で表せる，ということに注目する．たとえば，中心が (7, 0) で大きさ 5 でタイプ 2 の巣において，y = 2 の行（上から 3 行目）は

x ... 2 3 4 5 6 7 8 9 10 11 12 ...
糖度 ... 0 0 1 2 3 3 3 2 1 0 0 ...

という形になるが，これは

  • 3 ≤ x < 6 のとき f(x) = x - 3
  • 6 ≤ x < 8 のとき f(x) = 3
  • 8 ≤ x < 11 のとき f(x) = -x + 11
  • 上記以外のとき f(x) = 0

のように表せる．前出の部分点のときにならって差分を考えてみると，

x ... 2 3 4 5 6 7 8 9 10 11 12 ...
Δf(x) ... 0 x-3 0 0 -x+6 0 -x+8 0 0 x-11 0 ...
f(x) ... 0 x-3 x-3 x-3 3 3 -x+11 -x+11 -x+11 0 0 ...
糖度 ... 0 0 1 2 3 3 3 2 1 0 0 ...

とかなりわかりやすい感じの表が得られる．完全なアルゴリズムにするにはもう少し手順が必要になるが，そろそろ説明する気力が尽きてきたので，残りは読者の課題（笑）とさせていただきたい．タイプ 3 も同じように考えればよい（タイプ 2 よりもややこしいが）．多項式が現れているが f(x) = ax² + bx + c とおけば (a, b, c) の組だけを気にすればよいことに注意．足したり引いたりするだけで，乗算は現れないので難しく考える必要はない．

もう少し単純な類題が KUPC 2012 で出題されているので，そちらを先に解くのもよいだろう．

*1:当初は C++ も long でよいと書いていたが，Windows では 64-bit 環境でも long が 32 ビット幅であることを思い出したので記述を改めた．