AtCoder Beginner Contest 177 E,F問題メモ

AtCoder Beginner Contest 177

E - Coprime

• $N$ 個の正整数 $A_1,A_2,...,A_N$ が与えられる
• 以下を出力せよ
  • 全てのペアについて互いに素なら「pairwise coprime」
  • $N$ 個全体に1以外の共通の約数が無ければ（$GCD(A_1,A_2,...,A_N)=1$ なら）「setwise coprime」
  • そうでないなら「not coprime」
• $1 \le N \le 10^6$
• $1 \le A_i \le 10^6$

• いろいろな解き方がまとめられている
  • ABC177-E coprime 4つの解法 - 30歳で競プロに目覚めた霊長類のブログ

まず最初に、全てのgcdを取ることで「pairwise or setwise」か「not」かは判別できる。結果が1以外なら「not」確定。

pairwise と setwise の判別をどうするか。

まず、pairwise な状態では、どの2数の素因数も被っていない。
しかし、$N$ から $A_i=1$ であるものを除いた個数が、 $10^6$ 以下の素数の個数以上あったら、その時点でどれか2つには共通の素因数が含まれざるを得ない。

$10^6$ 以下の素数の個数は、検索すれば78498個とわかる。つまり、$A_i \ge 2$ の個数がこれより大きければ「setwise」と判定できる。
これにより、実質的に考慮すべき $N$ がぐっと小さくなった。

そしたら、後は $\sqrt{A_{max}} = 1000$ までの全ての素数で各 $A_i$ を試し割っていく。
「これまでの素数で割られた後の $A_i$ の値」を $B_i$ として、集合で持っておく。

もしどれか2つが共通の素因数を持つなら、$B_i$ にかぶりが発生する。

$B_i$ を素数 $p$ で割ったとき、

• 2つ以上の $B_i$ が $p$ で割り切れてしまったら setwise
• $p$ で割った後の新しい $B_i$ が1以外の時、他の $B_j$ と被ってしまったら setwise

上記のようなことがなく最後まで処理できたら pairwise となる。

重複の判定には、$B_i$ を set で管理して、別途「$B_i=1$ の個数」を数えて、合わせて要素数が $N$ になるかでチェックした。
だが、$10^6$ 程度ならその分の配列を用意して、存在する・しないフラグを使った方が楽だったね。

計算量は、$P(N)$ を「$N$ 以下の素数の個数」として、$O(\max(N,P(A_{max})) \times P(\sqrt{A_{max}}))$

F - I hate Shortest Path Problem

• $(H+1) \times W$ のグリッドを、右か下のみに移動する
• 始点は、1段目の好きな位置を選んで決める
• $i=1～H$ について、$i$ 段目 $A_i～B_i$ 列目のマスから下に移動することは出来ない（そこに移動してくることは出来る）
• $k=2～H+1$ について、$k$ 段目のいずれかのマスまで降りるために必要な最小移動回数を求めよ
  • 到達できない場合は-1を答えよ

  1234   A B  答
1 v___   2 4
2 __vv   1 2   1
3 v__v   2 3   4
4 vvv_   4 4   6
5 ....        -1

_: 降りれない
v: 降りれる

順序付き集合（std::setなど）による状態管理。

$k$ 段目までの下移動の回数は $k-1$ 回と決まっているので、同じ段では右移動の回数の最小値を考えればよい。
右移動の回数は「降り立つ列番号 - 始点の列番号」なので、なるべく右には移動せず、下に降りられる限りは下に降りるように移動するとする。

すると、壁に出会すたびに、降り立つ列番号は徐々にまとめられていく。

例えば、1段目の $A_1～B_1$ 列目に壁があったら、$A_1～B_1+1$ 列目を始点とした時の2段目に降り立つ位置は全て $B_1+1$ になる。
この時、考慮する始点は $B_1+1$ だけ残して、$A_1～B_1$ は最小値になり得ないので除いてしまってよい。

 1  2 ...   A1 ... B1 B1+1
↓ ↓    ↓ → →  → ↓
            ~~~~~~~~~

同様に、$i$ 列目で $(A_i,B_i)=(2,10)$ として、$2～11$ の中で降り立つ可能性のある列番号が $3,4,8,9$ だった場合、
9だけを11に更新しつつ残して、3,4,8に降り立つルートは、以降の段目では除いてしまってよい。

1  2  3  4  5  6  7  8  9 10 11
     ↓ ↓          ↓ ↓
     → → → → → → → → ↓
  ~~~~~~~~~~~~~~~~~~~~~~~~~~ ↓

1段目から順に「現在の段目まで降り立つ可能性のある列番号」を、順序付き集合で管理する。$desc$ とする。

  12345678   desc
1 v__vvvvv   { 1 2 3 4 5 6 7 8 }
2 vvvvvv__   { 1 4 5 6 7 8 }
3 _vvvvvvv   { 1 4 5 6 }
4 vvvvv__v   { 2 4 5 6 }
5 vv__vvvv   { 2 4 5 8 }
6 v____vvv   { 2 5 8 }
7 vvvvvv__   { 6 8 }
8 ........   { 6 }

ある段目まで考慮したときの $desc$ の各要素を $D_1,D_2,...$、またそれぞれに対応する、そこに降り立つために最も効率のよい始点を $S_1,S_2,...$ とする。 $S_i$ と $D_i$ は、段目が進む毎に更新されることはあるが、各時点では1対1対応する。

以下のデータを管理する。

• $rel$: $D_j→S_j$ 対応辞書
• $getmin$: 現在有効な $D_j-S_j$ の集合を管理し、最小値を取得、また不要になった値を削除できるデータ構造

2番目は、C++ならstd::multisetで実装できるし、機能が無い言語なら、よくある代替手段として遅延削除優先度付きキュー¹⁾を使うと可能になる。

• 遅延削除優先度付きキュー
  • 優先度キューと、現在の正しい状態を保持するデータ構造を用意（今回は各 $S_i$ に対応する $D_i-S_i$ の値など）
  • 優先度キューから最小値を取得するとき、現在の正しい状態と一致するまでpopして捨てる

$i$ 段目を考える時、以下の要領で更新する。

• $desc$ の中から、$A_i$ 以上 $B_i+1$ 以下の要素を抽出
• 抽出された最大の要素を $D_{max}$ とし、
  • $desc$ から抽出された要素を全て削除、$B_i+1$ を追加
  • $rel[B_i+1]←S_{max}$ に更新（$S_{max}$ は $D_{max}$ に対応する始点）
  • $getmin$ から、$D_j-S_j$ を全て削除、$B_i+1-S_{max}$ を追加
  • その時の $getmin$ における最小値に、縦移動の回数 $i$ 回を加えたものが、$i+1$ 段目の答え
• ただし $B_i=W$（右端まで追いやられて降りれない）場合、$desc$ や $getmin$ への追加は無し
• 途中で $getmin$ が無くなったら、以下は全て -1

計算量は、各段について「$desc$ に残る $A_i$ 以上 $B_i+1$ 以下のそれぞれに対して、削除したり更新したりの操作」を行う必要があるが、1段につき1列以外は削除され、1回削除した列は再び対象となることは無いので、全体を通して操作は最大でも $O(H+W)$ に抑えられる。1回の操作では順序付き集合から値を削除したり追加したりで、これは $O(\log{W})$ で可能である。

よって、$O((H+W)\log{W})$ となり、十分に間に合う。

この問題では、$desc$（$D_i$ の管理）と $getmin$（$D_i-S_i$ の管理）に2種類の順序付き集合のデータ構造を用いる。

Pythonでは、前者は Binary Indexed Tree (Fenwick Tree)、後者は heapq で代替できる。

• std::setを使わない代替テクニック

Fenwick Treeを用いた代替実装は、機能的にはおよそheapqの上位互換だが²⁾、indexの扱いなどで混乱しやすい。heapqは制約があるが比較的実装で迷いにくい。（個人の感想）

前者は、「$A_i$ 以上の最小の要素」～「$B_i+1$ 以下の最大の要素」を求める必要があるが、このように特定の値以上・以下を探すのはheapqではできない。
Fenwick Treeでは、要素がある場所に+1、無い場所は0として累積和を取ることで「$A_i$ 未満にいくつの要素があるか→$k$ とする」「累積和が $k+1$ となる最小の（つまり $k+1$ 番目の）要素は何か」を求めることで、「$A_i$ 以上の最小の要素」を取得できる。

対して $getmin$ は、参照は最小値さえできればよいので、値が有効かどうか別途管理しておけばheapqで代替できる。