复盘｜AtCoder ABC 319

信息奥赛复盘｜AtCoder ABC 319（2023.12.1）

比赛信息 📚

VP时间：2023 年 12 月 1 日 19:15 - 20:55

竞赛链接：https://atcoder.jp/contests/abc319

个人情况 ✍️

个人排名：331/690

AC情况：3/7

A 签到题，纯纯拼手速 ✅

B 签到题，数学 + 模拟 ✅

C 思维题 ✅

D 思维 + 模拟，比较难的D题 ❌

E 赛场看出可以用线性DP，但是不知道怎么表示状态 ❌

F 需要维护区间最大值，已知树状数组不行，线段树可以，但是不会线段树 ❌

G 未看 ❌

题目列表 🧑🏻‍💻

题目名称	难度	赛时VP	补题
A - Legendary Players	🟢	✅	✅
B - Measure	🟢	✅	✅
C - False Hope	🟡	❌	✅
D - Minimum Width	🟢	✅	✅
E - Bus Stops	🟡	❌	✅
F - Fighter Takahashi	🟡	❌
G - Counting Shortest Paths	🟡	❌

---

题解 🚀

A - Legendary Players

题目信息 📚

【题目描述】

In AtCoder, the top $10$ rated players’ usernames are displayed with a gold crown, and the top-rated player’s username is displayed with a platinum crown.

At the start of this contest, the usernames and ratings of the top $10$ rated players in the algorithm category are as follows:

tourist 3858
ksun48 3679
Benq 3658
Um_nik 3648
apiad 3638
Stonefeang 3630
ecnerwala 3613
mnbvmar 3555
newbiedmy 3516
semiexp 3481

You are given the username $S$ of one of these players. Print that player’s rating.

【输入】

The input is given from Standard Input in the following format:

$S$

【输出】

Print the rating of the corresponding player in one line.

【数据范围】

• $S$ is equal to one of the usernames of the top $10$ rated players in the algorithm category.

【输入样例1】

tourist

【输出样例1】

3858

【输入样例2】

semiexp

【输出样例2】

3481

【题目来源】

https://atcoder.jp/contests/abc319/tasks/abc319_a

---

题目解析 🍉

【题目分析】

A 签到题，纯纯拼手速。

【C++代码】

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;

int main() {
    string s; cin>>s;
    if (s == "tourist") cout << 3858 << endl;
    else if (s == "ksun48") cout << 3679 << endl;
    else if (s == "Benq")cout << 3658 << endl;
    else if (s == "Um_nik")cout << 3648 << endl;
    else if (s == "apiad")cout << 3638 << endl;
    else if (s == "Stonefeang")cout << 3630 << endl;
    else if (s == "ecnerwala")cout << 3613 << endl;
    else if (s == "mnbvmar")cout << 3555 << endl;
    else if (s == "newbiedmy")cout << 3516 << endl;
    else if (s == "semiexp")cout << 3481 << endl;

    return 0;
}

---

B - Measure

题目信息 📚

【题目描述】

You are given a positive integer $N$. Print a string of length $(N+1)$, $s_0s_1\ldots s_N$, defined as follows:

For each $i=0,1,2,\ldots,N$,

• If there is a divisor $j$ of $N$ that is between $1$ and $9$, inclusive, and $i$ is a multiple of $N/j$, then $s_i$ is the digit corresponding to the smallest such $j$ ($s_i$ will thus be one of 1, 2, …, 9);
• If no such $j$ exists, then $s_i$ is -.

【输入】

The input is given from Standard Input in the following format:

$N$

【输出】

Print the answer.

【数据范围】

• $1 \leq N \leq 1000$
• All input values are integers.

【输入样例1】

12

【输出样例1】

1-643-2-346-1

We will explain how to determine $s_i$ for some $i$.

• For $i = 0$, the divisors $j$ of $N$ between $1$ and $9$ such that $i$ is a multiple of $N/j$ are $1, 2, 3, 4, 6$. The smallest of these is $1$, so $s_0$ = 1.
• For $i = 4$, the divisors $j$ of $N$ between $1$ and $9$ such that $i$ is a multiple of $N/j$ are $3, 6$. The smallest of these is $3$, so $s_4$ = 3.
• For $i = 11$, there are no divisors $j$ of $N$ between $1$ and $9$ such that $i$ is a multiple of $N/j$, so $s_{11}$ = -.

【输入样例2】

7

【输出样例2】

17777771

【输入样例3】

1

【输出样例3】

11

【题目来源】

https://atcoder.jp/contests/abc319/tasks/abc319_b

---

题目解析 🍉

【题目分析】

数学 + 模拟。

【C++代码】✅

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;
int n;

int main() {
    cin >> n;

    string s;
    // 输出n+1个字符
    for (int i = 0; i <= n; i++) {
        bool flag = false;
        // 枚举1～9
        for (int j = 1; j <= 9; j++) {
            // j为n的因子，且(n/j)为i的因子
            if (n % j == 0 && i % (n / j) == 0) {
                cout << j;
                flag = true;
                break;
            }
        }
        if (!flag) cout << "-";
    }

    return 0;
}

---

C - False Hope

题目信息 📚

【题目描述】

There is a $3 \times 3$ grid with numbers between $1$ and $9$, inclusive, written in each square. The square at the $i$-th row from the top and $j$-th column from the left $(1 \leq i \leq 3, 1 \leq j \leq 3)$ contains the number $c_{i, j}$.

The same number may be written in different squares, but not in three consecutive cells vertically, horizontally, or diagonally. More precisely, it is guaranteed that $c_{i, j}$ satisfies all of the following conditions:

• $c_{i, 1} = c_{i, 2} = c_{i, 3}$ does not hold for any $1 \leq i \leq 3$.
• $c_{1, j} = c_{2, j} = c_{3, j}$ does not hold for any $1 \leq j \leq 3$.
• $c_{1, 1} = c_{2, 2} = c_{3, 3}$ does not hold.
• $c_{3, 1} = c_{2, 2} = c_{1, 3}$ does not hold.

Takahashi will see the numbers written in each cell in random order. He will get disappointed when there is a line (vertical, horizontal, or diagonal) that satisfies the following condition:

• The first two squares he sees contain the same number, but the last square contains a different number.

Find the probability that Takahashi sees the numbers in all the squares without getting disappointed.

【输入】

The input is given from Standard Input in the following format:

$c_{1,1}$ $c_{1,2}$ $c_{1,3}$

$c_{2,1}$ $c_{2,2}$ $c_{2,3}$

$c_{3,1}$ $c_{3,2}$ $c_{3,3}$

【输出】

Print one line containing the probability that Takahashi sees the numbers in all the squares without getting disappointed. Your answer will be considered correct if the absolute error from the true value is at most $10^{-8}$.

【数据范围】

• $c_{i,j} \in {1, 2, 3, 4, 5, 6, 7, 8, 9}$ $(1 \leq i \leq 3, 1 \leq j \leq 3)$.
• $c_{i,1} = c_{i,2} = c_{i,3}$ does not hold for any $1 \leq i \leq 3$.
• $c_{1,j} = c_{2,j} = c_{3,j}$ does not hold for any $1 \leq j \leq 3$.
• $c_{1,1} = c_{2,2} = c_{3,3}$ does not hold.
• $c_{3,1} = c_{2,2} = c_{1,3}$ does not hold.

【输入样例1】

3 1 9
2 5 6
2 7 1

【输出样例1】

0.666666666666666666666666666667

【输入样例2】

7 7 6
8 6 8
7 7 6

【输出样例2】

0.004982363315696649029982363316

【输入样例3】

3 6 7
1 9 7
5 7 5

【输出样例3】

0.4

【题目来源】

https://atcoder.jp/contests/abc319/tasks/abc319_c

---

题目解析 🍉

【题目分析】

枚举 + 排列。

优质题解传送门：https://anubhavnegi54.medium.com/false-hope-atcoder-abc-319-ed3a7d3e12c8

【C++代码】✅

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;
int g[10], order[10];
// 需要枚举判断的行、列、对角线
vector<tuple<int, int, int>> lines = {
        {1, 2, 3},  // 第一行
        {4, 5, 6},  // 第二行
        {7, 8, 9},  // 第三行
        {1, 4, 7},  // 第一列
        {2, 5, 8},  // 第二列
        {3, 6, 9},  // 第三列
        {1, 5, 9},  // 主对角线
        {3, 5, 7}   // 次对角线
};

// 查找值x在order中的下标
int findi(int x) {
    for (int i = 1; i <= 9; i++) if (order[i] == x) return i;
}

int main() {
    ios::sync_with_stdio(false);  //cin读入优化
    cin.tie(0);

    // 读入原始棋盘
    for (int i = 1; i <= 9; i++) cin >> g[i];

    // 设定初始排列顺序
    for (int i = 1; i <= 9; i++) order[i] = i;

    int ans = 0, tot = 0; // 设定答案数量与排列总数
    // 枚举所有的排列情况（9! = 362880）
    do {
        bool dis = false;
        tot++;
        // 对于当前排列，枚举所有行、列、对角线，判断是否有disappointed的情况
        for (auto t: lines) {
            // 如判断主对角线的3个元素是否存在disappointed的情况
            // 先取出主对角线元素下标1、5、9，分别赋给a、b、c
            // 然后查看1、5、9在当前order排列中的位次，赋给oa、ob、oc
            int a = get<0>(t), oa = findi(a);
            int b = get<1>(t), ob = findi(b);
            int c = get<2>(t), oc = findi(c);

            // 若1、5元素相同，且1、5在当前order中出现的顺序均早于9，说明存在disappointed的情况
            if (g[a] == g[b] && oa < oc && ob < oc) {
                dis = true;
                break;
            }

            // 同理，枚举1、9元素相同的情况
            if (g[a] == g[c] && oa < ob && oc < ob) {
                dis = true;
                break;
            }

            // 同理，枚举5、9元素相同的情况
            if (g[b] == g[c] && ob < oa && oc < oa) {
                dis = true;
                break;
            }
        }
        if (!dis) ans++;
    } while (next_permutation(order + 1, order + 9 + 1));

    // 输出答案
    cout << fixed << setprecision(10) << 1.0 * ans / tot << endl;

    return 0;
}

---

D - Minimum Width

题目信息 📚

【题目描述】

Takahashi is displaying a sentence with $N$ words in a window. All words have the same height, and the width of the $i$-th word $(1 \leq i \leq N)$ is $L_i$.

The words are displayed in the window separated by a space of width $1$. More precisely, when the sentence is displayed in a window of width $W$, the following conditions are satisfied:

• The sentence is divided into several lines.
• The first word is displayed at the beginning of the top line.
• The $i$-th word $(2 \leq i \leq N)$ is displayed either with a gap of $1$ after the $(i-1)$-th word, or at the beginning of the line below the line containing the $(i-1)$-th word. It will not be displayed anywhere else.
• The width of each line does not exceed $W$. Here, the width of a line refers to the distance from the left end of the leftmost word to the right end of the rightmost word.

When Takahashi displayed the sentence in the window, the sentence fit into $M$ or fewer lines. Find the minimum possible width of the window.

【输入】

The input is given from Standard Input in the following format:

$N$ $M$

$L_1$ $L_2$ $\dots$ $L_N$

【输出】

Print the answer in one line.

【数据范围】

• $1 \leq M \leq N \leq 2 \times 10^5$
• $1 \leq L_i \leq 10^9$ $(1 \leq i \leq N)$

All input values are integers.

【输入样例1】

13 3
9 5 2 7 1 8 8 2 1 5 2 3 6

【输出样例1】

26

【输入样例2】

10 1
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

【输出样例2】

10000000009

【输入样例3】

30 8
8 55 26 97 48 37 47 35 55 5 17 62 2 60 23 99 73 34 75 7 46 82 84 29 41 32 31 52 32 60

【输出样例3】

189

【题目来源】

https://atcoder.jp/contests/abc319/tasks/abc319_d

---

题目解析 🍉

【题目分析】

经典二分答案。

【C++代码】✅

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
LL a[N], n, m, sum = 0;

// 判断宽度为x的情况下，能否满足条件
bool check(LL x) {
    LL cur = 0;
    LL lines = 1;
    int i = 1;
    while (i <= n) {
        if (x < a[i]) return false;
        cur += a[i];
        if (cur == x) {
            if (i != n) lines++, cur = 0;
            i++;
        } else if (cur < x) cur++, i++;  // 添加一个末尾空格
        else if (cur > x) lines++, cur = 0;
    }
    return lines <= m;
}

int main() {
    ios::sync_with_stdio(false);  //cin读入优化
    cin.tie(0);

    // 读入数据并且计算最大可能宽度
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        sum += a[i];
    }
    sum += (n - 1);

    // 二分答案
    LL l = 1, r = sum;
    while (l < r) {
        LL mid = l + r >> 1;
        if (check(mid))
            r = mid;
        else
            l = mid + 1;
    }
    cout << l << endl;

    return 0;
}

---

E - Bus Stops

题目信息 📚

【题目描述】

Takahashi is initially at his house and is about to visit Aoki’s house.

There are $N$ bus stops numbered $1$ to $N$ between the two houses, and Takahashi can move between them in the following ways:

• He can walk from his house to bus stop $1$ in $X$ units of time.
• For each $i=1,2,\ldots,N-1$, a bus departs from bus stop $i$ at each time that is a multiple of $P_i$, and by taking this bus, he can get to bus stop $(i+1)$ in $T_i$ units of time. Here, the constraints guarantee that $1 \leq P_i \leq 8$.
• Takahashi can walk from bus stop $N$ to Aoki’s house in $Y$ units of time.

For each $i=1,2,\ldots,Q$, process the following query:

Find the earliest time that Takahashi can arrive at Aoki’s house when he leaves his house at time $q_i$.

Note that if he arrives at a bus stop exactly at the departure time of a bus, he can take that bus.

【输入】

The input is given from Standard Input in the following format:

$N$ $X$ $Y$

$P_1$, $T_1$

$P_2$, $T_2$

$\vdots$

$P_{N-1}$, $T_{N-1}$

$Q$

$q_1$

$q_2$

$\vdots$

$q_Q$

【输出】

Print $Q$ lines. For each $i=1,2,\ldots,Q$, the $i$-th line should contain the answer to the $i$-th query.

【数据范围】

• $2 \leq N \leq 10^5$
• $1 \leq X, Y \leq 10^9$
• $1 \leq P_i \leq 8$
• $1 \leq T_i \leq 10^9$
• $1 \leq Q \leq 2 \times 10^5$
• $0 \leq q_i \leq 10^9$

All input values are integers.

【输入样例1】

4 2 3
5 4
6 6
3 1
7
13
0
710511029
136397527
763027379
644706927
447672230

【输出样例1】

34
22
710511052
136397548
763027402
644706946
447672250

For the first query, Takahashi can move as follows to arrive at Aoki’s house at time $34$.

• Leave his house at time $13$.
• Walk from his house and arrive at bus stop $1$ at time $15$.
• Take the bus departing from bus stop $1$ at time $15$ and arrive at bus stop $2$ at time $19$.
• Take the bus departing from bus stop $2$ at time $24$ and arrive at bus stop $3$ at time $30$.
• Take the bus departing from bus stop $3$ at time $30$ and arrive at bus stop $4$ at time $31$.
• Walk from bus stop $4$ and arrive at Aoki’s house at time $34$.

For the second query, Takahashi can move as follows and arrive at Aoki’s house at time $22$.

• Leave his house at time $0$.
• Walk from his house and arrive at bus stop $1$ at time $2$.
• Take the bus departing from bus stop $1$ at time $5$ and arrive at bus stop $2$ at time $9$.
• Take the bus departing from bus stop $2$ at time $12$ and arrive at bus stop $3$ at time $18$.
• Take the bus departing from bus stop $3$ at time $18$ and arrive at bus stop $4$ at time $19$.
• Walk from bus stop $4$ and arrive at Aoki’s house at time $22$.

【题目来源】

https://atcoder.jp/contests/abc319/tasks/abc319_e

---

题目解析 🍉

【题目分析】

模拟 + 暴力做法很容易想到，但是如何优化是个比较大的难题。

需要运用 数学 + 思维 的方法。（具体过程见下面代码）

官方题解传送门

https://atcoder.jp/contests/abc319/editorial/7141

https://atcoder.jp/contests/abc319/editorial/7122

【C++代码】暴力 + 模拟（TLE）❌

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
LL n, x, y, q, p[N], t[N], s, e;

int main() {
    ios::sync_with_stdio(false);  //cin读入优化
    cin.tie(0);

    // 读入公交信息
    cin >> n >> x >> y;
    for (int i = 1; i <= n - 1; i++) {
        cin >> p[i] >> t[i];
    }

    // q次查询
    cin >> q;
    for (int i = 1; i <= q; i++) {
        // 模拟出发过程
        cin >> s;
        s += x; // 家到公交站1
        // 各个公交站点
        for (int j = 1; j <= n - 1; j++) {
            if (s % p[j])
                s = s + p[j] - s % p[j];
            s += t[j];
        }
        s += y;  // 公交站n到家
        cout << s << endl;
    }

    return 0;
}

【C++代码】预处理优化 ✅

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
LL n, x, y, q, p[N], t[N], s, e;
LL ans[1000];

int main() {
    ios::sync_with_stdio(false);  //cin读入优化
    cin.tie(0);

    // 读入相关数据
    cin >> n >> x >> y;
    for (int i = 1; i <= n - 1; i++) {
        cin >> p[i] >> t[i];
    }

    // 预处理一个大循环（lcm(1, 2, 3,...8) = 840）
    // 840为最极端的情况，即pi取遍了1～8
    // 在一般测试样例中，lcm(p1, p2...pn-1)一般到不了840
    // 但是大循环840一定是小循环的倍数，所以直接处理大循环即可
    for (int i = 0; i < 840; i++) {
        LL cur = i;
        for (int j = 1; j <= n - 1; j++) {
            if (cur % p[j])
                cur = cur + p[j] - cur % p[j];
            cur += t[j];
        }
        ans[i] = cur - i;   // ans[i]表示时刻i到达第一个站点，后续到达第n个公交站点需要的时间
    }

    // q次查询，每次查询只需要获得到达第一个站点的时间s+x
    // 就可以通过预处理的ans数组，算出在(s+x)在大循环840中的位置
    // ans[(s+x)%840]即为公交上花费的总时间
    // 最后再加上y即可
    cin >> q;
    for (int i = 1; i <= q; i++) {
        cin >> s;
        s += x;
        cout << s + ans[s % 840] + y << endl;
    }

    return 0;
}

---