Educational Codeforces Round 92 (Rated for Div. 2) 感想

Dashboard - Educational Codeforces Round 92 (Rated for Div. 2) - Codeforces

ABCEの4完で 1850->1896 (+46)。結構上がったのでうれしい。

CをACした時点でフレンド内順位表を見ると、D で WA を連発している方がかなり多かった一方で、E は割とすんなり解かれていた。なので、Dを飛ばしてEを解いた。これが結果的に良かった。

A - LCM Problem

$\mathrm{LCM}(x, y) \ge \max (x, y) \gt l$ なので、 $\mathrm{LCM}(x, y) \le r$ とできるかだけを考えれば良い。

$x$ を固定したとき、どのように $y\ (\gt x)$ を選べば $\mathrm{LCM}(x, y)$ を最小にできるかを考えると、 $\mathrm{LCM}(x, y)$ はその定義から絶対に $x$ の倍数なので、 $y = 2x$ として $\mathrm{LCM}(x, y) = 2x$ とするのが最小。

だから、 $\mathrm{LCM}(x, y)$ は $x = l,\ y = 2l$ のとき最小値 $2l$ をとる。

よって、 $r \ge 2l$ なら $l, 2l$ 、そうでなければ、-1 を出力すればいい。

提出コード

リンク： http://codeforces.com/contest/1389/submission/88301413

void solve() {
    int Q;
    cin >> Q;
    while (Q--) {
        ll l, r;
        cin >> l >> r;
        if (r < l * 2) {
            prints()(-1, -1);
        }
        else {
            prints()(l, l * 2);
        }
    }
}

B - Array Walk

これむずかしい。

しばらく何も手を付けられなかったが、 $0 \le z \le \min(5, k)$ という怪しすぎる制約から DP の着想を得てなんとかACすることができた。

まず、DPによって

$dp[i][j] := 既に j 回左に移動する操作を行っていて i 番目にいるときの最大スコア$

を求める。最終的に到達する位置は左に移動する操作を行った操作の回数のみに依存して、その回数を $a$ とおくと、最終到達位置は $k - 2a +1$ となる。なので答えは $\displaystyle{ \mathrm{ans} = \max_{0 \le a \le z} dp[k - 2a + 1][a]}$ 。

提出コード

リンク：http://codeforces.com/contest/1389/submission/88329582

ll dp[100010][6];
 
void solve() {
    int Q;
    cin >> Q;
    Vl A;
    while (Q--) {
        ll N, K, Z;
        cin >> N >> K >> Z;
        A.resize(N);
        for (ll i = 0; i < N; i++) {
            cin >> A[i];
        }
        for (ll i = 0; i < N; i++) {
            for (ll j = 0; j <= Z; j++) {
                dp[i][j] = -L_INF;
            }
        }
        dp[0][0] = 0;
        for (ll i = 0; i < N; i++) {
            dp[i + 1][0] = dp[i][0] + A[i];
        }
        for (ll j = 1; j <= Z; j++) {
            for (ll i = 0; i < N - j; i++) {
                dp[i + 1][j] = max(dp[i][j] + A[i], dp[i + 1][j - 1] + A[i + 1] + A[i]);
            }
        }
        ll ans = 0;
        for (ll j = 0; j <= Z; j++) {
            if (K - j * 2 >= 0)
                ans = max(ans, dp[K - j * 2 + 1][j]);
        }
        prints()(ans);
    }
}

C - Good String

Bより簡単だと思う。good であるための必要十分条件は

$n$ が偶数のとき： $t_1 = t_3 = \cdots = t_{n-1}$ かつ $t_2 = t_4 = \cdots = t_n$
$n$ が奇数のとき： $t_1 = t_2 = \cdots t_n$

だから、最終的に残る数字は高々2種類しかない。その2文字を決め打ったときの、文字列を good にするために消去する必要のある文字数の最小値は簡単に求められるから、それを求めながら残す2文字を全探索すればいい。

提出コード

リンク： http://codeforces.com/contest/1389/submission/88344435

void solve() {
    int Q;
    cin >> Q;
    while (Q--) {
        string S;
        cin >> S;
        ll N = (ll)S.size();
        ll ans = L_INF;
        for (ll i = 0; i < 10; i++) {
            for (ll j = 0; j < 10; j++) {
                if (j == i) continue;
                bool is_left = true;
                ll cnt = 0;
                for (ll k = 0; k < N; k++) {
                    ll sk = S[k] - '0';
                    if (is_left) {
                        if (sk == i) {
                            is_left ^= true;
                        }
                        else {
                            ++cnt;
                        }
                    }
                    else {
                        if (sk == j) {
                            is_left ^= true;
                        }
                        else {
                            ++cnt;
                        }
                    }
                }
                if (!is_left) {
                    ++cnt;
                }
                ans = min(ans, cnt);
            }
        }
        for (ll i = 0; i < 10; i++) {
            ll cnt = 0;
            for (ll j = 0; j < N; j++) {
                ll sj = S[j] - '0';
                if (sj != i) {
                    ++cnt;
                }
            }
            ans = min(ans, cnt);
        }
        prints()(ans);
    }
}

D - Segment Intersections

Dを飛ばしてEを解き終わった時点で残り12分。さすがに時間が足りず解けなかった。

E - Calendar Ambiguity

個人的には B より簡単に感じた。

まず、x 月 y 日と y 月 x 日の両方が存在しないとだめなので、 $1 \le x \lt y \le \min(m, d)$ 。

また、 $w$ 日で構成される1週間について、前から $1$ 曜日、 $2$ 曜日、...、 $w-1$ 曜日、 $0$ 曜日と呼ぶことにすると、 x 月 y 日の曜日は $d(x-1) + y \bmod w$ と表せる。

よって、求めるのは下の2つの条件を共に満たす $(x, y)$ の個数。

$1 \le x \lt y \le \min(m, d)$
$d(x-1)+y \equiv d(y-1)+x \pmod w$

2番目の式を変形すると $(d-1)(x-y) \equiv 0 \pmod w$ であるから、 $d-1$ が $w$ の倍数かそうでないかで場合分けする。

$d-1$ が $w$ の倍数なら、 $(x, y)$ は1番目の条件を満たせばなんでもいいから、 $k = \min(m, d)$ とおいて、答えは $\mathrm{ans} = k(k-1) / 2$ 。

$d-1$ が $w$ の倍数でないとき、 $e = d - 1,\ g = \mathrm{gcd}(e, w),\ e^\prime = e/g,\ w^\prime = w/g$ とおくと、2番目の条件は $e^\prime (x-y) \equiv 0 \pmod{w^\prime}$ に変形できて、 $e^\prime$ と $w^\prime$ は互いに素だからこれを満たすための必要十分条件は $x- y \equiv 0 \pmod{w^\prime}$ 。

なので、結局 $x \equiv y \pmod{w^\prime}$ である $(x, y)$ の個数を求めればよくて、 $k = \min(m, d),\ q = \mathrm{floor}(k/w^\prime),\ r = k \bmod w^\prime$ とおくと、答えは $\mathrm{ans} = q(q-1)/2 \times (w^\prime - r) + q(q+1)/2 \times r$ 。

提出コード

リンク： http://codeforces.com/contest/1389/submission/88359610

void solve() {
    ll Q;
    cin >> Q;
    while (Q--) {
        ll M, D, W;
        cin >> M >> D >> W;
        if ((D - 1) % W == 0) {
            ll a = min(M, D);
            prints()(a * (a - 1) / 2);
        }
        else {
            ll g = gcd(D - 1, W);
            ll p = (D - 1) / g;
            ll q = W / g;
            ll a = min(M, D);
            ll b = a / q;
            ll c = a % q;
            ll ans = b * (b - 1) / 2 * (q - c) + b * (b + 1) / 2 * c;
            prints()(ans);
        }
    }
}

スコルの知恵袋

主にプログラミング関係の気になったこと等をまとめたブログ

Educational Codeforces Round 92 (Rated for Div. 2) 感想

A - LCM Problem

B - Array Walk

C - Good String

D - Segment Intersections

E - Calendar Ambiguity