目次
AtCoder Beginner Contest 170 D,E,F問題メモ
D - Not Divisible
問題
- $N$ 個の正整数 $A_1,A_2,...,A_N$ が与えられる
- この内、以下の条件を満たす $i$（$1 \le i \le N$）の個数を答えよ
- 条件
- $A_i$ 以外の他のどの要素でも $A_i$ を割り切ることができない
- $1 \le N \le 2 \times 10^5$
- $1 \le A_i \le 10^6$
解法
条件は、「$A_i$ は、他のどの要素の倍数でもない」と言い換えられる。
素因数分解でもするのかと思うが、$10^6$ を素因数分解するのに $\sqrt{10^6}$ までの素数、つまり168個で試し割る必要があって、 $10^5$ 個の要素それぞれでやってたらちょっと間に合わない。（そこから答えを求めるまでまだ段階があるし）
- [参考] ρ法を使えば間に合うらしい
素数というと、素数を求めるエラトステネスの篩を思いつく。これをちょっとアレンジすれば上手くいく。
$10^6$ までのindexを持つ配列 $can$ を作り、はじめ全てTrueで初期化する。これは、その要素が（暫定）他のどの要素の倍数でもないことを示す。
$A_i$ を小さい方からチェックすることにして、
- $can[A_i]$ がその時点でTrueなら
- 自分より小さい他のどの要素の倍数でも無い
- 自分より大きい要素の倍数では当然無い
- 従って、$A_i$ は条件を満たす（※注意点あり）
- $can$ の、自身の倍数 $2A_i,3A_i,...$ を全てFalseにする
- $can[A_i]$ がその時点でFalseなら
- $A_i$ は他の要素の倍数のため、条件を満たさない
- $can$ 上の自身の倍数も、$A_i$ をFalseにした要素によって既にFalseにされているので、何もする必要は無い
上記のようにすればよい。
ただし、今回は $A_i$ が同じ要素が複数ある。 同じ数同士は互いの倍数のため条件を満たさないが、上記の方法では条件を満たすと判定されてしまう。
このため、最初に $A_i$ の値ごとの個数を求めておき、2個以上存在するものについては、答えに計上しないという処理が必要となる。
計算量
まずソートに $O(N \log{N})$ かかる。
また、$N$ 個の要素が全て条件を満たすとき、それぞれについて自身の倍数 $2A_i,3A_i,...$ をFalseにしていく部分がボトルネックとなる。
これが最も多くなる場合、$\dfrac{A_{max}}{p_1}+\dfrac{A_{max}}{p_2}+\dfrac{A_{max}}{p_3}+...$ のように、 互いで互いを割り切れないような $p_1,p_2,...$ 分の1の足し算となる。
これは、自然数分の1の足し算 $\dfrac{1}{2}+\dfrac{1}{3}+\dfrac{1}{4}+...+\dfrac{1}{N}$ がおよそ $\log{N}$ となるらしいので、それ以下であることはわかる。
よって、$O(N \log{N} + A_{max} \log{N})$ となり、間に合う。
import sys
from collections import Counter
import numpy as np
n, *aaa = map(int, sys.stdin.buffer.read().split())
cnt = Counter(aaa)
duplicated = {x for x, c in cnt.items() if c > 1}
aaa.sort()
can = np.ones(aaa[-1] + 1, np.int8)
ans = 0
for a in aaa:
if can[a] == 0:
continue
if a not in duplicated:
ans += 1
can[a * 2::a] = 0
print(ans)
E - Smart Infants
問題
- $N$ 人の園児と、たくさんの幼稚園がある
- 園児 $i$ のAtCoderのレートは $A_i$ で、はじめ、幼稚園 $B_i$ に所属している
- ここで、「不平等度」を以下のように定義する
- 不平等度
- 幼稚園 $i$ に所属する園児のレートの最大値を $X_i$ とする
- 園児が1人以上いる幼稚園について $X_i$ を求め、その最小値を不平等度とする
- さて、これから園児の転園が $Q$ 回行われる
- $j$ 回目の転園では、園児 $C_j$ を幼稚園 $D_j$ に移動させる
- 各転園直後の不平等度を求めよ
- $1 \le N,Q \le 2 \times 10^5$
- $1 \le A_i \le 10^9$
- $1 \le B_i,D_i \le 2 \times 10^5$
解法
方針
1回の転園につき、最強園児が変わりうるのは転園元・転園先の2園のみ。
この2園さえ情報更新すれば、他の幼稚園の更新をしなくても正しい答えが保たれるような方法を使う。
実装
C++ には、要素の順序を保ったまま挿入・削除を行えるデータ構造multisetがあるため、それを使えば比較的素直に管理できる。
Python使いは、あ、まずい、と悟って C++ に切り替えるか、何らかの代替方法を考える必要がある。
この問題のように、ある集合の順序を保ちつつ、「常に（最小値、最大値など）一定の場所を参照したい」場合は、優先度付きキューで代用できる場合がある。
- 参考
基本的には解説pdfに準拠し、以下を持っておく。
- 園児 $i$ が所属する幼稚園番号…$belongings[i]$
- 幼稚園 $i$ に所属する幼児のレートの順序付き多重集合…$kindergartens[i]$
- それぞれの幼稚園の最強園児のレートの順序付き多重集合…$fairness$
$kindergartens[i]$ と $fairness$ の部分に、heapqをもちいる。
heapqとmultisetの主な違いは「heapqは中途半端な位置からの削除ができない」「multisetは任意の要素を削除できる」ことだが、これは遅延評価する。
つまり、heapq実装においては要素は削除せず放っておき、いざ最小値・最大値に来たとき、それが本当に今の状態と合致しているかをチェック、正しくなければその時に削除（pop）する。
従って、後からチェックするための必要な情報が何かを考えて、heapqに挿入する要素を作る必要がある。
$kindergartens[i]$ には、$(園児のレート, 園児番号)$ を挿入する。 （Pythonではheapqは最小値を取り出すものしか無いため、最大値を求めたい場合はレートを正負逆転させるが、ややこしいため説明上は省く）
$fairness$ には、$(最強園児のレート, 幼稚園番号)$ を挿入する。
転園クエリ $(C,D)$ が来たら、
- 園児の情報を取得
- 転園前の幼稚園 $b=belongings[C]$
- 園児 $C$ のレート $a$
- 園児 $C$ の所属を更新 $belongings[C]=D$
- 転園先の情報を更新
- $kindergartens[D]$ に、$(a, C)$ を挿入
- もしその結果 $kindergartens[D]$ の最大値が $(a, C)$ になれば、$(a, D)$ を $fairness$ に挿入
- 転園元の情報を更新
- $kindergarten[b]$ の最大値 $(レート, 園児番号 i)$ を取得
- 園児 $i$ の所属先が $b$ でない場合、不整合なのでpop
- 以上を、最強園児の所属先が正しくなるまで繰り返す
- 正しくならないまま $kindergartens[b]$ が空になったら、その幼稚園は0人になっているため削除
del kindergartens[b]
- 1つ以上popした後に空にならなかったら、$(新しい最強園児のレート, b)$ を $fairness$ に挿入
- 答えを求める
- $fairness$ の最小値 $(レート p, 幼稚園番号 q)$ を取得
- $kindergartens[q]$ が存在するか？ その最大レートが $p$ か？を確認
- 存在しなかったり、$p$ でない場合、古い情報なのでpop
- 幼稚園とレートとの関係が正しくなるまで繰り返す
- 正しくなったら、その時の $p$ が答え
$kindergartens$ と $fairness$ の最大値・最小値を取得するところで、整合チェックを行っている。
本番中、$kindergartens$ から削除した後、新しい最強園児を $fairness$ に挿入する処理を忘れて、うんうん唸っていた。 まぁうっかりではあるんだが、heapqでは多少実装がややこしくなるのは否めない。
import sys
from collections import defaultdict
from heapq import heappop, heappush, heapify, heapreplace
n, q, *abcd = map(int, sys.stdin.buffer.read().split())
kindergartens = defaultdict(list)
infant_smartness = []
infant_belongings = []
for i, (a, b) in enumerate(zip(abcd[0:2 * n:2], abcd[1:2 * n:2])):
kindergartens[b].append((-a, i))
infant_smartness.append(a)
infant_belongings.append(b)
fairness = []
for b, ls in kindergartens.items():
heapify(ls)
a, i = ls[0]
fairness.append((-a, b))
heapify(fairness)
buf = []
for c, d in zip(abcd[2 * n::2], abcd[2 * n + 1::2]):
c -= 1
a = infant_smartness[c]
b = infant_belongings[c]
infant_key = (-a, c)
infant_belongings[c] = d
heappush(kindergartens[d], infant_key)
if kindergartens[d][0] == infant_key:
heappush(fairness, (a, d))
kgb = kindergartens[b]
is_changed = False
while kgb:
if infant_belongings[kgb[0][1]] == b:
break
heappop(kgb)
is_changed = True
else:
del kindergartens[b]
if kgb and is_changed:
heappush(fairness, (-kgb[0][0], b))
while True:
aa, bb = fairness[0]
if bb not in kindergartens:
heappop(fairness)
continue
ta = -kindergartens[bb][0][0]
if ta != aa:
heapreplace(fairness, (ta, bb))
continue
buf.append(aa)
break
print('\n'.join(map(str, buf)))
F - Pond Skater
問題
- アメンボが $H \times W$ のグリッドを $(x_1,y_1)$ から $(x_2,y_2)$ まで移動する
- 上から $i$ 行目、左から $j$ 列目を $(i,j)$ で表す
- グリッドの情報は文字列で与えられ、'.' なら通行可能、'@' なら不可能
- アメンボは、1回の移動で上下左右のいずれかに、1マス以上 $K$ マス以下進める
- 途中で '@' があるとそれ以上は進めない
- 最小の移動回数を求めよ
- $1 \le H \times W \le 10^6$
- $1 \le K \le 10^6$
- $(x_1,y_1)$ と $(x_2,y_2)$ は '.'
解法
一見、素直な経路探索に見えるが、一癖ある。
解説pdfまたは解説放送で、スマートな方法が紹介されている。以下は、自分の採った方法。
訪れた全てのマスから毎回、上下左右に $K$ マスの移動を調べていると、$H,W,K$ が大きく空白の多いグリッドだとTLEとなる。 （だいたい $O(HWK)$ のマスを調べることになる）
なので、$K$ マスの移動途中で既に訪れたマスがあったらそこで打ち切るなどして、無駄な計算を省きたい。
一般的な幅優先探索では、各マスへ到達できる暫定最短距離を保持しておいて、更新できる場合のみ次の探索候補としてキューに入れる、という方法を採る。
ここまでコスト4で到達可能 ↓ ４④６ ←┬既に判明している暫定最短距離 ∞ ←┘ ４: 他の経路でコスト4で到達可能。④を経由すると5かかるので、他の経路の方がよい ６: 他の経路でコスト6で到達可能だが、更新できるので更新し、キューに追加 ∞: まだ訪れたことがないマス。更新できるので更新し、キューに追加
今回、$K$ マスの移動の打ち切り判定にこれを使うと、困った事態が発生する。
方向性の違い問題
Ｓ──┐
｜ ｜←(1)
└──┼──Ｇ
｜↑(2)
(1)と(2)は、どちらもコスト2で行ける移動を示す。
もし(1)の移動が先に処理され、(2)の移動で「暫定最小コストが更新できなければそこで打ち切る」としていた場合、 交点のマスは既に(1)によってコスト2が入っているため、更新できず、そこで止まってしまう。
Ｓ１１１ ※数字は暫定最小コスト
１ ２
１２２２ Ｇ
２
そのため、訪れたマスには「どの方向を向いて訪れたか」が必要となる。縦移動で訪問済みでも、横移動で未訪問なら打ち切ってはいけない。
ただし、区別するのは縦横のみでよい。 左と右・上と下は、どちらか一方で訪れていたら、逆方向の移動でそれより先のマスに、更新可能なマスがあることはない。
ここまで右移動でコスト2で行けることが確定済み
↓
２２２２
→→→→
２２２２
→→→→←←○
２２１
左移動で訪れても、それより先はコスト2以下で行ける
君はもっと飛べるさ問題
キューに (コスト, 座標) みたいなデータを入れて小さい方から取り出すと、都合上、同じコストに関しては座標が小さいものが先に取り出される。
K=3 ... ↓↓ ＡＢ□□□□□Ｇ
A,Bに、下移動によってどちらもコスト2でたどり着けるとする。キューからはAが先に取り出される。
Aから次の移動先を求める際、近い方から次の移動コストである3を埋めていくとする。 （Bは横移動に対しては未訪問のため、Aからの探索は打ち切られない）
Ａ３３３□□□Ｇ
その次にBが取り出されたとき、既に右移動の1歩目でコスト3が埋まっているため、そこで打ち切られる。
ＡＢ３３□□□Ｇ
~~
このまま探索を続けると、Gにたどり着くのは5かかる。 だが、実際はBまで行った後、3回ずつ移動するのが最適である。
Ａ３３３４４４５ × Ｂ３３３４４４ ○
これは、キューからは小さい座標の頂点が取り出されるという性質上、座標を大きくする移動（下・右）の時に発生する。 方向による頂点の分離では区別できない。
かといって、打ち切らなければ、最初に言及したとおりTLEとなる。
「近い方からではなく、移動できる中で遠い方から順に更新できるか調べる」とすることで、回避できる。
こんなケースで発生しうる。（正答は5）
5 9 3 1 1 5 9 .@@@@@@@@ ...@@@@@@ ...@@@@@@ @..@@@@@@ @........
計算量
最初に $O(HW)$ 使って「各マスから上下左右、どこまで移動できるか」を作る。
コストは1回の探索で1しか増えないため、あるマスが更新されてキューに積まれる回数は、たかだか縦横の2回に抑えられる（はず？）
よって、探索も $O(HW)$（幅優先探索）または $O(HW \log(HW))$（Dijkstra）となる。
……の割には実行時間かかったので、計算量の見積もりは何か間違っているかも知れない。
from collections import deque
def reachable(field, h2, w2, k):
# 各マスから上下左右にどこまで行けるか
hw = h2 * w2
up, dw, lf, rg = [-1] * hw, [-1] * hw, [-1] * hw, [-1] * hw
lf_tmp = -1
for i in range(w2, hw - w2):
if field[i] == '.':
if lf_tmp == -1:
lf_tmp = i
lf[i] = max(lf_tmp, i - k)
else:
lf_tmp = -1
rg_tmp = -1
for i in range(hw - w2, w2 - 1, -1):
if field[i] == '.':
if rg_tmp == -1:
rg_tmp = i
rg[i] = min(rg_tmp, i + k)
else:
rg_tmp = -1
wk = w2 * k
for j in range(1, w2):
up_tmp = -1
for i in range(j, hw, w2):
if field[i] == '.':
if up_tmp == -1:
up_tmp = i
up[i] = max(up_tmp, i - wk)
else:
up_tmp = -1
dw_tmp = 0
for i in range(hw - w2 + j, w2 - 1, -w2):
if field[i] == '.':
if dw_tmp == -1:
dw_tmp = i
dw[i] = min(dw_tmp, i + wk)
else:
dw_tmp = -1
return up, dw, lf, rg
def solve(h2, w2, k, field, x1, y1, x2, y2):
s = x1 * w2 + y1
t = x2 * w2 + y2
up, dw, lf, rg = reachable(field, h2, w2, k)
INF = 10 ** 18
ans = [[INF, INF] for _ in field]
ans[s][0] = ans[s][1] = 0
q = deque([(0, s)])
while q:
cost, v = q.popleft()
if v == t:
return cost
nc = cost + 1
for u in range(up[v], v, w2):
if ans[u][0] <= nc:
break
ans[u][0] = nc
q.append((nc, u))
for u in range(dw[v], v, -w2):
if ans[u][0] <= nc:
break
ans[u][0] = nc
q.append((nc, u))
for u in range(lf[v], v, 1):
if ans[u][1] <= nc:
break
ans[u][1] = nc
q.append((nc, u))
for u in range(rg[v], v, -1):
if ans[u][1] <= nc:
break
ans[u][1] = nc
q.append((nc, u))
return -1
h, w, k = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())
h2 = h + 2
w2 = w + 2
field_tmp = [input() for _ in range(h)]
field = ['@' * w2]
for row in field_tmp:
field.append('@' + row + '@')
field.append('@' * w2)
field = ''.join(field)
print(solve(h2, w2, k, field, x1, y1, x2, y2))
解法2
解説pdfや解説放送にあった解法を参考にした実装。
- Dijkstraで探索する
- グラフの頂点を、(マス, そのマスに到達した方向) とする
- キューに持たせる情報を、(コスト, マス, 方向) とする
- コストは、移動回数を $K$ 倍して表現する
- 遷移
- 前回と同じ方向に1マス進む:
- コストは1増える
- 前回と違う方向に1マス進む:
- コストを $K$ の倍数に切り上げた上で、1増える
基本的に、同じマスを同じ方向で訪れるなら、移動回数が少ない方がいいのは当然として、できるだけ残り直進回数も多い方が嬉しい。
それを、今何マス移動したかを1ずつコストに計上してやることで、1回の移動開始からの直進回数が少ない（残り直進回数が多い）移動状態が優先的にキューから取り出される。
この方法は上手いなぁ。
from heapq import heappop, heappush
def solve(field, s, t, k):
INF = 10 ** 18
ans = [[INF, INF] for _ in field]
ans[s][0] = ans[s][1] = 0
MOVE = [(-w2, 0), (-1, 1), (1, 1), (w2, 0)]
q = [(0, s, 0)]
while q:
cost, v, direction = heappop(q)
if v == t:
return (cost - 1) // k + 1
ceiling = ((cost - 1) // k + 1) * k + 1
for di, ax in MOVE:
u = v + di
if field[u] == '@':
continue
nc = cost + 1 if di == direction else ceiling
if ans[u][ax] <= nc:
continue
ans[u][ax] = nc
heappush(q, (nc, u, di))
return -1
h, w, k = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())
h2 = h + 2
w2 = w + 2
field_tmp = [input() for _ in range(h)]
field = ['@' * w2]
for row in field_tmp:
field.append('@')
field.append(row)
field.append('@')
field.append('@' * w2)
field = ''.join(field)
s = x1 * w2 + y1
t = x2 * w2 + y2
print(solve(field, s, t, k))
