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

目次

パナソニックプログラミングコンテスト2021(AtCoder Beginner Contest 231) F,H問題メモ

パナソニックプログラミングコンテスト2021(AtCoder Beginner Contest 231)

GとH、解法に使う技術はそれなりにわかりやすくても、応用のさせ方がなかなか高度。
(逆に言うと知識の有無が出やすかった?)

F - Jealous Two

F - Jealous Two

問題

解法

問題文が少しややこしいが、太郎に i、次郎に j を渡すとして、 喧嘩が発生しないのは以下の条件に言い換えられる。

(Ai,Bi) を二次元座標と捉えると、条件を満たす位置関係が把握しやすくなる(気がする)。

サンプル1

3 |      x
2 |          x
1 |  x
0 +------------
    50  100 150

ある点を太郎に渡す i と固定した場合、そこより↖にある点が、j として条件を満たす。

3 |      x   |
2 | _________x     (150, 2) を i とすると
1 |  x             j はラインより↖の範囲にある点。
0 +------------    (ただし境界を含む)
    50  100 150

これは、点全体を Ai 基準でソートするとよい。

Ai の小さい方からFenwick Treeなどのデータ構造に登録していくと、 「今まで登録した中でBi 以上の点の個数」を数えればよいことになり、 これは O(logN) で高速に求められる。

Ai が同じ点については、境界も含まれるので 今回は Bi の大きい方から先にデータ構造に登録されていなければならない。
最初のソート順に気をつける。

また、Ai,Bi とも全く同じ点が k 個あったとしたら、 それらはどう渡してもよいので、k2 個の渡し方が存在する。

Ai,Bi の一方でも異なれば、条件を満たしつつ i,j を交換することはできないが、 全く同じであれば交換も可能なので、そこを数え忘れないようにする。

Python3

H - Minimum Coloring

H - Minimum Coloring

問題

解法

最小流量制約付き最小費用流。

各行各列にちょうど1個の場合

今回の問題設定を少し簡単にすると、典型っぽい問題となる。

行と列の数が同じで、全ての行・列に「ちょうど」1個の黒い駒がある状態にするのは、 過去に類題があったと思うが、単純な最小費用流で解ける。

まず、行を表す H 個の頂点、列を表す W 個の頂点、超頂点 S,T を用意する。

以上の辺を張ったら、ST に流量 H を流す最小コストを求めれば答え。

今回の問題

1つの行・列に何個でも置いてよい(その方がコストが安いなら)。

上記の辺の張り方で、ST の容量上限が 1 ではなくなる。
また、最終的に ST にいくら流せば良いか(駒を何個置くのが最適か)もわからない。

それでもまぁ、容量上限は INF とするとして、 流量もまぁ多くとも H+W 流せば十分で残りを流すためのバイパスを作るとして、 以下のような最小費用流グラフ(仮)が作れる。

             行    列
               ,_--③ -,               S→行: 容量INF,コスト0
         _,- ①         \             行→列: 容量1  ,コストCi
H+W → ⓢ      `---④ ---ⓣ → H+W    列→T : 容量INF,コスト0
       |`--- ②----'    /|
       |       `---⑤ -' |
       `-----------------'          ←バイパス(容量INF,コスト0)

ただしこのままだと、当然コスト 0 のバイパスに全部流れてしまう。

S」「T」の各辺には、それぞれに少なくとも 1 の流量を流さなければならない。

これを実現するのが「最小流量制約付き最小費用流」で、 少しグラフの作り方を変えると、単純な最小費用流に変換できる。

まず、前提として

というように考え方を拡張する。
この考えのもとでは、上記のグラフは dS=H+W,dT=(H+W)、他は dv=0 と表現できる。

この上で、流したい辺にはあらかじめ流したように dv を変更する。
つまり、

最後に、超超頂点1)P,Q として、

とし、PQ に、P から出ている辺の容量合計だけ流してやれば、答えとなる。

Python3

1)
語感が前前前世みたい