复盘｜AtCoder ABC 125

信息奥赛复盘｜AtCoder ABC 125（2023.12.8）

比赛信息 📚

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

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

个人情况 ✍️

AC情况：2/4

A 签到题，纯纯拼手速 ✅

B DFS / 贪心皆可 ✅

C 看起来很难的水题，VP时未做出 ❌

D 翻转の思维题，解题思路非常巧妙，VP时未做出 ❌

题目列表 🧑🏻‍💻

题目名称	难度	赛时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++代码】✅

---