F - I hate Shortest Path Problem(AtCoder Beginner Contest 177)

問題リンク

atcoder.jp

問題概要

 \(H+1 \times W \)マスのグリッドがある。

グリッド上は右か下に移動できる。

ただし、上からk行目からk+1行目に移動する時、左から\(A_k\)マス目から\(B_k\)マス目の区間で下方向に移動するのは禁止されている。

一番上のWマスのうちのいずれかからスタートして、k+1行目に到達するまでの最小移動回数を\(1 \leq k \leq H\)に対して求めよ。到達不可能ならば-1を出力せよ。

解法

縦移動の回数は決まっているので、横方向の最小移動回数を求める。

各行のWマスに対し、「その地点に到達するのに必要な横移動の最小回数」を上から順に更新していくことを考える。

区間最小値を求めるsegtreeを使う。

segtreeの中の要素を\(s[i]\)で表す。

k-1行目まで処理したとする。

この時、\(A_k \leq i \leq B_k\)に対し、\(s[i]\)を\(s[A_k - 1]+(i-(A_k - 1))\)で更新すれば良い。(禁止されていないギリギリの区間から回り込むイメージ。\(A_k=1\)の時は別途処理)

これを素直にやると更新が\(O(HW)\)回発生するので高速化する。

sは「1ずつ増加する」いくつかの区間に分割でき、1回の更新で1個の区間で上書きされる。

このような「中身が単純な区間で上書きする」タイプの更新は、区間の端点だけをsetで管理するのが有効(今回は始点だけで良い)。

\(A_k - 1\)と\(B_k+1\)での値を保存しておけば、残りは最小値となり得ないので、setから削除し\(s[i]\) をinfで更新してしまえば良い。

端点の追加・削除の合計回数は\(O(H+W)\)になり、segtreeやsetの操作でlogがつくが十分間に合う。

初期値では、1,...,Wの全てが区間の始点としてsetに全て入れておくと実装が楽になる。

提出

https://atcoder.jp/contests/abc177/submissions/16363990

感想

持ってないデータ構造(なんとかセグ木とか)を使いそうな気がしてめちゃくちゃ焦った。

F - Range Set Query(AtCoder Beginner Contest 174)

問題リンク

atcoder.jp

問題概要

\(N\)要素の数列\(c_1,...,c_N\)が与えられる。

以下の\(Q\)個のクエリを処理せよ。

• クエリ\(i\)：\(c_{l_i}\)から\(c_{r_i}\)までの要素の種類数を答える。

解法

 要素数は\(r_i - l_i + 1\)なので、これから同じ要素が重複している分だけ引くことを考える。

\(c_j=c_k\)かつ\(j\)と\(k\)の間に同じ値の要素が存在しないような全てのペアに対し、

区間\([l_i,r_i]\)が\([j,k]\)を完全に含んでいるようなペアの個数を引く、という方針で考える。

上のような\( (j,k) \)の組み合わせは\(O(N)\)個あるので、効率的に処理する必要がある。

また、「区間を完全に含んでいる」は「\(l_i \leq j \)かつ\(k \leq r_i\)」という2つの条件が絡んでいるので面倒である。

こういう時は、片方の条件が常に成り立つようにソートをして点を追加しつつクエリに答えることで上手くいくことがある。今回の場合、

• 全ての区間(\([l_i,r_i]\)と\([j,k]\)たち)を左端に関して降順にソート。
• ただし等しい場合は\([j,k]\)が先にくるようにする。
• \([l_i,r_i]\)が来た時は、それまでに登場した\(c_k\)のうち\(r_i\)以下であるような物の個数が含まれる区間の個数なので、i番目のクエリの答えは\( (r_i - l_i + 1) \)からその個数を引いたものになる。

左端の降順に並べたことで、それまでに追加された点に対し\(l_i \leq j\)が常に成り立っていることが肝心である。

後は、点を追加しつつ、ある値以下の点の個数を答えればよいので、これはBITを使えば求められる。

提出

https://atcoder.jp/contests/abc174/submissions/15624952

感想

最初累積和の変形で考えたのでかなりタイムロスした。

上位陣がめちゃくちゃ速いし典型っぽい。

(追記：Mo's algrorithmというのがあるそうです)

E - M's Solution(M-SOLUTIONS プロコンオープン 2020)

解説と異なる解法でした。

問題リンク 

atcoder.jp

問題概要

平面上にN個の集落があり、各集落iは座標\( (X_i,Y_i) \)にあって重み\(P_i\)が与えられている。

また、X軸とY軸には線路がある。

この時、X軸またはY軸に平行な線路をK本追加して、「重み×最も近い線路までの距離」の和Sを最小化したい。

最小値を\(K=0...N\)まで求めよ。

解法

線路は集落を通るように敷くのが最適なので、候補は実質2N本しかない。

片方の向きの敷き方を固定して、もう片方の向きの線路の敷き方はDPする。

集落はX座標の昇順にソートしておく。

X軸に平行な線路( \(y=Y_i\) )の敷き方を1つ決め打ちし、最初に敷いてしまう。

この時点での距離の最小値を各集落に対しまず求めておく。

次にY軸に平行な線路( \(x=X_i \) )の敷き方に関してDPを行う。

\(dp[i][j][k]\) = (i番目の集落まで見て、最後に敷いた線路が集落jを通り、既に線路をk本敷いている時の集落jまでのSの最小値)

とする。(ただしj=0は線路を敷いていないとする)

この時\(j < i\)ならば

\(dp[i][j][k] = dp[i-1][j][k]\)

である。

また新たに集落iを通る線路を敷く事を考えると

\(dp[i][i][k+1] = min \{0 \leq j \leq i-1 | dp[i-1][j][k] + \sum_{l = j+1}^{i-1} P_l \times (集落lの距離) \} \)

となり、集落lの距離は前計算した物と集落j,iを通るものだけを考えれば良い。

\( dp[N][j][k] + \sum_{l = j+1}^{N} P_l \times (集落lの距離) \)

の最小値がこの場合での本数kでのSの最小値になる。

これを\(y=Y_i\)の敷き方\(2^N\)通り全てに対し試せばよい。

計算量は\(O(2^N N^4)\)になる。

定数は軽いが906msだったので結構危ない。

(7/26 追記：Σの部分を使いまわしたら普通にループが一個外せた。\(O(2^N N^3)\) で624ms。)

提出

https://atcoder.jp/contests/m-solutions2020/submissions/15448869

https://atcoder.jp/contests/m-solutions2020/submissions/15460557(7/26 追記)

感想

 Nが小さいせいで色々解法が浮かぶのでかえって方針に悩んだ。

解説の方法は「\(3^N N^2\)だしなぁ」と思って切り捨ててしまった。