Translation Notice
This article was machine-translated using DeepSeek-R1.
- Original Version: Authored in Chinese by myself
- Accuracy Advisory: Potential discrepancies may exist between translations
- Precedence: The Chinese text shall prevail in case of ambiguity
- Feedback: Technical suggestions regarding translation quality are welcomed
Problem Summary
Given two positive integers $B,G$ ($1\le B,G\le 1000$ and $B\ne G$), determine which is larger.
Analysis
Just simulate.
Code
1
2
3
4
5
6
7
8
9
10
|
#include <cstdio>
using namespace std;
int main()
{
int b, g;
scanf("%d%d", &b, &g);
puts(b > g? "Bat": "Glove");
return 0;
}
|
Problem Summary
Given $A,M,L,R$.
For any integer $k$, Snuke places a Christmas tree at position $A+kM$ on the number line.
Find the number of trees in the interval $[L,R]$.
$-10^{18}\le A\le 10^{18}$
$1\le M\le 10^9$
$-10^{18}\le L\le R\le 10^{18}$
Analysis
Notice that for any integer $x$, there’s a tree at $x$ if and only if $x \equiv A \ (\bmod \ M)$. This can be transformed to $(x-A) \mid M$. Therefore, shift coordinates by $A$ and count multiples of $M$ in $[L-A, R-A]$.
Code
Note the handling of negative numbers in C++.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
#include <cstdio>
using namespace std;
using LL = long long;
int main()
{
LL a, l, r;
int m;
scanf("%lld%d%lld%lld", &a, &m, &l, &r);
l -= a, r -= a;
if(l < 0) l = -((-l) / m * m);
else l = (l + m - 1) / m * m;
if(r < 0) r = -((-r + m - 1) / m * m);
else r = r / m * m;
printf("%lld\n", (r - l) / m + 1);
return 0;
}
|
Problem Summary
Given a sequence $S=(1,1,2,2,\dots,N,N)$ of length $2N$.
Remove one occurrence of each $A_1,\dots,A_K$ from $S$, leaving $2N-K$ numbers.
Pair these remaining numbers (possibly with one unpaired) to minimize the sum of absolute differences. Output this minimum sum.
$1\le K\le N\le 2\times 10^5$
$1\le A_1 < A_2 < \dots < A_K\le N$
Analysis
The $N-K$ complete pairs can be optimally matched as self-pairs. The remaining $K$ single elements must be paired optimally.
For even $K$, pair adjacent elements. For odd $K$, precompute prefix and suffix sums to efficiently find the optimal single element to exclude.
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
|
#include <cstdio>
#define maxn 200005
using namespace std;
inline void setmin(int& x, int y)
{
if(y < x) x = y;
}
int a[maxn], pre[maxn], suf[maxn];
int main()
{
int n, k;
scanf("%d%d", &n, &k);
for(int i=1; i<=k; i++)
scanf("%d", a + i);
if(!(k & 1))
{
int ans = 0;
for(int i=1; i<=k; i+=2)
ans += a[i + 1] - a[i];
printf("%d\n", ans);
return 0;
}
for(int i=1; i<k; i+=2)
pre[i] = pre[i + 1] = pre[i - 1] + a[i + 1] - a[i];
for(int i=k-1; i>0; i-=2)
suf[i] = suf[i + 1] = suf[i + 2] + a[i + 1] - a[i];
int ans = 1e9;
for(int i=1; i<=k; i++)
{
int cur = i & 1? pre[i - 1] + suf[i + 1]
: a[i + 1] - a[i - 1] + pre[i - 2] + suf[i + 2];
setmin(ans, cur);
}
printf("%d\n", ans);
return 0;
}
|
Problem Summary
Given $N$ sleighs with reindeer requirements $R_i$ and $Q$ queries, each asking the maximum number of sleighs that can be pulled with $X$ reindeer.
Analysis
Sort $R_i$ and compute prefix sums. For each query, use binary search to find the largest prefix sum ≤ $X$.
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
#include <cstdio>
#include <algorithm>
#define maxn 200005
using namespace std;
using LL = long long;
LL s[maxn];
int main()
{
int n, q;
scanf("%d%d", &n, &q);
for(int i=0; i<n; i++)
scanf("%lld", s + i);
sort(s, s + n);
for(int i=1; i<n; i++)
s[i] += s[i - 1];
while(q--)
{
LL x;
scanf("%lld", &x);
printf("%d\n", int(upper_bound(s, s + n, x) - s));
}
return 0;
}
|
Problem Summary
A grid has red (.) and green (#) cells. Randomly paint one red cell green and compute the expected number of green connected components modulo 998244353.
Analysis
Use Union-Find to precompute green components. For each red cell, count adjacent distinct green components. The contribution to the expectation is the original count minus (adjacent components - 1).
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
|
#include <cstdio>
#include <unordered_map>
#include <set>
#include <atcoder/modint>
#define maxn 1005
using namespace std;
using modint = atcoder::modint998244353;
int n, m, fa[maxn * maxn];
char s[maxn][maxn];
int find(int x) { return fa[x] == x? fa[x]: fa[x] = find(fa[x]); }
inline int calc(int x, int y) { return x * m + y; }
inline int fc(int x, int y) { return find(calc(x, y)); }
inline void merge(int x, int y) { fa[find(x)] = find(y); }
int main()
{
scanf("%d%d", &n, &m);
for(int i=0; i<n; i++)
scanf("%s", s[i]);
int k = n * m;
for(int i=0; i<k; i++)
fa[i] = i;
for(int i=0; i<n; i++)
for(int j=0; j<m; j++)
{
if(s[i][j] != '#') continue;
if(i && s[i - 1][j] == '#') merge(calc(i, j), calc(i - 1, j));
if(j && s[i][j - 1] == '#') merge(calc(i, j), calc(i, j - 1));
}
int cnt = 0, tot = 0;
for(int i=0; i<n; i++)
for(int j=0; j<m; j++)
if(s[i][j] == '#' && fc(i, j) == calc(i, j))
cnt ++;
modint ans = 0;
for(int i=0; i<n; i++)
for(int j=0; j<m; j++)
if(s[i][j] == '.')
{
set<int> S;
if(i && s[i - 1][j] == '#') S.insert(fc(i - 1, j));
if(s[i + 1][j] == '#') S.insert(fc(i + 1, j));
if(j && s[i][j - 1] == '#') S.insert(fc(i, j - 1));
if(s[i][j + 1] == '#') S.insert(fc(i, j + 1));
int cur = cnt - (int)S.size() + 1;
ans += cur, tot ++;
}
printf("%d\n", (ans / tot).val());
return 0;
}
|
Problem Summary
Santa delivers gifts in sequence, carrying up to $K$ gifts. Find the minimal travel distance starting and ending at home.
Analysis
Dynamic programming optimized with a deque and prefix sums. Maintain the minimal distance for each possible remaining gift count.
Code
Implementation 1: deque + multiset
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
|
#include <cstdio>
#include <deque>
#include <set>
#define maxn 200005
using namespace std;
using ld = long double;
const ld INF = 2e18l;
int x[maxn], y[maxn];
inline ld dis(int i, int j)
{
return __builtin_hypotl(x[i] - x[j], y[i] - y[j]);
}
int main()
{
int n, k;
scanf("%d%d", &n, &k);
for(int i=0; i<=n; i++)
scanf("%d%d", x + i, y + i);
deque<ld> f;
multiset<ld> s;
k --;
for(int i=0; i<k; i++)
f.push_back(INF), s.insert(INF);
f.push_back(dis(0, 1)), s.insert(dis(0, 1));
ld dt = 0;
for(int i=2; i<=n; i++)
{
ld lt = *s.begin() + dis(i - 1, 0) + dis(0, i) + dt;
s.erase(s.find(f.front())), f.pop_front();
dt += dis(i - 1, i), lt -= dt;
f.push_back(lt), s.insert(lt);
}
printf("%.15Lf\n", dt + *s.begin() + dis(n, 0));
return 0;
}
|
Implementation 2: Monotonic Queue
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
#include <cstdio>
#include <deque>
#define maxn 200005
using namespace std;
int x[maxn], y[maxn];
inline double dis(int i, int j)
{
return __builtin_hypotl(x[i] - x[j], y[i] - y[j]);
}
int main()
{
int n, k;
scanf("%d%d", &n, &k);
for(int i=0; i<=n; i++)
scanf("%d%d", x + i, y + i);
deque<pair<double, int>> f;
f.emplace_back(dis(0, 1), 1);
double dt = 0;
for(int i=2; i<=n; i++)
{
double lt = f.front().first + dis(i - 1, 0) + dis(0, i) + dt;
if(f.front().second == i - k) f.pop_front();
dt += dis(i - 1, i), lt -= dt;
while(!f.empty() && f.back().first >= lt) f.pop_back();
f.emplace_back(lt, i);
}
printf("%.15lf\n", dt + f.front().first + dis(n, 0));
return 0;
}
|
Problem Summary
Randomly paint a green cell red and compute the expected number of green connected components modulo 998244353.
Analysis
Use Tarjan’s algorithm to identify articulation points. The removal of a non-articulation point increases the component count by its degree minus one.
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
|
#include <cstdio>
#include <vector>
#include <atcoder/modint>
#define maxn 1000005
using namespace std;
using modint = atcoder::modint998244353;
inline void setmin(int& x, int y)
{
if(y < x) x = y;
}
vector<int> G[maxn];
inline void add(int x, int y)
{
G[x].push_back(y);
G[y].push_back(x);
}
int root, low[maxn], cnt, dfn[maxn], ncut[maxn];
void tarjan(int v)
{
low[v] = dfn[v] = ++cnt;
ncut[v] = v != root;
for(int u: G[v])
if(!dfn[u])
{
tarjan(u);
if(low[u] >= dfn[v])
ncut[v] ++;
setmin(low[v], low[u]);
}
else setmin(low[v], dfn[u]);
}
char s[1005][1005];
int id[1005][1005];
int main()
{
int n, m;
scanf("%d%d", &n, &m);
for(int i=1; i<=n; i++)
scanf("%s", s[i] + 1);
int num = 0;
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++)
if(s[i][j] == '#')
{
id[i][j] = ++num;
if(s[i - 1][j] == '#') add(num, id[i - 1][j]);
if(s[i][j - 1] == '#') add(num, id[i][j - 1]);
}
int cc = -1;
for(int i=1; i<=num; i++)
if(!dfn[i])
tarjan(root = i), cc ++;
modint ans = 0;
for(int i=1; i<=num; i++)
ans += cc + ncut[i];
printf("%d\n", (ans / num).val());
return 0;
}
|
Postscript
First, wishing everyone a Merry Christmas in advance 🎉! From the title to the problem settings, this contest is intricately tied to Christmas, showing AtCoder’s meticulous preparation for this festive event 🎄.
Regrettably, during the contest, I solved A~E and G, submitting F just 51 seconds after the contest ended, which was AC. A near AK, but narrowly missed by under a minute 😅. Hoping to perform better next time, and best wishes to all contestants. Keep striving! 💪