第五回アルゴリズム実技検定

A

ooo..

.ooo.

..ooo

B

(問題文の通りに実装しても O(N^2) で間に合う)

S を後ろから見て、各文字ごとに、最初に見たものだけ残す方針で T が得られる O(N)

C

2 進 ⇔ 10 進の変換を知っていればできると思う

D

ソートの比較関数を作る

かなりバグらせてしまった

E

なかなか大変

グリッドを 90 度回転する関数を用意

S の周りを障害物マスで埋める

をして、ハンコの向き・位置について全探索

F

2^N 全探索

G

始点を全て試して、ヘビの伸ばし方を DFS 的に全探索

計算量がよく分からないけど H, W ≦ 4 なので大丈夫そう

苦手

H

以下が同じ

「各マスからゴールへ到達できるか」

「辺を逆向きにしたグラフで、ゴールから各マスへ到達できるか」

I

DP

標高が低い村から答えが確定していく

J

再帰系の問題?で、苦手

K

きちんと式を整理しないまま実装を始めてしまい破滅

確率系問題の中では易しめに見えるので時間内に正解したかった

L

かなり自然な全探索をメモ化 (思いつきたかった)

M

「数列をいくつかの区間に分割して、それぞれの区間和を s 以上 t 以下にできるか」という問題になる

(そもそも、ここの整理ができてなかった)

添字の ±1 を合わせるのが難しくて苦手

N

「頂点 B から行ける最右の頂点」≒「頂点 B より右で、一番近い通れない辺」

辺の通れる・通れないの管理は、イベントソートの要領でできる

A の小さい順にクエリを処理することにして、クエリに答える前に

L ≦ A の辺を通れるようにする

R < A の辺を通れないようにする

という感じ

O

「未読数=全体-前回までの既読数」