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! πͺ