$a^b$ で表せるものを数えて、全体 $N$ から引く方針でいく。
範囲内の数で $a$ が取り得る最大値は、$b=2$ の時に $\sqrt{N}$ なので、$a$ を全探索するのは間に合う。
あとは、$a$ を固定したときに $b$ が最大いくつまで取り得るかを、$N$ を $a$ で何回割れるかで調べればよい。
ただし、$2^6=4^3$ のように、異なる $a,b$ で同じ整数が表せることがあるので、一度出た整数はsetなどで管理しておく。
$a^b$ で表せる数があんまり多いとTLEやMLEになるが、最大の $N$ で試して大丈夫なら大丈夫。
Python3
n = int(input())
ans = n
checked = set()
for k in range(2, 10 ** 5 + 1):
if k * k > n:
break
t = k * k
while t <= n:
if t in checked:
break
ans -= 1
checked.add(t)
t *= k
print(ans)
裏になっているカードの状態は $9 \times 9$ で81通りしかないので、それぞれについて調べればよい。
確率の計算に注意。
裏になっているカードが $i$ である確率は、表に見えている $i$ の枚数によって変わりうる。
たとえば、$K=3$ のときに「A: 1122#」「B: 1345#」であれば、Aの裏になっているカードは
カード1はもう残っていない
カード2はあと1枚
カード3～5はあと2枚ずつ
カード6～9はあと3枚ずつ
で全部で21枚あるので、裏のカードがそれぞれの数である確率は、例えばカード3なら $\frac{2}{21}$ となる。
さらにBの裏になっているカードは、Aのカードが何だったかでさらに1枚消費した状態で同様に数える。
10個中2個の当たりが入ったくじを引くとき、2個同時に引いても、1個ずつ順番に引いても、結果の確率は変わらない、みたいな文章題、よく見た記憶がある。
今回も、裏になっているカードの状態をA,B同時に決めても、順番に決めても、確率は変わらない。
として、点数計算してAが勝つ場合だけ、$p_i \times q_{i,j}$ を合計すれば答えとなる。
Python3
from collections import Counter
k = int(input())
s = input()
t = input()
count = Counter(s + t)
def score(s):
c = Counter(s)
res = 0
for i in range(1, 10):
res += i * 10 ** c[str(i)]
return res
ans = 0
for i in range(1, 10):
if count[str(i)] >= k:
continue
tak = score(s[:4] + str(i))
p = (k - count[str(i)]) / (9 * k - 8)
for j in range(1, 10):
if count[str(j)] + int(i == j) >= k:
continue
aok = score(t[:4] + str(j))
q = (k - count[str(j)] - int(i == j)) / (9 * k - 9)
if tak > aok:
ans += p * q
print(ans)
電車で寝て、起きたら既に終点を通り越して逆方向だった経験、誰しもあるよね！
問題設定が少々長いが、実体験でもあり得る問題なので飲み込みやすくて嬉しい。
（日常生活からそういう性質を持ったものを何個も見つけるのは難しいと思う）
制約をよく見ると「$Y$: 電車が停車している時間」「$Q$: 高橋君が起きている時間」が圧倒的に短い。
高橋君が下車できる条件をもっと限定的に表現すると、
「電車が $B$ に停車してから $i$ 秒後と、高橋君が起きてから $j$ 秒後の時刻が一致する」といえる。
$0 \le i \lt Y, 0 \le j \lt Q$ で $(i,j)$ を全探索して、さらにそれを $T$ ケースやっても十分間に合う。
それぞれを数式で表すと、$k,l$ を適当な非負整数としてそれぞれ以下のようになる。
$(2X+2Y)k+X+i$
$(P+Q)l + P+j$
modを使えば $k,l$ を省いて以下のように表せる。
中国剰余定理を使えば、これを満たす解が存在するか、存在するなら正の最小値はいくつかを求めることができる。
AtCoder Libraryにも crt として用意されている。
Python3
ライブラリ用意してなかったので以下のサイトを使わせていただいた。感謝。
def inv_gcd(a, b):
# 略
def crt(r, m):
# 略
t = int(input())
INF = 1 << 60
for _ in range(t):
x, y, p, q = map(int, input().split())
ans = INF
for i in range(y):
for j in range(q):
r, m = crt([x + i, p + j], [2 * x + 2 * y, p + q])
if r == 0 and m == 0:
continue
ans = min(ans, r)
if ans == INF:
print('infinity')
else:
print(ans)
よく考えると、$(i,j)$ を全探索しなくても、最適になり得るのは「駅に着いた瞬間」か「起きた瞬間」のいずれかに限られるのだから、
とすれば計算量がもっと減らせたね。
過去に類題見たことあると思いつきやすいかも知れない。
俗に燃やす埋める問題と呼ばれる、グラフの最小カット問題に帰結できる問題パターンがある。
$N$ 個のゴミを、それぞれ燃やすか埋めるか決める
ゴミ $i$ は燃やすとコスト $c_{i,1}$、埋めるとコスト $c_{i,2}$ が発生する
また「ゴミ $i$ を燃やし、$j$ を埋めると、追加コスト $d_{i,j}$ が発生する」という条件が何個かある
処遇を適切に決めて、総コストを最小化せよ
今回の場合、上の説明でゴミが「'?'マス」、燃やす埋めるが「白に塗る、黒に塗る」にあたるのだが、コストの最小化でなくて得点の最大化となる。
このような場合、負辺ができないようにあらかじめ下駄を履かせた上で正負逆転させる。
今回では「隣接するマスの個数分だけ既に得点をもらった後、同じ色のマスが隣りあった場合をコストとする」とよい。
各'?'マスの周囲の黒、白、'?'マスを数えておいて、以下のようなグラフを構築する。$s,t$ は仮想的な始点・終点とする。辺上の数字はその辺のコストとする。
白に塗る 黒に塗る
,- 1 -→ ?マス1 -- 1 --, 周囲に白が1個、黒が1個
| ↓
s - 2 -→ ?マス2 -- 0 → t 周囲に白が2個、黒が0個
| ↑
`- 1 -→ ?マス3 -- 2 --' 周囲に白が1個、黒が2個
さて、ここで'?'マス同士が隣り合った場合の追加コストを表現する辺を追加していきたいのだが、
燃やす埋める問題の制約として「同じ側の処遇を行った場合の追加コストは表現できない」というのがある（たぶん）。
つまり、本来は隣り合った'?'マス2個を「どちらも白」「どちらも黒」にした場合にコストが発生するのだが、これは“同じ処遇”なのでグラフで表現できない。
ここで、グリッドグラフは、2部グラフになることが利用できる。
どういうことかというと、左を「白に塗る」、右を「黒に塗る」と意味づけしたのはあくまで人間の理解のためで、アルゴリズム上は個別に左右反転しても問題ない。
,-白- 1 -→ ?マス1 -- 1 -黒-, 周囲に白が1個、黒が1個
| ↓
s 黒- 0 -→ ?マス2 -- 2 -白→ t 周囲に白が2個、黒が0個
| ↑
`-白- 1 -→ ?マス3 -- 2 -黒-' 周囲に白が1個、黒が2個
こうすると、例えば'?'マス1と2が隣り合っていたとしても、追加コストの辺をちゃんと表現できる。
,-白- 1 -→ ?マス1 -- 1 -黒-,
| ｜↑ ｜
| 1｜｜1 ｜
| ↓｜ ↓
s 黒- 0 -→ ?マス2 -- 2 -白→ t
| ↑
`-白- 0 -→ ?マス3 -- 2 -黒-'
そして、例えば市松模様の白いマスだけを左右反転する、というように決めると、
全ての「隣り合った'?'マス同士」は「左右反転してないのが1個と、したのが1個」となり、必ず追加コストの辺を張れるようになる。
こうやってグラフを構築して、最小カット問題（＝最大流問題）を解けば、答えが求まる。
入れ替わっただけのペアを重複して数えないように注意。
Python3
from collections import deque
class Dinic:
def __init__(self, n):
self.n = n
self.links = [[] for _ in range(n)]
self.depth = None
self.progress = None
def add_link(self, _from, to, cap):
self.links[_from].append([cap, to, len(self.links[to])])
self.links[to].append([0, _from, len(self.links[_from]) - 1])
def bfs(self, s):
depth = [-1] * self.n
depth[s] = 0
q = deque([s])
while q:
v = q.popleft()
for cap, to, rev in self.links[v]:
if cap > 0 and depth[to] < 0:
depth[to] = depth[v] + 1
q.append(to)
self.depth = depth
def dfs(self, v, t, flow):
if v == t:
return flow
links_v = self.links[v]
for i in range(self.progress[v], len(links_v)):
self.progress[v] = i
cap, to, rev = link = links_v[i]
if cap == 0 or self.depth[v] >= self.depth[to]:
continue
d = self.dfs(to, t, min(flow, cap))
if d == 0:
continue
link[0] -= d
self.links[to][rev][0] += d
return d
return 0
def max_flow(self, s, t):
flow = 0
while True:
self.bfs(s)
if self.depth[t] < 0:
return flow
self.progress = [0] * self.n
current_flow = self.dfs(s, t, float('inf'))
while current_flow > 0:
flow += current_flow
current_flow = self.dfs(s, t, float('inf'))
n = int(input())
field = [input() for _ in range(n)]
vertices = {} # {i,j: 頂点番号, 周囲の黒, 周囲の白個数, [周囲の'?'の(i,j)]}
fixed_zebra = 0
for i, row in enumerate(field):
for j, c in enumerate(row):
def register(ni, nj, b, w, ques):
if field[ni][nj] == 'B':
b += 1
elif field[ni][nj] == 'W':
w += 1
else:
ques.append((ni, nj))
return b, w
b, w = 0, 0
ques = []
if i > 0:
b, w = register(i - 1, j, b, w, ques)
if i < n - 1:
b, w = register(i + 1, j, b, w, ques)
if j > 0:
b, w = register(i, j - 1, b, w, ques)
if j < n - 1:
b, w = register(i, j + 1, b, w, ques)
if c == 'B':
fixed_zebra += w
elif c == 'W':
fixed_zebra += b
else:
v = len(vertices)
vertices[i, j] = [v, b, w, ques]
fixed_zebra //= 2
mf = Dinic(len(vertices) + 2)
s = len(vertices)
t = len(vertices) + 1
geta0 = 0
geta1 = 0
for (i, j), (v, b, w, ques) in vertices.items():
geta0 += b + w
geta1 += len(ques)
if (i + j) % 2 == 0:
mf.add_link(s, v, w)
mf.add_link(v, t, b)
else:
mf.add_link(s, v, b)
mf.add_link(v, t, w)
for ti, tj in ques:
u = vertices[ti, tj][0]
mf.add_link(v, u, 1)
f = mf.max_flow(s, t)
print(fixed_zebra + geta0 + geta1 // 2 - f)