第二回 アルゴリズム実技検定 解説記事

A 今地上にいるかいないか、目的地が地上にあるかないか4通り場合分けします。

B それぞれの文字が何個あるか見ます。

C 下の行から順に見ていき、Xを見つけたら右上、上、左上のそれぞれについて空白でなければXにします。

D 文字列全部列挙してSのすべての開始位置について一致しているか見ます。

E シミュレーションをします。移動経路をグラフにすると、明らかに有向サイクルになるのでN手以内に戻ってくることが分かります。

F 常に今選べるタスクの中で得られるポイントが最大のものを選ぶのが最適です。

G dequeを使うと追加も削除も効率良くできます。

H スタートを0、ゴールを10と考えて、すべてのマスについて、自分以下の数字を一度以上踏んでいるときの最小の移動回数を考えます。

I シミュレーションをします。一人当たりの試合回数は高々N回なので間に合います。

J 最初の閉じ括弧が見つかったときに、その括弧対について操作を行います。操作回数は高々N回なので間に合います。

K dp[i文字目まで見て][開き括弧の余剰がj個のときの]コストの最小値を考えます。

L 常に今取っても今後破綻しないようなものの中で最小のものを、最小のものが複数存在する場合は一番左のものを取るのが最適です。

M 日をMOD Dで考えます。すべての日について、次に同じ種類の定食を食べるまでに何回食堂に行くかを求めます。それは各種類の定食が出る日付を持っておくと分かります。その情報が分かるとダブリングが出来るので各人について答えをO(logD)で求められます。

N あるx座標を含むような敷地集合(Xとする)が分かっているとき、あるy座標を含むような敷地集合は敷地のy座標の最小値でソートしたものと、敷地のy座標の最大値でソートしたものを持っておくと、二分探索などで求めることができます。また、そのような集合のコストはセグメントツリーなどを用いると高速に計算できます。x座標を単調に変化させるとき、各敷地は1回ずつXに追加され、1回ずつXから削除されます。なので、クエリをx座標の昇順に見るとXへの追加と削除にO(N)かかり、各クエリの処理にO(log N)かかります。

O 最小全域木で根付き木を作って、全域木に使われている辺については、全域木のコストが答えです。そうでない辺については、全域木に含めて、その辺の端点間のパス上の最大の辺を消すのが最適です。そのような辺はダブリングなどで求めることができます。