簡単ではあると思うのですが、最後の問題を理論値($18$ 分ノーペナ)で通せた人はいなかったっぽい？

自分は $29$ 分かかりましたが優勝しました。

後ろの $3$ 問だけ解説します。

デイトレード

問題

長さ $N$ の数列 $A, B$ が与えられます。

$0$ で初期化された変数 $x$ に対して、$i = 1, 2, \dots, N$ の順に以下のいずれか $1$ つを選びます。

$x$ から $A_{i}$ を引く
$x$ に $A_{i}$ を足す
何もしない

ただし、引く操作と足す操作は交互である必要があり、最初の引く操作の前に足す操作をしてはいけません。

最終的な $x$ の最大値を出力してください。

$1\leq N\leq 10^{5}$

$1\leq A_{i}\leq 10^{9}$

$1\leq B_{i}\leq 10^{9}$

解説

$i$ 回目まで見て、次にする操作が足す操作であるときの $x$ の最大値
$i$ 回目まで見て、次にする操作が引く操作であるときの $x$ の最大値

これらが求まれば良いです。$i$ 回目のこれらの値から $i + 1$ 回目のこれらの値が求まります。$2$ 状態を持った動的計画法で $O(N)$ で求められます。

#include <bits/stdc++.h>
using namespace std;
template<class T> bool chmax(T &a,T b){if(a<b){a=b;return 1;}else return 0;}
using ll=long long;

int main(){
    ll N;
    cin >> N;
    vector<ll> A(N), B(N);
    rep(i, 0, N) cin >> A[i];
    rep(i, 0, N) cin >> B[i];
    // dp[0] が次に引く場合
    // dp[1] が次に足す場合
    vector<ll> dp(2);
    dp[1] = -(1ll << 60);
    rep(i, 0, N){
        // 何もしない
        auto n_dp = dp;
        // 足す操作
        chmax(n_dp[0], dp[1] + B[i]);
        // 引く操作
        chmax(n_dp[1], dp[0] - A[i]);
        // 更新
        swap(n_dp, dp);
    }
    cout << dp[0] << "\n";
}

Sum of Largest Primes

問題

正の整数 $x$ に対して、$f(x)$ を次のように定義します：

$x$ を割り切る最大の素数。ただし、$x$ を割り切る素数が一つも存在しなければ $0$ 。

$Q$ 回にわたって正の整数 $N$ が与えられるので、

$$\sum_{k = 1}^{N}\sum_{l = 1}^{N} f(kl)$$

をそれぞれ求めてください。

$1 \leq Q\leq 150000$

$1 \leq N\leq 150000$

解説

$N = X$ の答えを $S(X)$ とおくと、以下が成り立ちます。

$$S(X + 1) - S(X) = f(X + 1) + 2 \times \sum_{k = 1}^{X} \max(f(X + 1), f(k))$$

$S(X)$ がわかっているとき、$f(k) < f(X + 1)$ となる $k$ の数と、そうでないものに対する $f(k)$ の総和が求められるならば $S(X + 1)$ も求められます。

適当に segment tree 等で管理すれば、$S(X)$ が全て十分高速に求まります。

seg1 は最大素因数が i であるような数、seg2 は最大素因数が i であるような数に i をかけたものです。区間和を高速に取れるようにしています。

時間計算量は $O(N \log(N))$ です。

#include <bits/stdc++.h>
using namespace std;
#include <atcoder/segtree>
using ll = long long;
ll op(ll a, ll b){
    return a + b;
}
ll e(){
    return 0;
}

int main(){
    const int L = 150100;
    atcoder::segtree<ll, op, e> seg1(L), seg2(L);
    vector<int> pri(L, 0);
    for (int i = 2; i < L; i++) if (pri[i] == 0){
        for (int j = i; j < L; j += i){
            pri[j] = i;
        }
    }
    vector<ll> ans(L);
    seg1.set(0, 1);
    for (int i = 2; i < L; i++){
        ll X = seg1.prod(0, pri[i]);
        ll Y = seg2.prod(0, pri[i]);
        ans[i] = ans[i - 1] + (ll)pri[i] * (2 * X + 1) + 2 * (seg2.all_prod() - Y);
        seg1.set(pri[i], seg1.get(pri[i]) + 1);
        seg2.set(pri[i], seg1.get(pri[i]) * pri[i]);
    }
    int Q;
    cin >> Q;
    while (Q--){
        int N;
        cin >> N;
        cout << ans[N] << "\n";
    }
}

replace AB

問題

A と B からなる文字列 $S, T$ が与えられます。に対して、次の操作を好きな回数行います。

$S$ の連続部分文字列であって AB であるものを $1$ つ選ぶ。それを $T$ で置き換える。

操作を終了した時の最終的な $S$ の長さの最大値が存在するか判定し、するならばその長さを $998244353$ で割った余りを求めてください。

$1 \leq |S| \leq 10 ^5$

$1 \leq |T| \leq 10 ^5$

解説

$|T|\leq 2$ のとき

操作しても長さが増えないので、答えは $|S|$

$S$ に `AB` が含まれていないとき

操作できないので、答えは $|S|$

$T$ に `AB` が含まれているとき

無限回操作できるので、$|T|>2$ ならば、答えは inf

これ以降は、以下を仮定する

$T$ は B を $n$ 文字並べた後、その後ろに A を ${m}$ 文字並べた文字列。ただし、$n + m > 2$

また、以下のことを前提とする

操作回数の最大値を求めれば、答えは自明に求まる

$n = 0$ のとき

$S$ の先頭に B がある限りそれを取り除くと言う操作をします。その操作後の $S$ に含まれる B の数だけ問題文中の操作ができます。

操作は B を $m - 1 (> 0)$ 個の A に置き換えていることと同じなので、最初の A 以降の B を前から順に置き換えることが可能です。

(最初は嘘をかいていたが、shiomusubi さんによる指摘によって修正)

$m = 0$ のとき

一般に、$S,T$ にそれぞれに対して、前後を反転し、A と B を入れ替えても、答えは変わらない。よって上記のことをして、 $n = 0$ のケースに帰着

$n = 1$ のとき

$S$ の先頭にある B を取り除いても答えは変わらないので、取り除く

自身より前に B がない B に対して操作できる回数は、前にある A の数になる

よって前から順に B に対して操作をし、前にある A の数を適時更新すれば良い

### 操作回数
ans = 0
### A の数
count = 0

for c in S:
    if c == 'A':
        ### 前にある A の数が 1 増える
        count += 1

    if c == 'B':
        ### 前にある A の数だけ操作できる
        ans += count
        ### A の数は倍増する
        count *= m

$m = 1$ のとき

一般に、$S,T$ にそれぞれに対して、前後を反転し、A と B を入れ替えても、答えは変わらない。よって上記のことをして、 $n = 1$ のケースに帰着

以上より、残るケースは以下を満たす

$T$ に含まれる A と B の数は $2$ 個以上

$T$ は正規表現で BB(B*)(A*)AA と表される

このとき、以下が成り立つ

$S$ の連続部分文字列として、AAB , ABB, ABAB のいずれかが含まれるとき、無限回操作できる

`AAB` が含まれるとき

AAB

ABB(B*)(A*)AA

BB(B*)(A*)AABBB(B*)(A*)AA

$2$ 回操作して再び AAB が含まれる状態にできるため、無限回操作できる

`ABB` が含まれるとき

AAB と同様に示せる、具体的に、$T$ が BBAA であるときの操作例を記す

(AB)B

BBAAB

BBA(AB)

BBABBAA

BB(ABB)AA

`ABAB` が含まれるとき

$2$ 回操作することで AABB が含まれるようになる

よってこれら $3$ つの文字列にいずれかが含まれるとき、操作回数は無限になる。これらの文字列を含まず、AB が含まれるような文字列は (B*)AB(A*) と表される文字列のみなので、 $1$ 回しか操作できない。

#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i = a; i < (int)b; i++)
#include <atcoder/modint>
using mint = atcoder::modint998244353;

void solve(){
    string S, T;
    cin >> S >> T;
    auto rev = [&]() -> void {
        reverse(S.begin(), S.end());
        reverse(T.begin(), T.end());
        for (auto &c : S) c ^= 3;
        for (auto &c : T) c ^= 3;
    };
    bool zero = 1;
    rep(i, 1, S.size()) if (S[i - 1] == 'A' && S[i] == 'B'){
        zero = 0;
    }
    if ((int)T.size() <= 2) zero = 1;
    if (zero){
        cout << S.size() << "\n";
        return;
    }
    rep(i, 1, T.size()) if (T[i - 1] == 'A' && T[i] == 'B'){
        cout << "inf\n";
        return;
    }
    if (T.back() == 'B') rev();
    if (T[0] == 'A'){
        mint ans = S.size();
        bool ok = 0;
        for (auto c : S){
            if (c == 'A') ok = 1;
            else if (ok) ans += T.size() - 2;
        }
        cout << ans.val() << "\n";
        return;
    }
    if (T[(int)T.size() - 2] == 'B') rev();
    if (T[1] == 'A'){
        mint ans = S.size();
        mint tmp = 0;
        for (auto c : S){
            if (c == 'A') tmp += 1;
            else ans += tmp * (T.size() - 2), tmp *= (T.size() - 1);
        }
        cout << ans.val() << "\n";
        return;
    }
    rep(i, 1, S.size()){
        if (S[i - 1] == 'A' && S[i] == 'B'){
            S[i - 1] ^= 3;
            S[i] ^= 3;
            rep(j, 1, S.size()) if (S[j - 1] == 'A' && S[j] == 'B'){
                cout << "inf\n";
                return;
            }
            cout << T.size() + S.size() - 2 << "\n";
            return;
        }
    }
}

int main(){
    int t;
    cin >> t;
    while (t--) solve();
}