// return {{x,y},g} s.t. ax+by=g=gcd(a,b)>=0.
std::pair<std::pair<longlong, longlong>, longlong> ext_gcd(longlong a, longlong b) {
/** 計算中の行列を * x y * z w * としている */longlong x = 1, y = 0;
longlong z = 0, w = 1;
longlong tmp;
while (b) {
longlong p = a / b, q = a % b;
tmp = x - y * p; x = y; y = tmp;
tmp = z - w * p; z = w; w = tmp;
a = b; b = q;
}
// gcd(a,b)>=0 となるように補正を掛ける (任意)if (a >= 0) return {{x, z}, a};
elsereturn {{-x, -z}, -a};
}
H, W, X, Y = map(int, input().split())
X -= 1
Y -= 1
S = []
for _ inrange(H):
S.append(input())
ans = 1for j inrange(Y + 1, W):
if S[X][j] == '#':
break
ans += 1for j inreversed(range(Y)):
if S[X][j] == '#':
break
ans += 1for i inrange(X + 1, H):
if S[i][Y] == '#':
break
ans += 1for i inreversed(range(X)):
if S[i][Y] == '#':
break
ans += 1print(ans)
C - ORXOR
数列の各項の隙間 個に対して，それぞれ切る or 切らないの 全探索．区間列挙の際は両端に番兵を入れておくとよい．
N = int(input())
A = list(map(int, input().split()))
ans = 1 << 32for i inrange(1 << N - 1):
sep = [0] + [j + 1for j inrange(N - 1) if i >> j & 1] + [N]
K = len(sep) - 1
x = 0for l, r inzip(sep, sep[1:]):
v = 0for t in A[l:r]:
v |= t
x ^= v
ans = min(ans, x)
print(ans)
N = int(input())
p = [1]
for i inrange(10):
p.append(p[-1] * 10)
A = 0for i inrange(1, 1000001):
l = len(str(i))
x = i * p[l] + i
if x <= N:
A += 1print(A)
H, W, A, B = map(int, input().split())
N = H * W
D = {}
defdfs(s, a, b):
if s == (1 << N) - 1:
return1if (s, a, b) in D:
return D[(s, a, b)]
res = 0for i inrange(N):
if (s >> i) & 1 == 0:
if a:
r, c = divmod(i, W)
if c < W - 1and (s >> i + 1) & 1 == 0:
res += dfs(s | 1 << i | 1 << i + 1, a - 1, b)
if r < H - 1and (s >> i + W) & 1 == 0:
res += dfs(s | 1 << i | 1 << i + W, a - 1, b)
if b:
res += dfs(s | 1 << i, a, b - 1)
break
D[(s, a, b)] = res
return res
print(dfs(0, A, B))
N = int(input())
INF = 10 ** 18
D, U = -INF, +INF
L, R = -INF, +INF
for _ inrange(N):
a, t = map(int, input().split())
if t == 1:
D += a
U += a
elif t == 2:
d = max(0, a - D)
D += d
L += d
R = max(L, R)
U = max(U, D)
elif t == 3:
d = max(0, U - a)
U -= d
R -= d
L = min(L, R)
D = min(U, D)
input()
for x inmap(int, input().split()):
if x <= L:
print(D)
elif x >= R:
print(U)
else:
print(D + (x - L))
String s = sc.next();
String t = sc.next();
int n = s.length();
int m = t.length();
// 開始位置の mod 64 の値ごとに 64 bit 分割を行う．long[][] x = newlong[64][];
for (int i = 0; i < 64; i++) {
// 切り上げ除算int p = (n - i + 63) / 64;
long[] r = x[i] = newlong[p];
for (int j = 0; j < p; j++) {
// Long.parseLong を使用した場合，64 bit 目が 1 だと実行時エラーとなる．
r[j] = Long.parseUnsignedLong(s, i + (j << 6), Math.min(n, i + (j + 1 << 6)), 2);
}
}
// 切り上げ除算int p = (m + 63) / 64;
long[] y = newlong[p];
for (int j = 0; j < p; j++) {
y[j] = Long.parseUnsignedLong(t, j << 6, Math.min(m, j + 1 << 6), 2);
}
int ans = m;
// 開始位置を全探索for (int i = 0; i + m <= n; i++) {
int k = i >> 6;
int r = i & 63;
long[] a = x[r];
int sum = 0;
for (int j = 0; j < p - 1; j++) {
sum += Long.bitCount(a[k + j] ^ y[j]);
}
// 末項の帳尻合わせint l1 = k + p == a.length ? (n - i) & 63 : 64;
int l2 = l & 63;
// signed shift (>>) とした場合空いた部分は元の符号 bit によって埋められるため，unsigned shift (>>>) を用いる必要がある．long v1 = a[k + p - 1] >>> (l1 - l2);
long v2 = y[p - 1];
sum += Long.bitCount(v1 ^ v2);
ans = Math.min(ans, sum);
}
pw.println(ans);
N, M = map(int, input().split())
T = 3 * N
defmul_mod(*iterable):
res = 1for v in iterable:
res = res * v % M
return res
facT = mul_mod(*range(1, T + 1))
fac_inv = [0] * T + [pow(facT, M - 2, M)]
for i inrange(T, 0, -1):
fac_inv[i - 1] = fac_inv[i] * i % M
pow2_inv = [1] + [0] * N
inv_2 = pow(2, M - 2, M)
for i inrange(N):
pow2_inv[i + 1] = pow2_inv[i] * inv_2 % M
pow3_inv = [1] + [0] * N
inv_3 = pow(3, M - 2, M)
for i inrange(N):
pow3_inv[i + 1] = pow3_inv[i] * inv_3 % M
print(sum(sum(mul_mod(facT, fac_inv[T - 2 * y - 3 * z], fac_inv[y], fac_inv[z], pow2_inv[y], pow3_inv[z]) for z inrange(N + 1 - y)) for y inrange(N + 1)) % M)
from math import gcd
A, B = map(int, input().split())
W = B - A + 1
coprime = [[i < j and gcd(A + i, A + j) == 1for j inrange(W)] for i inrange(W)]
memo = {}
defdfs(s):
if s in memo:
return memo[s]
res = 1
bits = [i for i inrange(W) if s >> i & 1]
for i in bits:
t = 0for j in bits:
t |= coprime[i][j] << j
res += dfs(t)
memo[s] = res
return res
print(dfs((1 << W) - 1))
functools.lru_cache を使えばメモ用の dict を持たなくてもよい．
from functools import lru_cache
from math import gcd
A, B = map(int, input().split())
W = B - A + 1
coprime = [[i < j and gcd(A + i, A + j) == 1for j inrange(W)] for i inrange(W)]
@lru_cache(maxsize=1 << 32)
defdfs(s):
res = 1
bits = [i for i inrange(W) if s >> i & 1]
for i in bits:
t = 0for j in bits:
t |= coprime[i][j] << j
res += dfs(t)
return res
print(dfs((1 << W) - 1))
if (a + b >= 15 && b >= 8) {
pw.println(1);
} elseif (a + b >= 10 && b >= 3) {
pw.println(2);
} elseif (a + b >= 3) {
pw.println(3);
} else {
pw.println(4);
}
B - Job Assignment
が答え．式にするとややこしいけど，実装はシンプル．
が小さいので，すべての , の組を全探索しても間に合う．
この問題では求められていないが， なので，左右からの累積 を持って で求めることもできる．
long min = Long.MAX_VALUE;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
long v;
if (i == j) {
v = a[i] + b[i];
} else {
v = Math.max(a[i], b[j]);
}
min = Math.min(min, v);
}
}
pw.println(min);
