N = int(input())
A = list(map(int, input().split()))
cnt = [0] * 200for v in A:
cnt[v % 200] += 1
ans = 0for c in cnt:
ans += c * (c - 1) // 2print(ans)
N, K = map(int, input().split())
f1 = [0] * (3 * N + 1)
f1[0] = 1
f1[N] = -1for i inrange(3 * N):
f1[i + 1] += f1[i]
f2 = f1[:]
for i inrange(3 * N):
f2[i + 1] += f2[i]
for i inrange(3 * N, N - 1, -1):
f2[i] -= f2[i - N]
f3 = f2[:]
for i inrange(3 * N):
f3[i + 1] += f3[i]
for i inrange(3 * N, N - 1, -1):
f3[i] -= f3[i - N]
for x inrange(3 * N - 2):
if K > f3[x]:
K -= f3[x]
continuefor i inrange(min(N, x + 1)):
if K > f2[x - i]:
K -= f2[x - i]
continuefor j inrange(min(N, x - i + 1)):
if K > f1[x - i - j]:
K -= f1[x - i - j]
continue
k = x - i - j
print(i + 1, j + 1, k + 1)
exit(0)
P = 10 ** 9 + 7defsolve(S: str, k: int):
if S == '?'and k == 1:
return0
ans = 0for prv, cur inzip(S[-1] + S, S):
if prv == '?'or cur == '?':
ans += 1elif prv != cur:
ans += 2return ans * k * pow(2, k * S.count('?') - 2, P) % P
if __name__ == '__main__':
S = input()
k = int(input())
print(solve(S, k))
N, D, H = map(int, input().split())
p = []
for _ inrange(N):
d, h = map(int, input().split())
p.append((d, h))
p.sort()
l = 0
r = H
for _ inrange(50):
X = (l + r) / 2
ok = Truefor d, h in p:
ok &= h <= (H - X) * d / D + X
if ok:
r = t
else:
l = t
print(f'{r:.10f}')
// ライブラリなどは省略publicstaticvoid solve(ExtendedScanner sc, FastPrintStream pw) {
int n = sc.nextInt();
int m = sc.nextInt();
Digraph<SimpleEdge> g = new Digraph<>(2 * n * m);
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m - 1; ++j) {
int a = sc.nextInt();
g.addEdge(new SimpleEdge(i * m + j, i * m + j + 1, a));
g.addEdge(new SimpleEdge(i * m + j + 1, i * m + j, a));
}
}
for (int i = 0; i < n - 1; ++i) {
for (int j = 0; j < m; ++j) {
int b = sc.nextInt();
g.addEdge(new SimpleEdge(i * m + j, (i + 1) * m + j, b));
g.addEdge(new SimpleEdge(n * m + (i + 1) * m + j, n * m + i * m + j, 1));
}
}
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
g.addEdge(new SimpleEdge(i * m + j, n * m + i * m + j, 1));
g.addEdge(new SimpleEdge(n * m + i * m + j, i * m + j, 0));
}
}
Dijkstra<SimpleEdge> dij = new Dijkstra<>(g, 0);
pw.println(dij.distance(n * m - 1));
}
publicstaticvoid solve(ExtendedScanner sc, FastPrintStream pw) {
int n = sc.nextInt();
int m = sc.nextInt();
boolean[] ok = newboolean[n];
Arrays.fill(ok, true);
for (int i = 0; i < m; ++i) {
int a = sc.nextInt();
ok[a] = false;
}
IntArrayList bases = new IntArrayList();
IntArrayList xs = new IntArrayList();
for (int i = 0; i < n; ++i) {
if (!ok[i]) continue;
int e = i;
PrimitiveIterator.OfInt iter = bases.iterator();
while (iter.hasNext()) e = Math.min(e, e ^ iter.nextInt());
if (e != 0) {
bases.add(e);
xs.add(i);
}
}
if (bases.size() != Integer.numberOfTrailingZeros(n)) {
pw.println(-1);
return;
}
boolean[] vis = newboolean[n];
IntDeque dq = new IntDeque(n);
vis[0] = true;
dq.addLast(0);
while (dq.size() > 0) {
int u = dq.removeFirst();
for (var iter = xs.iterator(); iter.hasNext();) {
int x = iter.nextInt();
int v = u ^ x;
if (!vis[v]) {
vis[v] = true;
dq.addLast(v);
pw.print(u).print(' ').println(v);
}
}
}
}
N, M = map(int, input().split())
A = []
for i inrange(N):
K, *X = map(int, input().split())
A.append(set(X))
P, Q = map(int, input().split())
B = set(map(int, input().split()))
print(sum(Q <= len(B & X) for X in A))
Python では &演算子で set 同士の intersection を取ることが出来て楽に書ける．
N, L, T, X = map(int, input().split())
C = 0
ans = 0for i inrange(N):
A, B = map(int, input().split())
if B < L:
C = 0
ans += A
elif C + A < T:
ans += A
C += A
elif C + A == T:
ans += A + X
C = 0else:
ans += T - C + X + A
C = A
if C > T:
print('forever')
exit(0)
elif C == T:
ans += X
C = 0print(ans)
int n = sc.nextInt();
int m = sc.nextInt();
int q = sc.nextInt();
// 無向グラフ
Graph<SimpleEdge> g = new Graph<>(n);
for (int i = 0; i < m; ++i) {
int u = sc.nextInt() - 1;
int v = sc.nextInt() - 1;
int w = sc.nextInt();
g.addEdge(new SimpleEdge(u, v, w));
}
// Union Find 木
DisjointSetUnion dsu = new DisjointSetUnion(n);
PriorityQueue<SimpleEdge> pq = new PriorityQueue<>();
for (var e : g.getEdges(0)) pq.add(e);
// i 日目に追加する辺を一時的に保存するための List
ArrayList<SimpleEdge> l = new ArrayList<>();
for (int i = 0; i < q; ++i) {
int x = sc.nextInt();
while (pq.size() > 0) {
var e = pq.peek();
if (e.cost > x) break;
pq.poll();
int u = e.from;
int v = e.to;
if (dsu.same(0, v)) {
int tmp = u; u = v; v = tmp;
}
if (dsu.same(0, v)) continue;
dsu.merge(0, v);
l.addAll(g.getEdges(v)); // ここで pq に追加すると 1 日に 2 歩歩くことを許してしまうので注意
}
pw.println(dsu.size(0));
pq.addAll(l);
l.clear();
}
int n = sc.nextInt();
int m = sc.nextInt();
int k = sc.nextInt();
long q = sc.nextInt();
LongPrioritySum ps = new LongPrioritySum(m, false);
IntArrayList t = new IntArrayList();
for (int i = 0; i < n; ++i) {
int p = sc.nextInt();
if (sc.nextInt() == 0) {
ps.add(p);
} else {
t.add(p);
}
}
t.sort();
int cnt = ps.size();
long ans = cnt >= m ? ps.sum() : Long.MAX_VALUE;
int max = (n + k - 1) / k;
for (int x = 1; x <= max; ++x) {
int l = k * (x - 1);
int r = Math.min(l + k, t.size());
for (int j = l; j < r; ++j) {
ps.add(t.get(j));
}
if (ps.size() >= m) {
ans = Math.min(ans, q * x + ps.sum());
}
}
pw.println(ans);
N, C = map(int, input().split())
ans = sx = 0
xs = []
for _ inrange(N):
x, y = map(int, input().split())
sx += x
ans += (y - C) ** 2
xs.append(x)
mx = sx / N
for x in xs:
ans += (x - mx) ** 2print(ans)
int n = sc.nextInt();
int[] a = sc.ints(n);
int q = sc.nextInt();
int[] vals = Arrays.copyOf(a, n + q);
IntPair3[] qs = new IntPair3[q];
for (int i = 0; i < q; ++i) {
int l = sc.nextInt() - 1;
int r = sc.nextInt();
int v = sc.nextInt();
qs[i] = new IntPair3(l, r, v);
vals[n + i] = v;
}
IntCompress cmp = new IntCompress(vals, false);
for (int i = 0; i < n; ++i) {
a[i] = cmp.compress(a[i]);
}
for (int i = 0; i < q; ++i) {
qs[i].trd = cmp.compress(qs[i].trd);
}
int m = cmp.compressedSize();
long[] num = newlong[m];
IntDualSegmentTree seg = new IntDualSegmentTree(
a, (f, x) -> f, (f, g) -> f, -1
);
IntRangeSet[] rs = new IntRangeSet[m];
for (int i = 0; i < m; ++i) rs[i] = new IntRangeSet();
for (int i = 0; i < n; ++i) {
rs[a[i]].add(i);
++num[a[i]];
}
long ans = 0;
for (long c : num) {
ans += c * (c - 1) / 2;
}
for (var query : qs) {
int l = query.fst, r = query.snd;
int v = query.trd;
int cur = l;
while (cur < r) {
int u = seg.get(cur);
int nxt = rs[u].getInclusingRange(cur).getRight();
long rem;
if (nxt < r) {
rem = rs[u].removeAll(cur, nxt);
cur = nxt + 1;
} else {
rem = rs[u].removeAll(cur, r - 1);
cur = r;
}
long x = num[u], y = num[u] - rem;
ans -= x * (x - 1) / 2 - y * (y - 1) / 2;
num[u] -= rem;
}
long add = rs[v].addAll(l, r - 1);
long x = num[v] + add;
long y = num[v];
ans += x * (x - 1) / 2 - y * (y - 1) / 2;
num[v] = x;
seg.apply(l, r, v);
pw.println(ans);
}
int n = sc.nextInt();
int m = sc.nextInt();
DisjointSetUnion dsu = new DisjointSetUnion(n);
int k = m - (n - 1);
IntPair[] edges = new IntPair[k];
TreeBuilder tb = new TreeBuilder(n);
for (int i = 0, j = 0; i < m; ++i) {
int u = sc.nextInt() - 1;
int v = sc.nextInt() - 1;
if (dsu.same(u, v)) {
edges[j++] = new IntPair(u, v);
} else {
dsu.merge(u, v);
tb.addEdge(u, v);
}
}
TreeSet<Integer> need = new TreeSet<>();
int[] ids = newint[n];
Tree t = tb.build();
EulerTourLCA lca = new EulerTourLCA(t);
int q = sc.nextInt();
while (q --> 0) {
int u = sc.nextInt() - 1;
int v = sc.nextInt() - 1;
need.add(u);
need.add(v);
for (var e : edges) {
need.add(e.fst);
need.add(e.snd);
}
int c = need.size();
int[] vs = newint[c];
for (int i = 0; i < c; ++i) {
vs[i] = need.pollFirst();
ids[vs[i]] = i;
}
long[][] g = newlong[c][c];
for (long[] r : g) Arrays.fill(r, Dijkstra2.UNREACHABLE);
for (int i = 0; i < c; ++i) {
g[i][i] = 0;
for (int j = i + 1; j < c; ++j) {
int x = vs[i], y = vs[j];
g[i][j] = g[j][i] = lca.dist(x, y);
}
}
for (var e : edges) {
int x = e.fst, y = e.snd;
int i = ids[x], j = ids[y];
g[i][j] = g[j][i] = 1;
}
long ans = new Dijkstra2(g, ids[u]).getDistance(ids[v]);
pw.println(ans);
}
A, B, C = map(int, input().split())
print("YNeos"[A ** 2 + B ** 2 >= C ** 2::2])
B - Intersection
つまりは を満たす を数える問題． のケースに注意．
N = int(input())
L = max(map(int, input().split()))
R = min(map(int, input().split()))
print(max(0, R - L + 1))
C - IPFL
type 2 のクエリで実際に swap する代わりに，swap されているかどうかのフラグを持つ．もし swap されていれば，添え字 (0-indexed) は次のように読み替えられる．
のとき:
のとき:
この変換法則を用いて type 1 のクエリを処理する．フラグが true の場合，最後の出力時に swap し忘れると間違えるので注意．
下に示すコードでは rev が swap のフラグとなっている．
N = int(input())
S = [c for c ininput()]
Q = int(input())
rev = Falsefor _ inrange(Q):
t, a, b = map(int, input().split())
a -= 1
b -= 1if t == 1:
if rev:
if a < N:
a += N
else:
a -= N
if b < N:
b += N
else:
b -= N
S[a], S[b] = S[b], S[a]
else:
rev = not rev
if rev:
S[:N], S[N:] = S[N:], S[:N]
print(''.join(S))
以下は Java による AC コード．DisjointSetUnion クラスや Graph などの実装は省略している．
publicstaticvoid solve(ExtendedScanner sc, FastPrintStream pw) {
int n = sc.nextInt();
int m = sc.nextInt();
int[] us = newint[m];
int[] vs = newint[m];
DisjointSetUnion dsu = new DisjointSetUnion(n);
for (int i = 0; i < m; ++i) {
us[i] = sc.nextInt() - 1;
vs[i] = sc.nextInt() - 1;
dsu.merge(us[i], vs[i]);
}
int[][] groups = dsu.groups(); // 連結成分を取得long ans = 1;
for (int[] group : groups) {
boolean[] con = newboolean[n]; // 連結成分に属するかどうかint k = group.length;
Graph<SimpleEdge> g = new Graph<>(k);
for (int id = 0; id < k; ++id) {
con[group[id]] = true;
}
for (int i = 0; i < m; ++i) {
int u = us[i];
int v = vs[i];
if (con[u] && con[v]) {
int ui = ids[u];
int vi = ids[v];
g.addEdge(new SimpleEdge(ui, vi));
}
}
ans *= solve(g);
}
pw.println(ans);
}
staticlong solve(Graph<SimpleEdge> g) {
int n = g.getV();
IntArrayList pre = new IntArrayList(); // BFS で訪問した順番int[] par = newint[n]; // 全域木における親
Arrays.fill(par, -1);
boolean[] vis = newboolean[n];
vis[0] = true;
IntDeque dq = new IntDeque(n);
dq.addLast(0);
while (dq.size() > 0) {
int u = dq.removeLast();
pre.add(u);
for (var e : g.getEdges(u)) {
int v = e.to;
if (!vis[v]) {
vis[v] = true;
par[v] = u;
dq.addLast(v);
}
}
}
int[] color = newint[n];
long ans = 0;
Out:for (int i = 0; i < 1 << n - 1; ++i) {
Arrays.fill(color, 1, n, -1);
for (int j = 1; j < n; ++j) { // 色を BFS の訪問順に決定していく．int v = pre.get(j);
color[v] = (color[par[v]] + 1 + ((i >> (v - 1)) & 1)) % 3;
}
for (int u = 0; u < n; ++u) {
for (var e : g.getEdges(u)) {
int v = e.to;
if (color[u] == color[v]) {
continueOut;
}
}
}
++ans;
}
return ans * 3;
}
publicstaticvoid solve(ExtendedScanner sc, FastPrintStream pw) {
int n = sc.nextInt();
int m = sc.nextInt();
int[] xs = newint[m];
int[] ys = newint[m];
int[] zs = newint[m];
for (int i = 0; i < m; ++i) {
xs[i] = sc.nextInt();
ys[i] = sc.nextInt();
zs[i] = sc.nextInt();
}
int[][] bits = BitUtil .bits(n); // bits[i] := i の 2 進数表記において立っている bit の位置を記録した配列long[] dp = newlong[1 << n];
dp[0] = 1;
for (int s = 1; s < 1 << n; ++s) {
int[] cnt = newint[n + 1]; // cnt[i] = i 未満の要素の個数for (int x : bits[s]) {
++cnt[x + 1];
}
for (int i = 0; i < n; ++i) {
cnt[i + 1] += cnt[i];
}
int k = bits[s].length; // k=|S|for (int x : bits[s]) { // 追加する要素を全探索int t = s ^ (1 << x);
boolean ok = true;
for (int j = 0; j < m; ++j) {
if (xs[j] >= k) { // Xj<k なる j に関する制約は満たされていることが保証されている
ok &= cnt[ys[j]] <= zs[j];
}
}
if (ok) dp[s] += dp[t];
}
}
pw.println(dp[(1 << n) - 1]);
}
F - Graph Smoothing
一回の選択で辺 が選択されたときの頂点 への寄与を考える．
のとき:
のとき:
従って， 行列 の要素を全て で初期化し，各辺 に対して
で更新し，行列累乗で を求めてベクトル に掛けると答えのベクトルが求まる．
// mod 関連の演算をやるクラスstaticfinal ModArithmetic ma = ModArithmetic1000000007.INSTANCE;
// mod M 上の行列演算をやるクラスstaticfinal ModMatrixFactory mmf = new ModMatrixFactory(ma);
publicstaticvoid solve(ExtendedScanner sc, FastPrintStream pw) {
int n = sc.nextInt();
int m = sc.nextInt();
int k = sc.nextInt();
long im = ma.inv(m);
long i2 = ma.inv(2);
long[] a = sc.longs(n);
long[][] mat = newlong[n][n];
for (int i = 0; i < m; ++i) {
int u = sc.nextInt() - 1;
int v = sc.nextInt() - 1;
for (int j = 0; j < n; ++j) {
if (j == u) {
mat[j][j] += ma.mul(i2, im);
mat[j][v] += ma.mul(i2, im);
} elseif (j == v) {
mat[j][j] += ma.mul(i2, im);
mat[j][u] += ma.mul(i2, im);
} else {
mat[j][j] += im;
}
}
}
long[] x = mmf.create(mat).pow(k).mul(a);
for (long e : x) {
pw.println(e);
}
}
// 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)
に対して
に対して
のとき
のとき
かつ
かつ
かつ
かつ
に対して単調増加な値を，左下の区画では
