###### tags: `Codeforces` `ログ` `解説記事` `競プロ` Educational Codeforces Round #46 === A. Codehorses T-shirts === [問題リンク](http://codeforces.com/contest/1000/problem/A) ## 概要 服のサイズに関するデータが$N$個セットで2つ与えられる。 服のサイズは * `M`のみ * `X`が$0 \sim 3$個続いたあとで`S`か`L` という計9種類の文字列によって表される。 一方のデータセットを、データの一部の文字を書き換えることでもう一方のデータセットに一致させるとき、書き換える必要のある最小の文字数を求めよ。 ただし各入力について、文字を消したり追加することなく2つのデータセットを一致させられることが保証されている。 ## 制約 * $1 \leq N \leq 100$ ## 解説 例によって問題文がとても読みづらい。というか導入が長い。 まぁその中から必要な情報をすばやく汲み取るのも一種のスキルなのかもしれないが。 本題に戻ろう。まず書き換えるべき文字は`SML`の三種のみで、`X`を書き換える必要は一切ない。さらに前についている`X`の数が同じものにのみ書き換えられるので、`X`の数と`SML`でふるい分けすればあとは各要素数を比較するだけ。 ## 回答例 ```cpp= 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 === [問題リンク](http://codeforces.com/contest/1000/problem/B) ## 概要 要素数$N$の狭義単調増加列$a_i(0 < a_1 < a_2 < \dots < a_N < M)$がある。 ここにランプがあり、時刻$0$に点灯後、各$i$について時刻$a_i$にオンオフが入れ替わって、時刻$M$で状態にかかわらず消灯する。  さて、あなたは上の条件を満たし続けるように数列$a_i$に値を**高々1つ**挿入できる。このとき、ランプの点灯時間の最大値を求めよ。 図解するとこういうこと。 ![](https://i.imgur.com/CRQtsGR.png) ## 制約 * $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$の場合は?」というのは至極真っ当な疑問で、このケースは値を挿入できないので省くべきである。[^seg1] [^seg1]: 本番ではそのケースも統一的に扱うコードを提出したのだが、なぜか通ってしまった。おそらく前後の区間に値を挿入するケースに吸収されたと考えられる。 ## 回答例 ```cpp= 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 === [問題リンク](http://codeforces.com/contest/1000/problem/C) ## 概要 $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法を使え」と言わんばかりのテーマだからね[^whatimos]。 [^whatimos]: ここではimos法の説明はしない。[いもす研HP](https://imoz.jp/algorithms/imos_method.html)に詳しく説明されているので、これを読めば私が想定している解法がなんとなく分かるだろう。 じゃあ例によって区間の始点と終点の要素をイジって...ってとこで$l, r$の制約がデカすぎることに気づく。空間も時間もまるで足りない。 一昔前の私ならここで諦めていたが、今は違う。区間がデカすぎるなら**圧縮すればいいじゃない**。というわけで「区間の端点を**座標圧縮**して十分記録できるサイズにして、それからimos法を適用する」というのが私の方針だった。正直座圧はそれほど慣れていなかったので不安があったが、通ったので良し。 ただ1つ注意することとして、imos法を使うときは区間を半開区間として扱う必要がある。閉区間$[l, r]$全体に1を加算するとき、imos法では ```cpp= imos[l]++; imos[r + 1]--; ``` という形の処理を行う。2行目で`r+1`としてるのが重要。なんとも説明しづらいが、要は閉区間$[l, r]$の$r$をこのまま扱って座圧すると上手くいかないよって話。$r+1$に変えておこう。 ## 回答例 ```cpp= 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](http://codeforces.com/blog/entry/60288)と九割方同じ方針だった。Editorial中では文で事細かに説明されているが、あれだけ汎用的なアルゴリズムにグローバルな名前がついていないのが不思議。 他の解法として「区間の端点をソートして頭から順に見ていく」というのも考えられる。実装は出来てないので机上の空論だが、どうなんだろう。 D. Yet Another Problem On a Subsequence === [問題リンク](http://codeforces.com/contest/1000/problem/D) ## 概要 $a_1 > 0$かつ長さが$a_1+1$であるような数列$a_i$を**good array**と呼ぶことにする。 例えば$[3, 3, -4, 0]$は$a_1=3$で長さ4なのでgood arrayである。 さらに、数列のうち1つ以上のgood arrayに分割できるようなものを**good sequence**[^badname]と呼ぶことにする。 [^badname]: good arrayとgood sequence、和訳するとどっちも「良い数列」になってしまうので諦めてそのままにした。コンテスト中も最初はこんがらがってしまって何がなんだかという状態だったり。 長さ$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を作るとすると、総パターン数は以下のように求められる。 ![](https://i.imgur.com/OPVZyGj.jpg) つまり $$ {}_{L-1} C_{a_i-1} \times (rec(i + L + 1) + 1) $$ 通りである。これを$a_i \leq L$かつ$i+L < N$の範囲の$L$で全て足せば、使う場合の総パターン数が求まる。 あと再帰回数がエゲツないため、ちゃんとメモして高速化しないとTLEになるので注意。 ## 回答例 随分長いけどうち40行はライブラリが原因なので、そこは読み飛ばしていただくと良いかと。 ```cpp= 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年まで上がった。早く現代になりたい。