AtCoder Beginner Contest 211 D,E,F問題メモ

AtCoder Beginner Contest 211

夏の競プロは蚊が天敵

D - Number of Shortest paths

問題

  • $N$ 頂点 $M$ 辺のグラフが与えられる
    • 単純であることは保証されるが連結であるとは限らない
  • 辺のコストは全て1として、頂点 $1$ から $N$ への最短経路は何通りあるか求めよ
  • $2 \le N \le 2 \times 10^5$
  • $0 \le M \le 2 \times 10^5$

解法

DijkstraやBFSなどで最短距離を求めるとき、各頂点への「最短距離」の配列を管理するが、 最短経路のパターン数を求める場合は、「パターン数」も一緒に管理する。

  • dist[v]: 頂点 $v$ への(暫定)最短距離
  • pat[v]: 頂点 $v$ への距離が $dist[v]$ であるような経路のパターン数

queueから取り出した頂点 $v$(最短距離が確定した頂点)から、隣接する頂点 $u$ へ伸ばすときを考える。

$v$ を経由して $u$ に至る距離を $d=dist[v]+1$ として、

  • 既に $u$ への最短距離で、$d$ より短いものが見つかっている場合($dist[u] \lt d$)
    • 何もしない
  • 既に $u$ への最短距離で、$d$ と同じものが見つかっている場合($dist[u] = d$)
    • $pat[u] += pat[v]$
  • まだ $u$ が未探索、または $d$ より長いものしか見つかっていない場合($dist[u] \gt d$)
    • $pat[u] = pat[v]$
    • queueに $u$ を追加

とすれば、通常の最短経路探索と比較して無駄に探索範囲を広げることなく、パターン数も求められる。

今回は辺のコストが全て1(正)なので、queueから $u$ が取り出される前には $dist[u]$ も $pat[u]$ も全て網羅されていることが保証される。

ただし、辺のコストに $0$ があったりすると、 $u$ にコスト0の辺を使って到達できる経路がまだある状態($pat[u]$ が確定していない状態)で $u$ がqueueから取り出されてしまうことがあり得る。

その場合は無向辺ならパターン数は無限大になるので問題の体を為さなくなるし、 有向辺ならコスト0の辺だけで最初にトポロジカルソートなりして、 距離が同率の場合はソート順にqueueから取り出せばいいのかな?

Python3

E - Red Polyomino

問題

  • $N \times N$ のマス目が与えられ、マス $(i,j)$ は $S_{i,j}$ が'#'なら黒く、'.'なら白く塗られている
  • 白く塗られたマスを $K$ 個選んで赤く塗る
  • この時、赤く塗られた $K$ マスが全てタテヨコにひとつながりになっているパターン数を求めよ
  • $1 \le N \le 8$
  • $1 \le K \le 8$

解法

$N,K$ が小さいのである程度全探索的なことを考える。

まぁ、全探索とはいえ $N^2$ マスから $K$ マス選ぶ方法を全探索して連結が調べる、なんてのはさすがに無理。

サンプル3が優しくて、パターン数が最大である $N=8,K=8,$ 全マス白マスのケースが64678しかないことを教えてくれている。

なので、「赤く塗ることを仮定するマスは常に連結」となるように探索範囲を広げていけば、そこまで状態数は大きくならなさそう。 マスの数も64個で、丁度64bit整数に収まるので、 bitフラグで赤く塗ることを仮定した頂点を管理することにする。

N=4
  0 1 2 3      4,8,9を赤く塗った状態を表す整数
  4 5 6 7  →    5432109876543210
  8 91011      0b0000001100010000  =  784
 12131415

探索済みの状態の集合 checked をsetで管理しておく。

まず、白マスを1マスだけ塗った状態を全てqueueに突っ込む。

queueから取り出した状態につき、

  • その状態で赤く塗られているマスを復元する
  • 上下左右に隣接している白マスから新しく1マスを赤く塗った状態に遷移する
    • 遷移後の状態が既に checked ならスキップ
    • そうでなく、$K$ マス塗られた状態なら、答えに+1カウント、checked に追加
    • そうでないなら、queueとcheckedに追加

としていけば、求められる。

Python3

F - Rectilinear Polygons

問題

  • 二次元平面上に $N$ 個の多角形がある
    • $i$ 個目の多角形は $M_i$ 角形で、各頂点の座標も与えられる
    • 多角形は単純(連続しない2辺が公差や接触していない)
    • 全ての多角形の辺は、$x$ 軸または $y$ 軸に平行
    • 頂点の座標は順に与えられるが、時計回りか反時計回りかは不明
  • 以下の $Q$ 個のクエリに答えよ
    • 座標 $(X_i+0.5, Y_i+0.5)$ には、いくつの多角形が重なっているか?
  • $1 \le N \le 10^5$
  • 全多角形の頂点数の合計 $\le 4 \times 10^5$
  • $0 \le $ 多角形やクエリの $x,y$ 座標の値 $\le 10^5$

解法

クエリ先読みでイベントソート。

「多角形のうち垂直な辺」「クエリ」を全てまとめて $x$ 座標でソートする。

1つの多角形の1つの垂直な線が $Y_1~Y_2$ まで引かれていたとして、 ここを境として左と右では、$Y_1~Y_2$ に対するクエリの答えが+1または-1される。

$x$ 座標の小さい方からFenwick Treeなどで管理してやれば、

  • 多角形: 区間 $Y_1~Y_2$ に1または-1を加算する
  • クエリ: 現時点の $Y$ の値を求める

という区間加算の問題に変わり、各操作を $O(\log(座標最大値))$ で処理できる。

さて問題は、各多角形の垂直な線が+1(外から内)なのか-1(内から外)なのかをどうやって判定するか。
これは、座標の与えられ方が時計回りか反時計回りかに依存する。

  • 時計回りなら、与えられた順で↑向きの辺で+1され、↓向きの辺で-1される
  • 反時計回りなら、↓向きの辺で+1され、↑向きの辺で-1される

では、時計回りか反時計回りかをどう判定するか。
最初の3点が右に折れ曲がっていたからといって、時計回りとは限らない。

④←←③
↓    ↑    ⓪→①→②だけを見ると右に折れ曲がっているが、
↓①→②    座標の与えられ方は反時計回り
↓↑
↓⓪←⑦
↓    ↑
⑤→→⑥

多角形の座標を全て $(x,y)$ でソートすれば、一番左下にある垂直な辺を取り出せる。(図では④→⑤)

この辺は一番左下なので、(当然だが)もっと左を回り込むような辺は無い。
なので、必ず外→内の辺である。

これが上向きなら時計回り、下向きなら反時計回りだといえる。

Python3

programming_algorithm/contest_history/atcoder/2021/0724_abc211.txt · 最終更新: 2021/07/24 by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0