第一回 アルゴリズム実技検定(PAST) 感想

　クレジットカードを持っていなかったので課金できず(?)、バーチャル参加をしました。179:50で全完、ひどいハマりかたをしたところはあったけどまあ自分の実力的にはこんなもんかなと思います。簡単に感想と解説を書いておきます。そのうち出る公式解説が丁寧だと思うので、あまり参考にならなさそうだけど...。提出はこちらで、言語はC++です。

A

　stringで読んだ後、islower()で小文字があるかを判定、なければstoi()で整数に変換して2倍する。ある程度関数をちゃんと知っていると楽。

B

　書いてある通りに。

C

　sortして上から3番目を出力する。

D

　各数が何回現れたかをカウントして、すべて1ならCorrect、そうでないなら回数が0のものが回数が2のものに変わったということなので、それを出力する。

E

　ハマった(は？)。書いてある通りにやるのだが、クエリ3の処理でフォローすべきユーザーを列挙してから更新を行わないとだめ。順番に更新を行ったためにサンプルが合わず頭を抱えていた。

F

　Aと同様、islower()とisupper()で大文字小文字判定ができる。指示の通りに文字列を分割してsortをするが、sortの際に小文字に揃えておいて、後で大文字に直すみたいなことが必要なので注意。自分は(小文字の配列,文字のid)でソートしてよしなにやった。

G

　 3 ^ {N}の全探索。dfsでもよいし、bitで集合を管理するやつでもできる。提出参照。

H

　遅延セグ木を貼ってしまったが、その必要はない。「偶数/奇数の中での残りの数の最小値」と「偶数/奇数について、クエリ2または3でどれだけの量が出荷されたか」ということを表す変数を持っておくと、売れるかどうかの判定はこれらの変数をもとに判定できる。よって、この問題はO(N+Q)で解ける。そもそもこの発想が遅延セグ木っぽいんだけど...。

I

　この問題と全く同じ。dp[i番目のセット販売まで見た][手に入れた部品の集合]でdp。

J

　少し悩んだ。整備することにしたマスの集合は、「ある1点を始点とした点(H,1),(H,W),(1,W)に伸びている、互いに始点以外をを共有しない高々3つのパスの分解できるようなもの」だけを考えればいいことがわかる。よって、始点を全探索してDijkstra法で上記3つの点への最短距離を求めてその和を取ればよい(始点の値も足す)。

K

　LCAを貼ってしまった。貼らずにやるなら、根からdfsをして、初めてその頂点を訪れるタイミングin _ vと、最後にその頂点を訪れるタイミングout _ vをメモしておく。すると、aがbの子孫である条件はin _ b \lt in _ a \lt out _ bとなる。

L

　少し悩んだ。大きい塔だけを頂点と見たグラフで最小全域木を作るみたいな感じだが、それだけだと小さい塔を使うと得をする場合の扱いが難しい。よく考えると、小さい塔を使うことがあるなら、使った小さい塔たちは当然大きい塔たちとも連結であるはず。だから、使うことにした小さい塔の集合を決め打つと、大きい塔と(使うことにした)小さい塔を含めたグラフの最小全域木のコストが答えの候補になる。bit全探索+クラスカル法でOK。

M

　お　ま　た　せ
　平均最大化といえば二分探索。モンスターの強さk以上を達成できるかを判定。これは\rm{(魔力の和)} - k\rm{(質量の和)\geq 0}と同値なのでこれを判定する。使うお助けモンスターを決めるとあとはdp[何体目まで見たか][何体使うことにしたか]というdpで上記の量の最大値を求め、この値が0以上ならkが達成可能とわかる。計算量はO(NM\log{ans})。

N

　Wがでかいことをとりあえず忘れる。ある区間を石がないようにするために必要なコストは、(すべての石のコストの総和)から(その区間と共通部分をもたないような石のコストの総和)を引いたものになる。後者の値は、l _ i:右端がiより左側にある石のコストの総和とr _ i:左端がiより右側にある石のコストの総和 をあらかじめ累積和みたいな感じで計算しておくとO(1)でわかる。
　今述べた方針で全探索できそうだが、ここでWが大きいことを思い出すと、これでは間に合わない。よく考えると、区間の候補としては左端や右端が、ある石の左端や右端と同じ位置にあるものだけを考えればいいので、座標圧縮をしておけば区間の候補がO(N)になって間に合う。ちょっと添え字とかがめんどくさい。半開区間を信じる。

O

　これと似ている。出目の大小しか関係ないので出目は座標圧縮しておく。dp _ iを直前に出た目がiのときに振れる回数の期待値の最大値、とすると、iの大きい順に更新していけば遷移できる。何も考えないと遷移がO(N)で間に合わないが、どのサイコロを振るべきかを考えると、当然振る回数の期待値が最大であるようなものを振るべきである。各出目に対応するサイコロは1つなので、dp _ iを更新した後に、対応するサイコロについて「このサイコロを振るとどれくらいの期待値ががもらえるか」という値を加算しておくと、遷移がO(1)、セグ木とかを使うとO(\log{N})でできるので間に合う。セグ木に投げる関数をmymaxという名前にしてたのに中身は加算にしていて、20分くらい時間を溶かした...。

だいたい典型だと思えたのでよかった。割と楽しかった。実装は、遅いね...。