Codeforces 1368B: Codeforces Subsequences

Codeforces 1368B C++ 和 Python 一解.

终于看到一道比较有趣的 constructive algorithm 的题目了.

分析

本题是 “乘法原理” 的经典应用之一: 每一个内容为 codeforces 子序列都需要在源串中各选择十个字符连续重复的字符串 (指连续的 c, o, d 等十个字符串) 中的一个字符. 若假定源串 $s$ 中 c, o, d 等字符各连续重复 $a_0,a_1,a_2,\cdots,a_9$ 次, 则最终能生成的 codeforces 子序列共有 $l=a_0a_1a_2\cdots a_9$ 个. 而为满足题意, 需要选择合适的 $a_0,a_1,a_2,\cdots,a_9$, 使得 $l\geq k$ 且 $L=a_0+a_1+a_2+\cdots+a_9$ 尽可能小.

一种贪心的策略

我们知道, 根据均值不等式, 对于长度为 $n$ 的正有限实数列 ${a_i}$, 有

$$
\sqrt[n]{\prod^{n}{i=1}{a_i}}\leq\sum^{n}{i=1}{a_i},
$$

当且仅当 ${a_i}$ 是常数列时取等号. 对于本题, 可以猜想: 当左式恒定, 即 $l$ 恒定时, 若要使右式 (也即 $L$) 尽可能小, 则需要选择相差不大的 $a_i(i=0,1,\cdots,9)$. 这即是一种贪心策略.

我们希望 $a_i$ 的极差尽可能小, 一种选择方法是令其中一部分 $a_i$ 比另一部分恰好大 $1$ (当然理想情况是这些 $a_i$ 都相等). 不妨假设 $a_0,a_1,\cdots,a_{m-1}$ ($m=0,1,\cdots,10$, 当 $m=0$ 时规定 $a_i=a$, 当 $m=10$ 时规定 $a_i=a+1$) 都等于 $a+1(a\in\mathbb{N}^{*})$, $a_m,a_{m+1},\cdots,a_9$ 都等于 $a$. 那么

$$
l=(a+1)^{10-m}a^m,\
L=(10-m)(a+1)+ma=10a-m+10.
$$

$a$ 和 $m$ 的确定

首先我们关注 $m=10$ 即 $l=a^{10}$ 的情况. 注意到此时若要使 $l\geq k$, 则 $a\geq\sqrt[10]{k}$.

而当 $a$ 固定时, 对于不同的 $m$, 有 $\sup l=(a+1)^{10}$, $\inf l=a^{10}$, 且考虑到当 $a_p>a_q$ 时恒有 $\left.L\right|{a=a_p}\geq\left.L\right|{a=a_q}$, 则 $a$ 可以选取 $\lfloor\sqrt[10]{k}\rfloor$.

对于 $m$, 理论上根据 $l\geq k$ 可以推导得到 $m\leq\dfrac{10\ln(a+1)-\ln k}{\ln(a+1)-\ln a}$, 但在实际编程中考虑到浮点数存在的误差 (直接用此式计算无法通过 Codeforces 测试集), 我们需要利用大整数 (long long unsigned 足够) 从 $m=0$ 或 $m=10$ 开始逐个测试 (理论上也可以使用二分查找, 但本题的数据规模下不必要), 直到找到符合要求的 $m$. 为方便起见, 确定 $a$ 的过程依然使用了对数法, 同时为尽可能保证计算准确, 代码中使用了自定义的下取整函数 better_floor().

在 Python 中, 考虑到其原生支持处理超长整数, 对上述推导公式修改为 $k(a+1)^m\leq a^m(a+1)^{10}$, 同样可以达到题意所需要求, 而这式两边即对应下述代码中的 left 和 right.

代码

C++

#include <cmath>
#include <cstring>
#include <iostream>
#define EPS (1e-14)

using namespace std;

const string base("codeforces");

double better_floor(double x)
{
    double y = ceil(x);
    
    return (y - x < EPS ? y : floor(x));
}

int calc_m(long long unsigned k, int a)
{
    long long unsigned l = 1;
    int m = 10;

    for (int i = 0; i < m; ++i)
    {
        l *= a;
    }
    while (l < k && m-- >= 0)
    {
        l = l * (a + 1) / a;
    }

    return m;
}

int main()
{
    long long unsigned k;
    int a, m;

    cin >> k;

    a = int(better_floor(pow(k, 0.1)));
    m = calc_m(k, a);

    for (int i = 0; i < 10 - m; ++i)
    {
        cout << string(a + 1, base[i]);
    }
    for (int i = 10 - m; i < 10; ++i)
    {
        cout << string(a, base[i]);
    }

    return 0;
}

Python

def calc_m3(k, a):
    left, right = k, (a + 1) ** 10
    for i in range(1, 12):
        left *= a + 1
        right *= a
        if left > right:
            return i - 1
    return -1

k = int(input())

base = 'codeforces'
a = int(k ** 0.1)
m = calc_m3(k, a)
for i in range(10 - m):
    print(base[i] * (a + 1), end='')
for i in range(10 - m, 10):
    print(base[i] * a, end='')