AtCoder Beginner Contest 218 C,F,H問題メモ

C - Shapes

問題

  • $N \times N$ の2つのグリッド $S,T$ が与えられ、各マスは '.' または '#' である
  • $S$ の '#' を平行移動や90度回転移動を繰り返して $T$ の '#' に一致させられるか判定せよ
  • $1 \le N \le 200$

解法

pythonなら2次元配列の90度回転は以下で行えるので、上下左右の空白行をトリムした後で4通り試せばよい。

aaa = [(0, 1, 2),
       (3, 4, 5)]

list(zip(*reversed(aaa)))
# ↓
# [(3, 0),
#  (4, 1),
#  (5, 2)]

reversedを無くせば行列の転置になるので、その用途でも使える。

Python3

F - Blocked Roads

問題

  • $N$ 頂点 $M$ 辺の有向グラフが与えられる
  • 1辺は全て長さ1とする
  • 各辺につき、その辺のみが使えなかったときの頂点 $1→N$ への最短距離を求めよ
  • $2 \le N \le 400$
  • $1 \le M \le N(N-1)$

解法

計算量を正しく見積もり、経路復元できる最短経路探索をしましょう、という問題。

全辺長さ1なので最短経路探索はBFSが使えて、その計算量は $O(M)$。

全辺に対して愚直にその辺が使えなかったときの答えを求めていては、$O(M^2)$、つまり $O(N^4)$ かかるので無理。

だが、全ての辺が使える状態で1個最短経路 $P$(距離 $d$)を見つけてしまえば、 $P$ 上の辺以外が使えない場合は $d$ が答えとなる。

問題は $P$ 上の辺が使えなくなった場合だが、これは最大 $N$ 頂点のパスなので多くとも $N-1$ 辺しか無い。
これらについては再計算しても、全体で $O(NM)$ なので間に合う。

経路復元つきのBFSは、「その頂点に最短でたどり着いたときの1つ前の頂点番号(または辺番号)」を各頂点、記録しておく。

ゴール $N$ までたどり着けたらそこから始点 $1$ まで逆順に辿ることで、復元できる。

そもそも最初の状態で $N$ までたどり着けない場合のコーナーケースに注意。

Python3

H - Red and Blue Lamps

問題

  • 横一列に並んだ $N$ 個のランプの $R$ 個を赤く、残りを青く光らせる
  • 隣り合う2つのランプのペアは $N-1$ 個あるが、それぞれにつき「2つが異なる色で光っていたら $A_i$ 点」というスコアが決まっている
  • 赤く光らせるランプを適切に決めて、スコアの総和を最大化せよ
  • $2 \le N \le 2 \times 10^5$
  • $1 \le A_i \le 10^9$

解法

色自体に固有の意味は無いので、赤を少ない方(多くない方)と固定してよい。

すると、スコアは全て正であることもあり、赤を隣り合わせること、端に配置することは必ず損することがわかる。

0:赤  1:青

[赤の連続]
1 1 0 0 1 0 1 1 1
 x o x o o o x x   ← o:スコアが得られるAiの位置
 
      v v v v
1 1 0 1 0 1 0 1 1  右側を、次に1が連続する手前まで反転。
 x o o o o o o x   0の個数、oの位置はそのまま、新たに2箇所、oが増える
     ~       ~
  v v
1 0 1 0 1 0 1 1 1  (または左側を同様に反転)
 o o o o o o x x   同上
 ~   ~

[端の赤]
0 1 0 1 0 1 1 1
 o o o o o x x

v v v v v v
1 0 1 0 1 0 1 1    端から、次に1が連続する手前まで反転
 o o o o o o x     0の個数、oの位置はそのまま、新たに1箇所、oが増える
           ~
(赤と青が同数の場合を除く。その場合は全てのAiを得られる)

従って赤の位置を決めると、その両隣の $A_i+A_{i+1}$ が得られることになる。問題を言い換えると

  • $A_1+A_2,A_2+A_3,A_3+A_4,...$ という数列を新たに $B_i$ とする
  • 隣り合う2つの $B_i,B_{i+1}$ は同時に選べない
  • $B_i$ から $R$ 個選んで総和を最大化せよ

となる。

では言い換えた問題をどうやって解くか。

DPをするにも個数が決まっているので、DP[何個目まで見たか][何個選んだか][直前を選んだか] みたいになり、$O(N^2)$ となってしまう。

一定の条件を満たすグラフについて、ちょうど $d$ 辺を使う最短経路を高速に求める方法があるらしい。

グラフで表すことは可能なので、それでも解ける(けど概念が難しい)。

かくなる上は貪欲に選びたいが、組み替えが発生しうる。

R=3

Ai  10  100  101  50  51  11  1  2  3
         |----|    |---|                 上位2つはこのペアだが...

     |---|    |----|   |---|             3つ選ぶとなると、こう選ぶべき

貪欲に選んだときのこの組み替えを、どう修正するか?

求めたいのはスコアの総和なので、それらがどのAiのペアとして足しあわされたものかはぶっちゃけ関係ない。
そしてよく見ると、組み替える場合に新しく加算されるスコアは、必ず既に選ばれた区間を挟んだ両隣となる。
つまり、「組み替える」行為を、「既に選ばれた区間の両隣のスコアを得る」と考える。

Ai  10  100  101  50  51  11  1  2  3
         |----|    |---|                 これとこれと
     |---------------------|             あと1つはこのペアを選んだと考えることができる

すると、以下の手順で解ける。

ペアのスコアの和 $A_i+A_j$ を優先度付きキュー(最大値を取り出す)で管理する。
最初は $A_1+A_2,A_2+A_3,...$ が入っている。

あるペアがキューから取り出されたとき、その元となった位置 $i,j$ が片方でも既に使われていたら、スキップ。

そうで無い場合、そのペアは答えに加算できる。
そのペアを挟んでまだ選ばれていない一番近い2つの $A_i,A_j$ を見つけ、その和を新たにキューに放り込む。

これを繰り返し、貪欲に選んだ $R$ 個の総和が答えとなる。

「まだ選ばれていない一番近い $i,j$」は、std::setを使わない代替テクニックの「配列・特殊アイデア系①」で紹介しているような方法で管理できる。

もちろん、std::setのように「ある値の前後の値を検索」と「ある値の削除」ができるデータ構造があればそれを使えばよい。

Python3

programming_algorithm/contest_history/atcoder/2021/0911_abc218.txt · 最終更新: 2021/09/13 by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0