Loading [MathJax]/jax/output/CommonHTML/jax.js

目次

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

AtCoder Beginner Contest 211

夏の競プロは蚊が天敵

D - Number of Shortest paths

D - Number of Shortest paths

問題

解法

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

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

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

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

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

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

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

Python3

E - Red Polyomino

E - Red Polyomino

問題

解法

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

まぁ、全探索とはいえ N2 マスから 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から取り出した状態につき、

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

Python3

F - Rectilinear Polygons

F - Rectilinear Polygons

問題

解法

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

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

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

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

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

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

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

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

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

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

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

Python3