KEYENCE Programming Contest 2024（AtCoder Beginner Contest 374）

\(solved: A B C D E\)

\(F\) 和 \(G\) 铸币 \(xkm\) 不会😭.

A – Takahashi san 2

判断给定的字符串末尾是不是 "san", 直接取 substr 判断就行.

void solve() {
    string s;
    cin >> s;
    if (s.size() >= 3 && s.substr(s.size() - 3) == "san"s) {
        cout << "Yes" << '\n';
    } else {
        cout << "No" << '\n';
    }
}

B – Unvarnished Report

给定两个字符串, 查询两个字符串第一个不一样的地方在哪, 若都相等输出 \(0\).

先判断是否相等, 然后 for 循环判断即可.

void solve() {
    string s, t;
    cin >> s >> t;
    if (s == t)
        cout << "0" << '\n';
    else {
        for (int i = 1; i < INF; i++) {
            if (i > s.size() || i > t.size()) {
                cout << i << '\n';
                return;
            }
            if (s[i - 1] != t[i - 1]) {
                cout << i << '\n';
                return;
            }
        }
    }
}

C – Separated Lunch

要求将所有部门分成两组, 让最大的组人数尽可能少.

先想到背包, 然后发现太大了根本没法做.

然后看一眼数据范围, 只有最多 \(20\) 个部门, 那直接暴力枚举 \(2^{20}\) 个状态即可.

void solve() {
    int n;
    cin >> n;
    vector<int> k(n);
    for (int i = 0; i < n; i++) cin >> k[i];
    LL sum = accumulate(k.begin(), k.end(), 0LL);
    LL ans = sum;
    for (int i = 0; i < (1 << n); i++) {
        LL a = 0;
        for (int j = 0; j < n; j++) {
            if ((i >> j) & 1) {
                a += k[j];
            }
        }
        ans = min(ans, max(a, sum - a));
    }
    cout << ans << '\n';
}

D – Laser Marking

在二维平面上打印 \(N\) 个线段. 单纯移动是每秒 \(S\) 个距离, 打印的时候是每秒 \(T\) 个距离. 对于重合的地方要求打印两次, 也就是说每次打印的结果是独立的.可以从线段的任一端点开始一直打印到另一端点, 中间不能暂停. 求起始坐标 \((0, 0)\) 的最短打印时间.

\(N \leq 6\), 那就只有 \(6! \times 2^6\) 种方式, 爆搜即可.

void solve() {
    int n;
    cin >> n;
    int t, s;
    cin >> s >> t;
    vector<array<int, 4>> lines(n);
    vector<char> vis(n);
    for (int i = 0; i < n; i++) {
        cin >> lines[i][0] >> lines[i][1] >> lines[i][2] >> lines[i][3];
    }
    double ans = INF;
    auto dfs = [&](auto self, int d, int x, int y, double time) -> void {
        if (d == n + 1) {
            ans = min(ans, time);
            return;
        }
        double pretime = time;
        for (int i = 0; i < n; i++) {
            if (!vis[i]) {
                vis[i] = 1;
                time += 1.0 / s * sqrt(pow(x - lines[i][0], 2) + pow(y - lines[i][1], 2));
                time += 1.0 / t * sqrt(pow(lines[i][0] - lines[i][2], 2) + pow(lines[i][1] - lines[i][3], 2));
                self(self, d + 1, lines[i][2], lines[i][3], time);
                time = pretime;

                time += 1.0 / s * sqrt(pow(x - lines[i][2], 2) + pow(y - lines[i][3], 2));
                time += 1.0 / t * sqrt(pow(lines[i][0] - lines[i][2], 2) + pow(lines[i][1] - lines[i][3], 2));
                self(self, d + 1, lines[i][0], lines[i][1], time);
                time = pretime;
                vis[i] = 0;
            }
        }
    };
    dfs(dfs, 1, 0, 0, 0);
    cout << fixed << setprecision(10) << ans << '\n';
}

E – Sensor Optimization Dilemma 2

生产产品, 一共要 \(N\) 个流程. 每个流程有两种机器, 机器有价格和生产效率, 可以购买任意个任意种类机器. 生产的效率为效率最低的流程. 现在给定预算, 要求最大生产效率.

最大生产效率显然可以二分, 然后考虑如何 \(check\).

背包是不行的, 因为每次预算是 \(1e7\) 级别, 那生产效率最多就是 \(1e9\).

那发现其实只有两种机器, 那一定有一种机器是不比另一种更不划算的, 最优解一定是买一些更划算的机器(或者不买), 然后差点生产效率用另一种填一下.

生产效率最大为 \(100\), 那直接暴力枚举买 \([0, 100]\) 次其中一种机器, 剩下买另一种机器的最小花费.

复杂度为 \(max(max(A_i), max(B_i)) \times nlog(max(max(A_i), max(B_i)) \times X)\).