AtCoder Beginner Contest 260 A~F Solutions

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

A - A Unique Letter

Problem Summary

Given a string $S$ of length 3.
Output any character that appears exactly once in $S$ (e.g., in abc, any of the three characters can be the answer).

If no such character exists, output -1.

Constraints:

  • $S$ has length 3
  • $S$ consists of lowercase English letters.

Input Format

$S$

Output Format

Output any valid answer.

Samples

$S$ Output
pop o
abc a/b/c
xxx -1

Analysis

Let the three input characters be a, b, c.

  1. If $a = b = c$, output -1.
  2. Check for two equal characters in different positions:
  • xxy pattern ($a = b$): output $c$
  • xyx pattern ($a = c$): output $b$
  • yxx pattern ($b = c$): output $a$
  • xyz pattern (all distinct): output any character

In the code, the last two cases are merged (handled by a single else, outputting $a$).

Code 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

#include <cstdio>
using namespace std;

int main()
{
    char a = getchar(), b = getchar(), c = getchar();
    if(a == b && b == c) puts("-1");
    else if(a == c) putchar(b);
    else if(a == b) putchar(c);
    else putchar(a);
    return 0;
}

B - Better Students Are Needed!

Problem Summary

$N$ candidates took an exam.
Candidate $i$ scored $A_i$ in math and $B_i$ in English.

The company selects candidates in three stages:

  1. Top $X$ math scores are selected.
  2. From remaining candidates, top $Y$ English scores are selected.
  3. From remaining candidates, top $Z$ total scores (math + English) are selected.

Note: Candidates with equal scores are ordered by their IDs.

Output all selected candidate IDs in ascending order.

Constraints:
$1\le N\le 1000$
$0\le X,Y,Z\le N$
$1\le X+Y+Z\le N$
$0\le A_i,B_i\le 100$

Input Format

$N~X~Y~Z$
$A_1~A_2~\dots~A_N$
$B_1~B_2~\dots~B_N$

Output Format

Output selected candidate IDs in ascending order, one per line.

Analysis

Two approaches:

  1. Use pair<int, int> for candidates and sort vectors/use priority queues for each selection stage.
  2. Use a struct to store candidate data and sort three times with different criteria.

See Code 1 and Code 2.

Code

Code 1 (vector + sort) 

 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

#include <cstdio>
#include <vector>
#include <algorithm>
#define maxn 1005
using namespace std;
    
int a[maxn], b[maxn];
bool used[maxn];
    
int main()
{
    int n, x, y, z;
    scanf("%d%d%d%d", &n, &x, &y, &z);
    for(int i=0; i<n; i++)
        scanf("%d", a + i);
    for(int i=0; i<n; i++)
        scanf("%d", b + i);
    
    // Math
    vector<pair<int, int>> sel_a;
    for(int i=0; i<n; i++)
        sel_a.emplace_back(-a[i], i);
    sort(sel_a.begin(), sel_a.end());
    for(int i=0; i<x; i++)
        used[sel_a[i].second] = true;
    
    // English
    vector<pair<int, int>> sel_b;
    for(int i=0; i<n; i++)
        if(!used[i])
            sel_b.emplace_back(-b[i], i);
    sort(sel_b.begin(), sel_b.end());
    for(int i=0; i<y; i++)
        used[sel_b[i].second] = true;
    
    // Total
    vector<pair<int, int>> sel_t;
    for(int i=0; i<n; i++)
        if(!used[i])
            sel_t.emplace_back(-(a[i] + b[i]), i);
    sort(sel_t.begin(), sel_t.end());
    for(int i=0; i<z; i++)
        used[sel_t[i].second] = true;
    
    for(int i=0; i<n; i++)
        if(used[i])
            printf("%d\n", i + 1);
    return 0;
}

Code 2 (struct-based sorting) 

 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

#include <cstdio>
#include <vector>
#include <algorithm>
#define maxn 1005
using namespace std;

struct Emp {
    int math, eng, id;
} emps[maxn];

inline bool cmp1(const Emp& e1, const Emp& e2) {
    return e1.math == e2.math?
            e1.id < e2.id:
            e1.math > e2.math;
}

inline bool cmp2(const Emp& e1, const Emp& e2) {
    return e1.eng == e2.eng?
            e1.id < e2.id:
            e1.eng > e2.eng;
}

inline bool cmp3(const Emp& e1, const Emp& e2) {
    int tot1 = e1.math + e1.eng, tot2 = e2.eng + e2.math;
    return tot1 == tot2?
            e1.id < e2.id:
            tot1 > tot2;
}

inline bool cmp4(const Emp& e1, const Emp& e2) {
    return e1.id < e2.id;
}

int main()
{
    int n, x, y, z;
    scanf("%d%d%d%d", &n, &x, &y, &z);
    
    for(int i=0; i<n; i++)
        scanf("%d", &emps[i].math),
        emps[i].id = i;
    for(int i=0; i<n; i++)
        scanf("%d", &emps[i].eng);
    
    auto last = emps + n;
    sort(emps, last, cmp1);
    sort(emps + x, last, cmp2);
    sort(emps + x + y, last, cmp3);
    sort(emps, emps + x + y + z, cmp4);
    
    for(int i=0; i<x+y+z; i++)
        printf("%d\n", emps[i].id + 1);
    return 0;
}

C - Changing Jewels

Problem Summary

Takahashi has an level $N$ red jewel.
He can perform the following operations any number of times:

  • Convert a level $N$ red jewel into “1 level $N-1$ red jewel + $X$ level $N$ blue jewels”.
  • Convert a level $N$ blue jewel into “1 level $N-1$ red jewel + $Y$ level $N-1$ blue jewels”.

What’s the maximum number of level 1 blue jewels he can obtain?

Constraints:
$1\le N\le 10$
$1\le X,Y\le 5$

Input Format

$N~X~Y$

Output Format

Output the maximum count of level 1 blue jewels.

Samples

$N$ $X$ $Y$ Output
$2$ $3$ $4$ $12$
$10$ $5$ $5$ $3942349900$

Note: Beware of 32-bit integer overflow.

Analysis

To maximize level 1 blue jewels, process jewels from higher levels downwards.
Maintain two variables: red (level $k$ red jewels) and blue (level $k$ blue jewels).
For each level from $N$ down to 2:

  1. Convert all red jewels to lower-level red and blue jewels.
  2. Convert all blue jewels to lower-level red and blue jewels.

Time complexity: $\mathcal O(N)$.

Code 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

#include <cstdio>
using namespace std;

int main()
{
    int n, x, y;
    scanf("%d%d%d", &n, &x, &y);
    long long red = 1LL, blue = 0LL;
    while(--n)
    {
        blue += red * x;
        red += blue, blue *= y;
    }
    printf("%lld\n", blue);
    return 0;
}

D - Draw Your Cards

Problem Summary

Process $N$ cards with unique numbers $P_1,\dots,P_N$ in order.
For each card $P_i$:

  • Find the topmost card in existing piles that is $\ge P_i$. Place $P_i$ on it.
  • If no such pile exists, create a new pile.
  • If a pile reaches $K$ cards, remove all its cards immediately.

Output the time each card is removed (or -1 if never removed).

Constraints:
$1\le K\le N \le 2\times 10^5$
$P$ is a permutation of $(1,2,\dots,N)$.

Analysis

Use a Union-Find structure to track parent cards and set-based operations to find the correct pile.
Maintain a set of current pile tops for efficient lookups.
For each card, track the pile size and update when merged.

Time complexity: $\mathcal O(N \log N)$.

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

#include <cstdio>
#include <set>
#define maxn 200005
using namespace std;

int fa[maxn], eat[maxn], sz[maxn];

int find(int x) {
    return fa[x] == x? x: fa[x] = find(fa[x]);
}

int main()
{
    int n, k;
    scanf("%d%d", &n, &k);
    set<int> cards;
    for(int i=0; i<n; i++)
    {
        int x;
        scanf("%d", &x);
        x --;
        eat[x] = -1, fa[x] = x;
        if(k == 1)
        {
            eat[x] = i + 1;
            continue;
        }
        auto it = cards.upper_bound(x);
        if(it == cards.end())
            cards.insert(x), sz[x] = 1;
        else
        {
            fa[*it] = x;
            cards.erase(it);
            if((sz[x] = sz[*it] + 1) == k)
                eat[x] = i + 1;
            else cards.insert(x);
        }
    }
    for(int i=0; i<n; i++)
        printf("%d\n", eat[find(i)]);
    return 0;
}

E - At Least One

Problem Summary

Given $M$ and $N$ pairs $(A_i,B_i)$, count all consecutive subarrays $[l,r]$ of $[1,M]$ such that for each $i$, $A_i$ or $B_i$ is in $[l,r]$.

Let $f(k)$ be the count of valid subarrays of length $k$. Output $f(1),\dots,f(M)$.

Constraints:
$1\le N\le 2\times 10^5$
$2\le M\le 2\times 10^5$
$1\le A_i < B_i\le M$

Analysis

Use a sliding window approach. For each $l$, find the smallest $r$ where all pairs are covered.
Preprocess each position’s contribution to coverage and track counts using difference arrays.

Time complexity: $\mathcal O(N + M)$.

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

#include <cstdio>
#include <vector>
#define maxn 200005
using namespace std;

vector<int> inv[maxn];
int cnt[maxn], ans[maxn];

int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    for(int i=0; i<n; i++)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        inv[a].push_back(i);
        inv[b].push_back(i);
    }
    int left = n;
    for(int i=1, j=1; i<=m; i++)
    {
        for(; j <= m && left > 0; j++)
            for(int x: inv[j])
                if(++cnt[x] == 1)
                    left --;
        if(left > 0) break;
        ans[j - i] ++, ans[m - i + 2] --;
        for(int x: inv[i])
            if(--cnt[x] == 0)
                left ++;
    }
    for(int i=1; i<=m; i++)
        printf("%d ", ans[i] += ans[i - 1]);
    return 0;
}

F - Find 4-cycle

Problem Summary

Given a bipartite graph between sets $U$ and $V$, find any 4-cycle (four nodes forming a cycle). Output the nodes or -1.

Constraints:
$2\le |U| \le 3\times 10^5$
$2\le |V| \le 3000$
$4\le M\le \min(|U|\times|V|,3\times 10^5)$

Analysis

Exploit the small size of $V$. For each node in $V$, track pairs of nodes in $U$ connected to it. Use a matrix to record pairs and detect overlaps.

Time complexity: $\mathcal O(T^2)$, feasible due to $T \le 3000$.

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

#include <cstdio>
#include <cstring>
#include <vector>
#define maxs 300005
#define maxt 3005
using namespace std;

vector<int> G[maxs];
int f[maxt][maxt];

int main()
{
    int s, t, m;
    scanf("%d%d%d", &s, &t, &m);
    while(m--)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        G[--u].push_back(--v - s);
    }
    memset(f, -1, sizeof(f));
    for(int i=0; i<s; i++)
        for(int j=0; j+1<G[i].size(); j++)
            for(int k=j+1; k<G[i].size(); k++)
            {
                int u = G[i][j], v = G[i][k];
                if(u > v) u ^= v ^= u ^= v;
                if(f[u][v] != -1)
                {
                    printf("%d %d %d %d\n", f[u][v] + 1, i + 1, u + s + 1, v + s + 1);
                    return 0;
                }
                f[u][v] = i;
            }
    puts("-1");
    return 0;
}
© 2020 - 2025 GoodCoder's Blog
Built with Hugo
Theme Stack designed by Jimmy