Mister雑記

競プロやります。

Educational Codeforces Round #46

MacbookProの以前から若干イカレ気味だったreturnキーより先に、なぜか予告なくxキーが死んでしまいました。Misterです。

文字が消せないし何よりtmuxが起動できません。外付けキーボード買うか...。

何はともあれえでゅこんの解説です。今回は現実世界での実装が重かったセットでした。解説は私が本番中に通せたA~Dの4問まで。

HackMD版はこちら

目次

本編

A. Codehorses T-shirts

問題リンク

概要

服のサイズに関するデータが N個セットで2つ与えられる。

服のサイズは

  • Mのみ
  • X 0 \sim 3個続いたあとでSL

という計9種類の文字列によって表される。

一方のデータセットを、データの一部の文字を書き換えることでもう一方のデータセットに一致させるとき、書き換える必要のある最小の文字数を求めよ。

ただし各入力について、文字を消したり追加することなく2つのデータセットを一致させられることが保証されている。

制約

  •  1 \leq N \leq 100

解説

例によって問題文がとても読みづらい。というか導入が長い。 まぁその中から必要な情報をすばやく汲み取るのも一種のスキルなのかもしれないが。

本題に戻ろう。まず書き換えるべき文字はSMLの三種のみで、Xを書き換える必要は一切ない。さらに前についているXの数が同じものにのみ書き換えられるので、Xの数とSMLでふるい分けすればあとは各要素数を比較するだけ。

回答例

using namespace std;

template <typename T>
using V = vector<T>;

#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
// Usual REP runs from 0 to n-1 (R: n-1 to 0)

/* ---------- ここまでマクロ ----------- */

int main() {
    const string sml = "SML";
    
    int N;
    cin >> N;
    V<V<V<int>>> cnt(2, V<V<int>>(4, V<int>(3, 0)));
    // cnt[k][i][j]
    // = k番目のセット中で、Xがi個ついていて接尾語がsml[j]のものの数

    REP(k, 2) {
        REP(_, N) {
            string S;
            cin >> S;
            
            // ここからSをふるいにかける
            REP(i, 3) {
                if (sml[i] == S.back()) {
                    cnt[k][SIZE(S) - 1][i]++;
                    // 文字列の長さでXの個数
                    // 最初に定義したsmlで接尾語を判定
                }
            }
        }
    }

    int ans = 0;
    REP(i, 4) {
        REP(j, 3) {
            ans += abs(cnt[0][i][j] - cnt[1][i][j]);
            // はみ出ている分(?)を書き換える必要がある
            // この時点では2回分重複してカウントしていることに注意
        }
    }

    cout << ans / 2 << endl;
    // 重複してカウントした分2で割る
    return 0;
}

工場の製造ラインで、商品をサイズ別に分ける機械に似ている気がする。

問題自体は簡単なのだが、実装が怠いタイプの問題。 ま、今回のセットの中では実装は軽いほうなのだが。

B. Light It Up

問題リンク

概要

素数  Nの狭義単調増加列  a_i (  0 \lt a_1 \lt a_2 \lt \dots \lt a_N \lt M )がある。

ここにランプがあり、時刻0に点灯後、各  iについて時刻  a_iにオンオフが入れ替わって、時刻  Mで状態にかかわらず消灯する。

さて、あなたは上の条件を満たし続けるように数列 a_iに値を高々1つ挿入できる。このとき、ランプの点灯時間の最大値を求めよ。

図解するとこういうこと。

f:id:misteer:20180630111919p:plain

制約

  •  1 \leq N \leq 10^{5}
  •  2 \leq M \leq 10^{9}

解説

以降、便宜上 a_0 = 0, a_{N+1} = Mとする。

挿入しない場合

まず、何も挿入しない場合について考える。 時刻 a_i時点での総点灯時間を s_iとすると、これは累積和DPで求まる。具体的には iが奇数のときだけ a_i - a_{i-1}を足していけばいい。

これにより、値を何も挿入しない場合の総点灯時間は s_{N+1}で求まる。これが答えの下限である。

挿入する場合

次に、値を挿入していく場合を考える。

例えば a_i a_{i + 1}の間に新しい値を挿入するとする。このときの最長点灯時間を求めよう。

  • 区間 [0, a_i]では上の何も挿入しない場合と点灯時間は同じで、 s_iで求まる。

  • 区間 [a_{i+1},M]では全体のオンオフが切り替わることになる。区間の長さは M - a_{i+1}、元の点灯時間は s_{N+1} - s_{i+1}なので、反転した場合の点灯時間は(M - a_{i+1}) - (s_{N+1} - s_{i+1})となる。

  • 区間 [a_i, a_{i+1}]。もし a_iでオンになった場合は、極力長引かせた後 a_{i+1} - 1でオフ。 逆に a_iでオフになった場合は、即 a_i+1でオンにするのが最も効率的となる。このとき、点灯時間はどちらのケースも a_{i+1} - a_i - 1で与えられる。

以上より、この場合の最長点灯時間は 
s_i + (M - a_{i+1}) - (s_{N+1} - s_{i+1}) + (a_{i+1} - a_i - 1)
となる。これを全ての i \in [0, N]で網羅して最大値を更新すればよい。

ここで「 a_{i+1} - a_i = 1の場合は?」というのは至極真っ当な疑問で、このケースは値を挿入できないので省くべきである。1

回答例

using namespace std;

template <typename T>
using V = vector<T>;
using ll = long long;

#define FOR(i, a, b) for (ll i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define NREP(i, n) FOR(i, 1, n + 1)
// Usual REP runs from 0 to n-1 (R: n-1 to 0)
// Natural REP runs from 1 to n

/* ---------- ここまでマクロ ----------- */

int main() {
    ll N, M;
    cin >> N >> M;

    V<ll> a(N + 2);
    a[0] = 0;
    NREP(i, N) {
        cin >> a[i];
    }
    a[N + 1] = M;

    V<ll> sum(N + 2, 0);
    // 挿入しないときの点灯時間

    NREP(i, N + 1) {
        sum[i] = sum[i - 1];
        if (i % 2 == 1) {
            sum[i] += a[i] - a[i - 1];
        }
    }

    ll ans = sum[N + 1];

    REP(i, N + 1) {
        // 区間長が1なら挿入できないのでスルー
        if (a[i + 1] - a[i] == 1) continue;
        
        // a[i]とa[i - 1]の間に挿入したときの点灯時間
        ll t = 0;
        
        t += sum[i];
        t += (M - a[i + 1]) - (sum[N + 1] - sum[i + 1]);
        t += a[i + 1] - a[i] - 1;

        ans = max(ans, t);
    }

    cout << ans << endl;
    return 0;
}

ただの累積和DPなのだが、実装というより計算が重い。本番では上のように筋道立てて式を導出していなかったので頭が割れるかと思った。メモ媒体の使用、大事。

C. Covered Points Count

問題リンク

概要

 N個の区間 [l_i, r_i]が与えられる(両端を含み l_i = r_iになることもある)。 このとき、各 k = 1,2, \dots ,Nについて、丁度 k個の区間で覆われている頂点の数を出力せよ。

制約

  •  1 \leq N \leq 2 \cdot 10^{5}
  •  0 \leq l_i \leq r_i \leq 10^{18}

解説

問題がとてもシンプルで好き。でも実装は重い。

まず問題文からぱっと出たのが「imos法」による解法。内容が「imos法を使え」と言わんばかりのテーマだからね2

じゃあ例によって区間の始点と終点の要素をイジって...ってとこで l, rの制約がデカすぎることに気づく。空間も時間もまるで足りない。

一昔前の私ならここで諦めていたが、今は違う。区間がデカすぎるなら圧縮すればいいじゃない。というわけで「区間の端点を座標圧縮して十分記録できるサイズにして、それからimos法を適用する」というのが私の方針だった。正直座圧はそれほど慣れていなかったので不安があったが、通ったので良し。

ただ1つ注意することとして、imos法を使うときは区間を半開区間として扱う必要がある。閉区間 [l, r]全体に1を加算するとき、imos法では

imos[l]++;
imos[r + 1]--;

という形の処理を行うのだが、2行目でr+1としてるのが重要。なんとも説明しづらいが、要は閉区間 [l, r]の rをこのまま扱って座圧すると上手くいかないよって話。 r+1に変えておこう。

回答例

using namespace std;

template <typename T>
using V = vector<T>;
template <typename T, typename U>
using P = pair<T, U>;
template <typename T>
using ll = long long;

#define fst first
#define snd second
#define pb push_back

#define LL(n) static_cast<ll>(n)

#define ALL(v) (v).begin(), (v).end()
#define SIZE(v) (LL((v).size()))
#define SORT(v) sort(ALL(v))

#define FOR(i, a, b) for (ll i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define NREP(i, n) FOR(i, 1, n + 1)
// Usual REP runs from 0 to n-1
// Natural REP runs from 1 to n

/* ---------- ここまでマクロ ---------- */

// 与えられた区間の両端を全部まとめて圧縮する
V<ll> compress(const V<P<ll, ll>>& seg) {
    V<ll> val;
    
    // 1.値を全部突っ込む
    for (auto p : seg) {
        val.pb(p.fst);
        val.pb(p.snd);
    }

    // 2.sortする
    SORT(val);
    
    // 3.被りを消す
    // 以下の文はイディオムみたいなもの
    val.erase(unique(ALL(val)), val.end());
    
    // 4.被りのなくなったものを配列として返す
    return val;
}


int main() {
    ll N;
    cin >> N;
    
    V<P<ll, ll>> seg(N);
    REP(i, N) {
        cin >> seg[i].fst >> seg[i].snd;
        seg[i].snd++;
        // ここで閉区間を半開区間に変えている
    }

    // 区間の端点を圧縮したものを受け取る
    V<ll> com = compress(seg);
    ll M = SIZE(com);

    map<ll, ll> mp;
    // comの各要素がcom内でどこにあるかを記録
    
    REP(i, M) {
        mp[com[i]] = i;
    }

    V<ll> imos(M + 1);
    // imos[i] = [com[i], com[i+1])を覆う区間の数
    
    // 1. 差分をカウント
    for (auto p : seg) {
        imos[mp[p.fst]]++;
        imos[mp[p.snd]]--;
    }

    // 2. 累積和で集計
    NREP(i, M) {
        imos[i] = imos[i - 1] + imos[i];
    }

    V<ll> ans(N + 1, 0);
    
    // 3. 答えをカウント
    REP(i, M) {
        ans[imos[i]] += com[i + 1] - com[i];
    }

    NREP(k, N) {
        cout << ans[k] << " ";
    }
    cout << endl;
    return 0;
}

ちなみにこの解法、Editorialと九割方同じ方針だった。 Editorial中では文で事細かに説明されているが、あれだけ汎用的なアルゴリズムにグローバルな名前がついていないのが不思議。

他の解法として「区間の端点をソートして頭から順に見ていく」というのも考えられる。実装は出来てないので机上の空論だが、どうなんだろう。

D. Yet Another Problem On a Subsequence

問題リンク

概要

 a_1 > 0かつ長さが a_1+1であるような数列 a_igood arrayと呼ぶことにする。 例えば [3, 3, -4, 0]は a_1=3で長さ4なのでgood arrayである。

さらに、数列のうち1つ以上のgood arrayに分割できるようなものをgood sequence3と呼ぶことにする。

長さ Nの数列 a_iが与えられるので、その部分列(連続でなくていい)でgood sequenceであるものの個数を 998244353 (素数)で割った余りを求めよ。

ただし、要素が全て同じ部分列同士であっても、元の数列の異なるindexから取ってきた要素が1つでも存在する場合は別としてカウントする。

制約

  •  1 \leq N \leq 10^{3}
  • -10^{9} \leq a_i \leq 10^{9}

解説

第一成分と長さだけで定義された、少し変わった数列に関する問題。裏を返せば第一成分以外は全部無視できるので扱いやすいとも言える。

ではどうやって考えていくかというと、頭から要素を見ていって「この要素をgood sequencesに入れるか?」を試していくのが一番シンプルだろう。

そこで、「 i文字目以降の部分列から、いくつのgood sequencesを作れるか」を計算する関数を rec(i)としよう。ちなみに iは0-indexedとする。明らかに i \geq Nにて rec(i) = 0である。

使わない場合

まず i文字目を使わない場合。少し考えれば分かるが、この場合の総パターン数は rec(i + 1)で求まる。それはそう。

 a_i \leq 0の場合はこっちだけ考えればいい。

使う場合

本題はこっちで、この場合はgood arrayの定義から i+1文字目以降から a_i文字取ってくる必要がある。good sequencesを作るとき、部分列は連続してなくてもいいことに注意。

 a_iを先頭として長さ Lのgood arrayを作るとすると、総パターン数は以下のように求められる。

f:id:misteer:20180630112829j:plain

つまり 
{}_{L-1} C_{a_i-1} \times (rec(i + L + 1) + 1)
通りである。これを a_i \leq Lかつ i+L \lt N の範囲の Lで全て足せば、使う場合の総パターン数が求まる。

あと再帰回数がエゲツないため、ちゃんとメモして高速化しないとTLEになるので注意。

回答例

随分長いけど内40行はライブラリが原因なので、そこは読み飛ばしていただくと良いかと。

using namespace std;

template <typename T>
using V = vector<T>;
using ll = long long;

#define FOR(i, a, b) for (ll i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define NREP(i, n) FOR(i, 1, n + 1)
// Usual REP runs from 0 to n-1
// Natural REP runs from 1 to n

/* ---------- ここまでマクロ ----------- */

/* ---------- ここから二項係数ライブラリ ---------- */

const ll MOD = 998244353;
const ll MAX_V = 10000;

V<ll> fact(MAX_V + 1), invfact(MAX_V + 1);
// 階乗とその逆元

// 繰り返し二乗法でn^kを計算
ll calc_pow(ll n, ll k) {
    if (k == 0) return 1;
    if (k == 1) return n;

    if (k % 2 > 0) {
        return calc_pow(n, k - 1) * n % MOD;
    } else {
        return calc_pow(n * n % MOD, k / 2);
    }
}

// 事前呼び出しで階乗と逆元のテーブルを埋める
void precalc() {
    invfact[0] = fact[0] = 1;
    NREP(i, MAX_V) {
        fact[i] = fact[i - 1] * i % MOD;
    }

    invfact[MAX_V] = calc_pow(fact[MAX_V], MOD - 2);
    RREP(i, MAX_V) {
        invfact[i] = invfact[i + 1] * (i + 1) % MOD;
    }
    return;
}

// aCbを計算
ll comb(ll a, ll b) {
    if (a < b) return 0;
    if (a == 0) return 1;  // a = b = 0

    return fact[a] * invfact[a - b] % MOD * invfact[b] % MOD;
}

/* ---------- ここまで二項係数ライブラリ ---------- */

ll N;
V<ll> a(1010);
// 入力受け取り

V<ll> dp(1010, -1);
// メモ化再帰用 メモされていなければ-1

// i文字目以降での総パターン数を返す
ll rec(ll i) {

    // 終端判定
    if (i >= N) return 0;
    
    // 計算済みならメモを使う
    if (dp[i] >= 0) return dp[i];

    ll ans = 0;

    if (a[i] > 0 && a[i] < N) {
        // a[i]を使う場合
        NREP(l, N) {
            if (i + l + 1 > N) break;
            
            // l<a[i]では二項係数が0になるのでカウントされない
            ans += comb(l - 1, a[i] - 1) * (rec(i + l + 1) + 1) % MOD;
            ans %= MOD;
        }
    }

    // a[i]を使わない場合
    ans += rec(i + 1);
    ans %= MOD;

    // 計算結果をメモ
    dp[i] = ans;
    
    return dp[i];
}

int main() {
    precalc();
    // 階乗と逆元を全部計算する

    cin >> N;
    REP(i, N) {
        cin >> a[i];
    }

    ll ans = rec(0);

    cout << ans << endl;
    return 0;
}

mod問題ということで、お手製ライブラリのお披露目となった。ペーストするだけで勝手に計算してくれるので楽。しばしばprecalcを呼び忘れる。

わざわざ演算後にmodで剰余取るのがめんどくさいし何度かバグってるので、専用のクラスとか作りたいな〜とか思ったり思わなかったり。

感想

今回のセットはコンテスト中は「実装めっちゃ重いな〜」と思っていたが、振り返ってみると「もっとちゃんと紙に書けばそれほど混乱せずに済んだのでは?」という感じがしている。現実世界でのメモの大切さを思い知った。今後はもっとキレイにメモを書こう。

ちなみに今回解けなかった残りの3問だが、E問題は「強連結成分潰すんだろうな〜」と思いながら潰し方を知らなかったので断念。F問題は愚直なTLE解しか分からず。G問題はにゃーんって感じ。まだまだだね。

ちなみにレートは昭和61年まで上がった。早く現代になりたい。


  1. 本番ではそのケースも統一的に扱うコードを提出したのだが、なぜか通ってしまった。おそらく前後の区間に値を挿入するケースに吸収されたと考えられる。

  2. ここではimos法の説明はしない。いもす研HPに詳しく説明されているので、これを読めば私が想定している解法がなんとなく分かるだろう。

  3. good arrayとgood sequence、和訳するとどっちも「良い数列」になってしまうので諦めてそのままにした。コンテスト中も最初はこんがらがってしまって何がなんだかという状態だったり。