# 2021/11/30 TPC

## A
### 問題概要
TF Quiz で、自分と友達の解答、友達の正解数 $K$ があたえられるので、自分の最大正解数を求める

### 解法
自分と友達の共通数を $S$ として $\min(K, S) + \min(N - K, N - S)$

### 考察の流れ
問題文を読解（1分）
考察：LR貪欲系なのでよしなにやればよい（1分）
実装（2分）

### コメント

実装はやいな～～～～～
自分は$S\geq k$と$S<k$で場合分けしました(ruthen)

## B
### 問題概要
順列 $P$ があたえられるので、転倒しない最長部分列を求める

### 解法
LIS

### 考察の流れ
問題文を読解（3分）
考察：転倒しなければよい → LIS
実装：LIS のライブラリあったか？とりあえずセグ木とってくる（あわせて3分）
LIS 書く（2分）

## C
### 問題概要
$A$ から $B$ までの桁数の総和を求める

### 解法
実家

### 考察の流れ
問題文を読む、桁 DP やるだけ（1分）
実装：個数と和 2 つ必要、添字 1 つ間違えたところをデバッグ（9分）

### コード

ll solve(ll x) {
    string s = to_string(x);
    ll DP[17][2], DP2[17][2];
    rep(i, 17) rep(j, 2) DP[i][j] = 0, DP2[i][j] = 0;
    DP[0][1] = 1;
    DP2[0][1] = 0;

    rep(i, s.size()) {
        rep(j, 10) {
            if (j < s[i] - '0') {
                DP[i + 1][0] += DP[i][0] + DP[i][1];
                DP2[i + 1][0] += DP2[i][0] + DP[i][0] * j;
                DP2[i + 1][0] += DP2[i][1] + DP[i][1] * j;
            } else if (j == s[i] - '0') {
                DP[i + 1][0] += DP[i][0];
                DP[i + 1][1] += DP[i][1];
                DP2[i + 1][0] += DP2[i][0] + DP[i][0] * j;
                DP2[i + 1][1] += DP2[i][1] + DP[i][1] * j;
            } else {
                DP[i + 1][0] += DP[i][0];
                DP2[i + 1][0] += DP2[i][0] + DP[i][0] * j;
            }
        }
    }

    return DP2[s.size()][0] + DP2[s.size()][1];
}

signed main() {
    codeforces {
        ll n, m;
        cin >> n >> m;

        cout << solve(m) - solve(n - 1) << rt;
    }
}

### コメント
DP配列の添え字ってどうなってますか(ruthen)
追記：ありがとうございます
ちなみにruthenは↓です
多分桁DPのほうが考えることは少ないと思います
$10^i$の位の0,...,9は周期が$10^{i+1}$であることを利用しています

ll f(ll x) {
    if (x <= 1) return 0ll;
    // [0, x)
    ll p10 = 1, ans = 0;
    for (int i = 0; i <= 15; i++) {
        p10 *= 10;
        ans += (x / p10) * 45 * (p10 / 10);
        ll r = x % p10;
        for (int d = 0; d <= 9; d++) {
            ans += d * min(r, p10 / 10);
            r -= min(r, p10 / 10);
        }
    }
    return ans;
}

にゃるほどにゃ

## D
文字列と意味の個数の組をもつ辞書があるので文字列 $W$ をパーティションしてそれぞれ辞書の要素に一致させたときの意味の個数を数え上げる

### 解法
実家

### 考察流れ
問題文を読む
考察：よくある 1 次元 DP を区間で埋めるやつ（合わせて2分）
実装：変数 $ij$ 混同する（5分）
MOD 取り忘れ 1 WA, 修正（1分）

### コメント
Copilotすげ～

if (i + t[j].size() <= s.size())

って書いたら勝手に Copilot が続きを書いてくれた

if (s.substr(i, t[j].size()) == t[j]) {
    DP[i + t[j].size()] += DP[i];
}

（ICPC の練習としてはよくない）

これってみれますか？
https://open.kattis.com/submissions/8102885
404: Not Found でした

ということは他のユーザの提出みる方法なさそう

ruthen71 の提出コード↓
https://github.com/ruthen71/submissions/tree/master/tpc/20211130
:thumbsup:

## E
### 問題概要
distinct な 2 つの数列の最長共通部分列を
もとめる

### 解法
DP 高速化

### 考察の流れ
LCS という概念を忘れていた（AtCoder ではほとんどでないだろ）
先頭から貪欲に対応付けると最後の位置を持つ DP ができる（$O(q^2)$）
MLE、そもそも間に合ってない
らて木と 2 分探索を使えば高速化できそう
終わり

### コメント
3 ペナ 40 分以上かかってかなしい GCJ でも使えるようにと即席で作った Case 出力マクロがバグってた やはり Case 出力は悪

らて木は区間 update ができない
RUMQ（遅延セグ木）は区間 combine ができない
両方できるデータ構造募集中です
あれ、これ Segment Tree Beats?

生配列一点更新でよいことにあとから気づいた

LISで解ける気がします(ruthen)

## F
### 問題概要
文字列をできるだけ繰り返しで縮約したときの長さをもとめる

### 解法
区間 DP $O(N^3\log N)$

### 考察の流れ
ネストできることをしらず、D と同じような DP をして値があわなかったため読み返した

ネストできるので再帰が確定、区間 DP で AC
$\sum_{i=1}^{x} \frac{x}{i} = O(x\log x)$ です

## 全体のコメント
提出をアーカイブしているのいいですね
↑コンテスト中に grep するために始めたんですが、あまり活用されていない……(ruthen)