第4回アルゴリズム実技検定 感想+解法

序盤の問題の読解や細かい設定がつらい感じで序盤でかなり時間を使ってしまった。反面後半の問題で詰まることはあまりなく、全体としてはスムーズに解けたと思う。(100分41秒)

A:vectorにpair持たせてソートした。

B:100倍した。

C:全探索

D:左、右に絶対に行く必要のある回数の最小値がそれぞれ分かる。それでカバーできているか判定する。

E:全探索

F:mapに突っ込む

G:全探索

H:全探索を累積和で高速化

I:全探索と累積和とにぶたんで高速化

J:超頂点用意してdijkstra

K:各数列について転倒数と各数字の数を求めておく。数列に数列を追加する度にそれら情報を使って加算、更新する。

L:偶奇クエリと一点クエリを分けて考える。隣接する要素の差(ただし、添え字が奇数のものから偶数のものを引く)をmapに突っ込んでおく。

M:LCA+imos+マージテク

N:dp[i行目まで見て][i-2行目のbit][i-1行目のbit][i行目のbit]のときの通り数を上から更新していく定数倍軽めのO(2^{4W}*HW)の解法をとりあえず書いて高速化するか～って言ってコードテストで最大ケース試したら間に合ってしまった。

O:dp[i番目まで開錠したかしてないか決まってて、i+1番目以降施錠されているときの]=利益の最大値にi+1番目以降の宝箱による利益の総和を足したものを持っておく。人を右端でソートしてセグ木で更新。