l r v : $\displaystyle \bigoplus _ {i = l} ^ {r - 1} (c _ i - v)$ が $0$ でなければ A と出力,$0$ ならば B と出力.ここで,$\oplus$ はビット毎の排他的論理和であり,また $c _ l \geq v$ が保証される.
実行時間制限 : 5 sec
制約
$1\leq N, M, Q \leq 2\cdot 10 ^ 5$
$0\leq c _ i \lt M $
各クエリ l r v について,
$0\leq l \lt r \leq N $
$0\leq v \lt M $
解法
如何にも SIMD で頑張れば通りそうな問題.クエリ処理で現れる $c _ i - v$ は $2\times 10 ^ 5$ 未満なので,32 bit 整数で扱うことができる.従って,256 bit のレジスタで $8$ つずつまとめて処理することで,高速化できる.
$\displaystyle v = \min _ { i : \mathrm{even} } a _ i \gt \max _ { i : \mathrm{odd} } a _ i$ または $\displaystyle v = \min _ { i : \mathrm{odd} } a _ i \gt \max _ { i : \mathrm{even} } a _ i$ を満たす $v = p _ k$ を固定した場合の長さの最大値を考える。
列 $x = (x _ 1, \ldots, x _ N)$ および $y = (y _ 1, \ldots, y _ {N - 1})$ を以下で定義する。
$$
\begin{aligned}
x _ i & := \begin{cases} -1 & \text{if $p _ i = v\;(\mathrm{i.e.}\; i = k)$} \\ 0 & \text{if $p _ i \lt v$} \\ +1 & \text{if $p _ i \gt v$} \end{cases} , \\
y _ i & := \begin{cases} 1 & \text{if $x _ i \neq x _ { i + 1 }$} \\ 0 & \text{if $x _ i = x _ { i + 1 }$} \end{cases} .
\end{aligned}
$$
h, w = map(int, input().split())
a, b = map(int, input().split())
if a >= h and b <= w:
print("Yes")
else:
print("No")
B - 穴の開いた硬貨
全ての硬貨が互いに倍数・約数関係にあるので、大きい順に貪欲に使うことで硬貨の枚数を最小化できる。
従って、各 $C _ i := B _ i - A _ i$ に対して $C _ i \bmod 100 \geq 50$ なら $50$ 円玉が一枚、$C _ i \bmod 10 \geq 5$ なら $5$ 円玉が一枚必要となる。
ans = 0for _ inrange(int(input())):
a, b = map(int, input().split())
r = b - a
ans += r % 100 >= 50
ans += r % 10 >= 5print(ans)
C - 最速正解者
問題文の通りに実装する。Python だと ord や chr で都度変換してると面倒なので dict で処理すると楽そう。
d = {}
for i inrange(int(input())):
p, v = input().split()
if v == 'WA'or p in d:
continue
d[p] = i + 1for key in'ABCDEF':
print(d[key])
D - 試験
問題文で与えられている通りに順列 $P = (1, 2, \ldots, N)$ をソートする。
#include <algorithm>#include <iostream>#include <numeric>#include <vector>intmain() {
int n;
std::cin >> n;
std::vector<int> a(n), b(n);
for (auto &e : a) std::cin >> e;
for (auto &e : b) std::cin >> e;
std::vector<int> p(n);
std::iota(p.begin(), p.end(), 0);
std::sort(
p.begin(), p.end(),
[&](int i, int j) {
if (a[i] + b[i] != a[j] + b[j]) {
return a[i] + b[i] > a[j] + b[j];
} elseif (a[i] != a[j]) {
return a[i] > a[j];
} else {
return i < j;
}
}
);
for (int i = 0; i < n; ++i) {
std::cout << p[i] + 1 << " \n"[i == n - 1];
}
return0;
}
E - キーボード
問題文通りに注意深く実装する。
#include <iostream>intmain() {
std::string s;
std::cin >> s;
int n = s.size();
longlong ans = 0;
char p;
for (int i = 0; i < n; ++i) {
if (i == 0) {
ans += 500;
} elseif (p == s[i]) {
ans += 301;
} elseif (('1' <= p and p <= '5') == ('1' <= s[i] and s[i] <= '5')) {
ans += 210;
} else {
ans += 100;
}
p = s[i];
}
std::cout << ans << std::endl;
return0;
}
#include <array>#include <iostream>#include <vector>using Row = std::array<int, 3>;
using Vec = Row;
using Matrix = std::array<Row, 3>;
Matrix operator*(const Matrix &A, const Matrix &B) {
Matrix C{};
for (int i = 0; i < 3; ++i) for (int j = 0; j < 3; ++j) for (int k = 0; k < 3; ++k) {
C[i][k] += A[i][j] * B[j][k];
}
return C;
}
Vec operator*(const Matrix &A, const Vec &x) {
Vec y{};
for (int i = 0; i < 3; ++i) for (int j = 0; j < 3; ++j) {
y[i] += A[i][j] * x[j];
}
return y;
}
intmain() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n, q;
std::cin >> n >> q;
Matrix CW_inv {
Row { 0, -1, n - 1 },
Row { 1, 0, 0 },
Row { 0, 0, 1 }
};
Matrix CCW_inv {
Row { 0, 1, 0 },
Row { -1, 0, n - 1 },
Row { 0, 0, 1 }
};
Matrix UD_inv {
Row { -1, 0, n - 1 },
Row { 0, 1, 0 },
Row { 0, 0, 1 }
};
Matrix LR_inv {
Row { 1, 0, 0 },
Row { 0, -1, n - 1 },
Row { 0, 0, 1 }
};
Matrix A {
Row { 1, 0, 0 },
Row { 0, 1, 0 },
Row { 0, 0, 1 }
};
std::vectorans(n, std::vector(n, 0));
while (q --> 0) {
int t;
std::cin >> t;
if (t == 1) {
int x, y;
std::cin >> x >> y;
--x, --y;
Vec pos = A * Vec { x, y, 1 };
ans[pos[0]][pos[1]] ^= 1;
} elseif (t == 2) {
char c;
std::cin >> c;
A = A * (c == 'A' ? CW_inv : CCW_inv);
} elseif (t == 3) {
char c;
std::cin >> c;
A = A * (c == 'A' ? UD_inv : LR_inv);
}
}
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
Vec pos = A * Vec { i, j, 1 };
std::cout << ans[pos[0]][pos[1]];
}
std::cout << '\n';
}
return0;
}
(これ難しくない?)
K - ガソリンスタンド
ガソリンスタンドの個数が少ないので、どのガソリンスタンドを経由するかを全探索することを考える。$a _ i$ を経由する場合の $s, t$ 間の最短距離 $d _ i (s, t)$ は $d _ i (s, t) = \mathrm{dist}(a _ i, s) + \mathrm{dist}(a _ i, t)$ と書けるので、各 $i = 1,\ldots, K$ に対して $\mathrm{dist}(a _ i, v)$ を計算しておくことにすれば前計算 $O(K (N + M))$、クエリ $O(K)$ でこの問題を解くことが出来る。全体の計算量は $O(K (N + M + Q))$。
#include <deque>#include <iostream>#include <limits>#include <vector>intmain() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n, m, q, k;
std::cin >> n >> m >> q >> k;
std::vector<int> a(k);
for (int &e : a) {
std::cin >> e;
--e;
}
std::vector<std::vector<int>> g(n);
for (int i = 0; i < m; ++i) {
int u, v;
std::cin >> u >> v;
--u, --v;
g[u].push_back(v);
g[v].push_back(u);
}
std::vectordist(k, std::vector(n, -1));
for (int i = 0; i < k; ++i) {
dist[i][a[i]] = 0;
std::deque<int> dq { a[i] };
while (dq.size()) {
int u = dq.front();
dq.pop_front();
for (int v : g[u]) {
if (dist[i][v] < 0) {
dist[i][v] = dist[i][u] + 1;
dq.push_back(v);
}
}
}
}
while (q --> 0) {
int s, t;
std::cin >> s >> t;
--s, --t;
int ans = std::numeric_limits<int>::max();
for (int i = 0; i < k; ++i) {
ans = std::min(ans, dist[i][s] + dist[i][t]);
}
std::cout << ans << '\n';
}
return0;
}
L - 嘘つきな生徒たち
$A$ を reverse して狭義単調増加にするために必要な要素の変更回数を求める。
添え字 $i _ 1 \lt i _ 2 \lt \cdots \lt i _ k$ を変更せずに残すとすると、狭義単調増加の条件から $j = 1, \ldots, k - 1$ に対して $A _ { i _ j } + (i _ { j + 1 } - i _ j) \leq A _ { i _ { j + 1} }$、すなわち $A _ { i _ j } - i _ j \leq A _ { i _ { j + 1} } - i _ { j + 1 }$ を満たす必要がある。
実はこれでは十分ではなく、添字 $0,\ldots, i _ 1 - 1$ および $i _ k + 1, \ldots, N - 1$ で変更後の値が $0$ 以上 $P$ 以下に収まるために、追加で $0 \leq A _ { i _ 1 } - { i _ 1 }$ および $A _ { i _ k } - { i _ k } \leq P - N + 1$ を満たす必要がある。
以上より、条件をまとめると以下のように書け、これは必要十分条件である。
$$
0 \leq A _ { i _ 1 } - i _ 1 \leq \cdots \leq A _ { i _ k } - i _ k \leq P - N + 1
$$
#include <algorithm>#include <iostream>#include <limits>#include <vector>constexprint inf = std::numeric_limits<int>::max();
intmain() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n, p;
std::cin >> n >> p;
std::vector<int> a(n);
for (auto it = a.rbegin(); it != a.rend(); ++it) std::cin >> *it;
for (int i = 0; i < n; ++i) {
a[i] -= i;
if (a[i] > p - n + 1or a[i] < 0) {
a[i] = -inf;
}
}
std::vectordp(n + 1, inf);
dp[0] = 0;
for (int v : a) {
if (v == -inf) continue;
int x = std::upper_bound(dp.begin(), dp.end(), v) - dp.begin();
dp[x] = v;
}
for (int i = n; i >= 0; --i) {
if (dp[i] == inf) continue;
std::cout << n - i << std::endl;
break;
}
return0;
}
M - 名前の変更
index アクセスのできる set があれば 殴れる (解説を確認したところ、想定解でした) 問題。
#include <iostream>#include <ext/pb_ds/assoc_container.hpp>#include <ext/pb_ds/tree_policy.hpp>usingnamespace __gnu_pbds;
template <typename T>
using ordered_set = tree<T, null_type, std::less<T>, rb_tree_tag, tree_order_statistics_node_update>;
intmain() {
int n, q;
std::cin >> n >> q;
std::vector<std::string> ans(n);
ordered_set<std::pair<std::string, int>> mp;
for (int i = 0; i < n; ++i) {
std::string s;
std::cin >> s;
mp.insert(std::pair { ans[i] = s, i });
}
while (q --> 0) {
int x;
std::string t;
std::cin >> x >> t;
--x;
auto [old_name, i] = *mp.find_by_order(x);
mp.erase(std::pair { old_name, i });
mp.insert(std::pair { ans[i] = t, i });
}
for (int i = 0; i < n; ++i) {
std::cout << ans[i] << " \n"[i == n - 1];
}
return0;
}
#include <complex>#include <iomanip>#include <iostream>#include <vector>using coordinate_t = longdouble;
using Point = std::complex<coordinate_t>;
using Line = std::pair<Point, Point>;
using Polygon = std::vector<Point>;
constexpr coordinate_t EPS = 1e-9;
intsgn(coordinate_t x) {
return x < -EPS ? -1 : x > +EPS ? +1 : 0;
}
coordinate_t det(const Point &x, const Point &y) {
return x.real() * y.imag() - x.imag() * y.real();
}
Point cross_point(const Line &l1, const Line &l2) {
Point u = l1.second - l1.first, v = l2.first - l2.second, c = l2.first - l1.first;
return l2.first - det(u, c) / det(u, v) * v;
}
autoconvex_cut(const Polygon &convex, const Line &l) {
constauto &[la, lb] = l;
Polygon res;
int sz = convex.size();
for (int i = 0; i < sz; ++i) {
int j = i + 1;
if (j == sz) j -= sz;
const Point &a = convex[i], &b = convex[j];
int da = sgn(det(lb - la, a - la));
if (da >= 0) res.push_back(a);
int db = sgn(det(lb - la, b - la));
if (da * db < 0) res.push_back(cross_point(l, Line { a, b }));
}
return res;
}
coordinate_t signed_area(const Polygon &poly) {
coordinate_t res = 0;
int n = poly.size();
for (int i = 0; i < n; ++i) res += det(poly[i], poly[(i + 1) % n]);
return res / 2;
}
intmain() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n, m;
std::cin >> n >> m;
Polygon s(n), t(m);
for (int i = 0; i < n; ++i) {
coordinate_t x, y;
std::cin >> x >> y;
s[i] = { x, y };
}
for (int i = 0; i < m; ++i) {
coordinate_t x, y;
std::cin >> x >> y;
t[i] = { x, y };
}
for (int i = 0; i < m; ++i) {
s = convex_cut(s, Line { t[i], t[(i + 1) % m] });
}
std::cout << std::fixed << std::setprecision(20) << std::abs(signed_area(s)) << std::endl;
return0;
}
O - ペアスコア
$B _ j - B _ i = k\; (1\leq k \leq N)$ を満たす $i, j$ の答えへの寄与を考える (主客転倒)。$i, j$ の並べ方は $N - (B _ j - B _ i)$ 通り、それ以外の並べ方は $(N - 2) !$ 通りである。従って、寄与は $S _ k \cdot (N - k) \cdot (N - 2) !$ と求められる。
以上より、$C _ k := \# \{ (i, j) \mid B _ j - B _ i = k \}$ と定義すれば、求める答えは $\displaystyle (N - 2) ! \cdot \sum _ {k = 1} ^ N C _ k \cdot S _ k \cdot (N - k)$ である。
あとは各 $C _ k$ を高速に求められればよいが、$\displaystyle M := \sup_i B_i = 100000$ に対して $B ' _ i = M - B _ i \geq 0$ として代わりに $B _ i + B ' _ j = k + M $ を満たす $i, j$ の組を数えることにする。和の条件になったので、これは高速フーリエ変換を用いて計算できる。計算量は $O(N + M \log M)$。
#include <iostream>#include <atcoder/modint>#include <atcoder/convolution>using mint = atcoder::modint998244353;
constexprint M = 100000;
intmain() {
int n;
std::cin >> n;
std::vector<mint> f(M + 1), g(M + 1);
for (int i = 0; i < n; ++i) {
int v;
std::cin >> v;
++f[v];
++g[M - v];
}
std::vector<int> s(n + 1);
for (int i = 1; i <= n; ++i) {
std::cin >> s[i];
}
auto c = atcoder::convolution(f, g);
c.erase(c.begin(), c.begin() + M);
c.resize(n + 1, 0);
mint ans = 0;
for (int i = 1; i <= n; ++i) {
ans += c[i] * (n - i) * s[i];
}
for (int i = 1; i <= n - 2; ++i) {
ans *= i;
}
std::cout << ans.val() << std::endl;
return0;
}
$$
\sum _ {x = 2} ^ N \sum _ { y = 2 } ^ N f ( x , y ) \tag{1}
$$
$\gcd ( a , b ) = x$ などの等号条件よりも $x \mid \gcd ( a , b ) \iff x\mid a \land x\mid b$ のような倍数条件の方が扱いやすいです。そこで、次のように $g$ を定義します。
$$
g ( x , y ) : = \# \{ ( i , j ) : 1 \leq i \leq j \leq N , \;
x \mid \gcd ( i , j ), \; y \mid \gcd ( P _ i , P _ j ) \}
$$
このとき、$g(x,y)$ は次のように表されます。
$$
g ( x , y ) = \# \left \{ ( i , j ) \; :\; 1 \leq i \leq j \leq \left\lfloor\frac { N }{ x } \right\rfloor, y \mid P _ { i x }, y \mid P _ { j x} \right \}
$$
$c(x,y)$ を $c ( x, y ) := \# \left \{ i \; :\; 1 \leq i \leq \lfloor N / x \rfloor,\; y \mid P _ { i x } \right \}$ で定義すれば、$g(x,y)$ は $c$ を用いて以下のように計算できます。
$g$ の計算方法は分かったので、次は $f(x,y)$ を $g$ を使って表します。$\displaystyle g( x , y ) = \sum _ { x \mid x ' } \sum _ { y \mid y ' } f ( x ' , y ' ) $ より、$\displaystyle f ( x , y ) = \sum _ { x \mid a ' } \sum _ { y \mid b ' } \mu ( a ' / x ) \cdot \mu (b ' / y ) \cdot g ( a' , b' )$ です。
証明
$$
\begin{aligned}
f ( x , y )
&= \sum _ { x \mid x ' } f ( x' , y ) \cdot \delta _ { x , x ' } \\
&= \sum _ { x \mid x ' } f ( x' , y ) \sum _ { a \mid (x ' / x )} \mu ( a ) \\
&= \sum _ { x \mid x ' } \sum _ { ax \mid x ' } f ( x' , y ) \cdot \mu ( a ) \\
&= \sum _ { x \mid a ' \land a' \mid x ' } f ( x' , y ) \cdot \mu ( a ' / x ) \\
&= \sum _ { x \mid a ' } \mu ( a ' / x ) \sum _ { a' \mid x ' } f ( x' , y ) \\
&= \sum _ { x \mid a ' } \sum _ { y \mid b ' } \mu ( a ' / x ) \cdot \mu (b ' / y ) \sum _ { a' \mid x ' } \sum _ { b' \mid y ' } f ( x' , y' ) \\
&= \sum _ { x \mid a ' } \sum _ { y \mid b ' } \mu ( a ' / x ) \cdot \mu (b ' / y ) \cdot g ( a' , b' )
\end{aligned}
$$
(書いてから気づいたんですが、和を展開するのが素直ですね)
以上より、答えは次のように表されます。
$$
\begin{aligned}
\sum _ { x = 2 } ^ N \sum _ { y = 2 } ^ N f ( x , y )
&= \sum _ { x = 2 } ^ N \sum _ { y = 2 } ^ N \sum _ { x \mid a ' } \sum _ { y \mid b ' } \mu ( a ' / x ) \cdot \mu (b ' / y ) \cdot g ( a' , b' ) \\
&= \sum _ { a' = 2 } ^ N \sum _ { b' = 2 } ^ N g ( a' , b' ) \sum _ { x \mid a ' , x \neq 1 } \mu ( a ' / x ) \sum _ { y \mid b ', y \neq 1 } \mu (b ' / y ) \\
&= \sum _ { a' = 2 } ^ N \sum _ { b' = 2 } ^ N g ( a' , b' ) \cdot ( \delta _ { a ', 1 } - \mu ( a ' ) ) \cdot ( \delta _ { b ', 1 } - \mu ( b ' ) ) \\
&= \sum _ { a' = 2 } ^ N \sum _ { b' = 2 } ^ N g ( a' , b' ) \cdot \mu ( a ' ) \cdot \mu ( b ' ) \\
&= \sum _ { a' = 2 } ^ N \mu ( a ' ) \sum _ { b' = 2 } ^ N g ( a' , b' ) \cdot \mu ( b ' ) \\
&= \sum _ { a' = 2 } ^ N \mu ( a ' ) \sum _ { b' = 2 } ^ N \dfrac{c(a', b')\cdot (c(a', b') + 1)}{2} \cdot \mu ( b ' )
\end{aligned}
$$
これにより、区間 $M ( v _ i ) = [ L _ { v _ i } , R _ { v _ i } ]$ に完全に包含されるバケットについては最短距離が $O(1)$ で求まります。そして、このようなバケットの個数は $O(N/B)$ 個です。
また、$[ L _ { v _ i } , R _ { v _ i } ]$ に包含されないバケットであって、$[ L _ { v _ i } , R _ { v _ i } ]$ との共通部分が空でないものは高々 2 つであり、その区間長は $B$ 以下です。この部分に関しては LCA などを用いて一つずつ距離を求めることにすれば、$O(B \log N)$ ないし $O(B)$ で残りの部分が計算できます。