初回 -> はじめに

ABC138を解きました。
4完です。
D問題につまって、他の人のコードをみました。

問題	時間	アルゴリズム	実行時間
A	1min	-	6ms
B	3min	-	6ms
C	2min	-	8ms
D	110min	木	129ms
E	55min	文字列マッチング	1415ms

A - Red or Not

    int a;
    string s;
    cin >> a >> s;
    cout << (3200 <= a ? s : "red");

そのままやるだけですね。
問題文もプログラムにしやすい書き方だと思います。

B - Resistors in Parallel

    int n;
    double a;
    double sum = 0.0;
    cin >> n;
    for(int i = 0; i < n; ++i)
    {
        cin >> a;
        sum += 1.0 / a;
    }
    printf("%.7f", 1.0 / sum);

数学的にシンプルな式が思いつかなかったのでそのままやりました。
丸め精度が不安でしたが、10^-5程度の誤差は許容とあったので助かりました。

C - Alchemist

    int n;
    cin >> n;
    vector<double> v(n);
    for(int i = 0; i < n; ++i)
    {
        cin >> v[i];
    }
    sort(v.begin(), v.end());

    double value = v[0];
    for(int i = 1; i < n; ++i)
    {
        value = (value + v[i]) / 2.0;
    }
    printf("%.7f", value);

ぶちゃけると数学的な考察はしていません。

暴論ととらえられるかもしれませんが、私なりの競技プログラミングのコツです。
こういう時はほとんどの場合で昇順か降順でソートして計算すると答えになります。
今回は最大値を求める問題だったので、昇順と降順で値が大きくなった方を選びました。
もしダメだったらその時に考えていたと思います。

※こういう時
・数列の要素ごとに処理する
・処理した順番によって値が変わる
・求まる値を最大化・最小化する
・四則演算を使う (mod とか xor とか約数とかは使わない)

D - Ki

vector< vector<int> > edge(200004, vector<int>());
ll counter[200004];
bool seen[200004];

void dfs(int node) // search child
{
    if (seen[node]) { return; }
    seen[node] = true;

    for(const auto& e : edge[node]) {
        if (seen[e]) { // 親
            counter[node] += counter[e];
            break;
        }
    }

    for(const auto& e : edge[node]) {
        if (!seen[e]) { // 子
            dfs(e);
        }
    }
}

void solve()
{
    fill(counter, counter + 200004, 0);
    fill(seen, seen + 200004, false);

    ll n, q, a, b, p, x;
    cin >> n >> q;

    for(ll i = 0; i < n - 1; ++i) {
        cin >> a >> b;
        edge[a].push_back(b);
        edge[b].push_back(a);
    }
    for(ll i = 0; i < q; ++i) {
        cin >> p >> x;
        counter[p] += x;
    }

    dfs(1);
    for(int i = 1; i <= n; ++i)
    {
        cout << counter[i] << " ";
    }
}

愚直にやるとO(N^3)くらいでしょうか。
N = [2, 200000]なので余裕をもってTLEしますね。

問題文には

点 p_j を根とする部分木に含まれるすべての頂点のカウンターの値に x_j を足す。

とありますが、部分木のすべての頂点ではなく根のカウンターのみ更新します。
入力をすべてそのように処理したあと、各頂点から根に向かって移動します。
移動時に通った頂点のカウンターをすべて足した値が頂点のカウンターになりますね。
いわゆる葉から根へ向かう処理です。
このやり方だとO(N logN)となります。

さて、解き方自体はわかったのですが、データの持ち方をミスりました。
この問題は入力時点での親子関係は不明ですね。(普通の問題は、特に言及されていなければ不明です。)
それとは気づかずに葉から根へ向かう処理を書いていました。
そのために木構造がうまく設定されず、WAを量産しました。反省。

他の人の解法を見て、根から葉へ向かう処理にしました。
葉から根へ向かっても、根から葉へ向かっても、計算量は同じO(N logN)です。

E - Strings of Impurity

    string s, t;
    cin >> s >> t;
    ll s_size = s.length();
    ll t_size = t.length();

    vector<int> bin[26] = {};
    for(int i = 0; i < s_size; ++i)
    {
        bin[ s[i] - 'a' ].emplace_back(i);
    }
    for(int i = 0; i < t_size; ++i)
    {
        if (bin[ t[i] - 'a' ].empty())
        {
            cout << "-1";
            return;
        }
    }

    vector<int> t_num(t_size, -1);
    t_num[0] = bin[ t[0] - 'a' ][0];
    for(int i = 1; i < t_size; ++i)
    {
        t_num[i] = bin[ t[i] - 'a' ][0];
        for(int j = 0; j < bin[ t[i] - 'a' ].size(); ++j)
        {
            if (bin[ t[i] - 'a' ][j] > t_num[i - 1])
            {
                t_num[i] = bin[ t[i] - 'a' ][j];
                break;
            }
        }
    }

    ll ans = 0;
    for(int i = 1; i < t_size; ++i)
    {
        if (t_num[i - 1] >= t_num[i])
        {
            ans += s_size;
        }
    }
    cout << ans + t_num.back() + 1;

ACしましたが実行時間かかりすぎです。反省。
O(|t|^2) です。制約は|t| = [1, 10000] なので普通はTLEです。
実際の計算量は |t|*|t| / 26程度のため、なんとかACになりました。

実行時間がかかっているのであまりスマートではないですが、解法です。

↓
↓
↓

tの各文字がsの何番目の文字かを配列に保存します。
その配列はできる昇順の長さが大きくなるようにします。

例えばs = "constest", t = "tston" のとき
s_num : { 1,2,3,4,5,6,7 } として
t_num : { 4,6,4,2,3 }
となります。
sの中に"t"という文字は4,7の2つです。つまり、"t"は4と7のどちらでもいいです。
この時、t_numの2つめの4を7にすると昇順の長さが増えますね。
つまり、
t_num : { 4,6,4,2,3 }
よりも
t_num : { 4,6,7,2,3 }
のほうが昇順になっている長さが大きいです。

このようにt_numを設定すると、t_numの値を順にみていったとき、
・前の値よりも小さくなった時に|s|を加算
・t_numの最後まで来たらその時の値を加算
の結果が答えになります。

以上です。ありがとうございました。