ひさしぶりに Codeforces の過去問の練習をしました。A問題からC問題までは自力で解けましたがわりと手間取り、D/E は解けませんでした。
競プロ参戦記
この連載記事では、着手した問題の考察を自分なりに書いていきます。
- 問題の詳細はリンク先を参照してください。
- 筆者の回答は Rust (1.15.1) で書いています。
- 前回: 競プロ参戦記 #36 XOR World | ABC 121
Codeforces Round 545 Div.2
- 問題一覧: https://codeforces.com/contest/1138 (英語)
- 解説記事: https://codeforces.com/blog/entry/65825 (英語)
A. Sushi for Two
問題概要: 1 と 2 からなる長さ N の数列 A が与えられる。この数列の次の条件を満たす区間の長さの最大値を求めよ。
- 区間内に出現する 1, 2 の個数が等しい。
- 区間の前半と後半にはどちらも1種類の値だけ出現する。
考察 1
条件 1. から区間の長さは偶数なので「前半」と「後半」が曖昧さなく決まります。条件 2. は要するに、区間が次のような形をしているという意味です。
- 1, 1, .., 2, 2, ..
- 2, 2, .., 1, 1, ..
最長区間の列挙なので「しゃくとり」が脳裏をよぎりました。区間の前半の長さが後半の長さに依存するのでダメそうです。少なくとも解いているときはダメだと思いました。
答えが最大値を求めよという形をしているので二分探索で解けそうな予感がしました。実際、区間の長さ M (偶数) を決めたときに答えが M 以上かどうかは O(N) 時間で判定できます。全体として O(N log N) 時間で解けます。
判定は全探索では間に合わないので工夫が必要です。長さ M の区間をすべて列挙しつつ、その区間に含まれる 1, 2 のそれぞれの個数と、「連続して 1 (2) が出現している回数」を持っておきます。出現回数が両方 M/2 で、1 か 2 が連続して M/2 回出現している区間は条件を満たします。
筆者の回答 (Rust, AC): https://codeforces.com/contest/1138/submission/51117821
考察 2
見返してみると、同じ数が連続する個数に注目するともっと簡単に解けそうです。
まずバケツソートの逆をします。つまり、x が k 回連続して出現する区間を k に置き換えます。例えば 1, 1, 1, 2 は 3, 1 に、2, 1, 1, 1, 2 は 1, 3, 1 にします。
この数列で x, y が隣り合って並んでいるとき、長さ 2 * min(x, y) の条件を満たす区間が存在することが分かります。これをすべてのペアについて計算して max をとれば答えです。O(N) 時間。
筆者の回答 (Rust, AC): https://codeforces.com/contest/1138/submission/51337002
考察 2 の実装
実装にも触れます。このような「区間分割」は、「いまみている区間」の左端と右端のインデックス l, r を変数で持ち、r = N になるまでループを回すとシンプルに書けて良い感じです。
今回は「区間内のすべての値が等しい」という条件を満たすように区間を可能なかぎり右に伸ばして、伸ばせなくなったところで分割する、という手順です。つまり区間には少なくとも1つの要素が必要なので、l < r という条件を満たすように気をつけて区間の右端 r を伸ばしていきます。
let mut streaks = vec![];
let mut l = 0;
let mut r = 1;
while r <= N {
// 区間の右隣の要素が区間内の値に等しいなら、それも区間に含める。これを可能な限り繰り返す。
while r < N && A[l] == A[r] {
r += 1;
}
// l, r が数列の端か値が異なる要素の境界に位置しているので、区間 (l, r) を列挙する。
streaks.push(r - l);
l = r;
r = l + 1;
}
反省
上記の解説記事を読むとさらにシンプルでした。具体例を触って感覚をつかむのをすっぽかすとこういうことになりがち。
B. Circus
問題概要: N 人 (偶数) のパフォーマーがいる。i 番目のパフォーマーは、c[i] = 1 なら道化ができて、a[i] = 1 ならアクロバットができる。次の条件を満たすようにパフォーマーを N/2 人選ぶことができるか判定し、できるならパフォーマーの選びかたを1つ構成せよ。不可能なら -1 を出力せよ。
条件: 選ばれたパフォーマーのうち道化ができる人数と、選ばれなかったパフォーマーのうちアクロバットができる人数が等しい
考察:
「選ばれたパフォーマーのうち道化ができる人数」を C、「選ばれなかったパフォーマーのうちアクロバットができる人数」を A とします。N/2 人を選んで、最終的に C = A ならOK。
変数 S = A - C を考えます。条件 C = A の代わりに S = 0 を考えると変数が減って嬉しいです。
はじめ、誰も選んでいないので C = 0、A = (アクロバットができるパフォーマーの総数)、S = A です。パフォーマーを1人選ぶとき、変数 S の値はどう変化するか観察します。
- 「道化もアクロバットもできるパフォーマー」を選ぶと C が 1 増えて A が 1 減るので、S は 2 減ります。
- 「道化とアクロバットの片方だけができるパフォーマー」を選ぶと、 C が 1 増えるか A が 1 減るかのどちらかで、どちらにせよ S は 1 減ります。
- 「道化もアクロバットもできないパフォーマー」(おそらく他のパフォーマンスができる)を選ぶと、C も A も変化しないので S は変化しません。
パフォーマーをこの3種類に分類して数えるとき、「選ばれたパフォーマー」の人数が上から x, y, z 人とします。S = 0 であるためには、x, y, z が以下の条件を満たせばいいです。
- x + y + z = N/2
- S - 2x - y = 0
道化もアクロバットもできないパフォーマーを選ぶ人数である z を全探索すると連立方程式の解が最大1つになり、(x, y, z) の組み合わせとしてありえるものをすべて列挙できます。
筆者の回答 (Rust, AC): https://codeforces.com/contest/1138/submission/51119004
反省:
解説記事を読むと S = A - C という変換をかませなくても連立方程式に持ち込める模様です。
C. Skyscrapers
問題概要: 非負整数からなる N×M 行列 A が与えられる。y 行目と x 列目のすべての組み合わせについて 独立に 以下の操作と計算をする。y 行目に出現する要素を、大小関係を維持しながら減少させる。同時に、x 列目に出現する要素を、大小関係を維持しながら減少させる。この操作の後、y 行目と x 列目に出現する y + x - 1 個の要素の最大値としてありえる値の最小値を求めよ。
考察:
問題文中に出現する例を借りて説明すると、例えば y=2, x=3 として、2行目の値が 11, 13, 14, 15, 16、3列目の値が 10, 20, 14, 10 であるとします。ここで 14 は行と列の交差点に位置することに注意です。
操作の一方では、2行目の要素を減少させますが、大小関係が変化してはいけません。つまり1列目と2列目の 11 < 13 という大小関係は維持しないといけないので、1, 2, .. (1 < 2) はOKですが 2, 1, .. (2 >= 1) や 1, 1, .. (1 == 1) にはできません。
この場合の答えは、交差点の14を3にして、2行目を 1, 2, 3, 4, 5、3列目を 1, 4, 3, 1 にすることで最大値 4 とするのがベストです。
さて、要するに座標圧縮のようなものですが、交差点に位置する要素の値が共通なので、行と列を独立に座標圧縮してはいけません。そもそも N, M ≤ 1000 なので座標圧縮する時間はありません。(すべての (y, x) について計算しないといけないので、全体で O(N M (N + M)) 時間になってしまい TLE 必至。)
最大値を最小化するには、まず交差点の値が最小でなければいけません。交差点の値は、それより小さい要素の個数より小さくはできません。
逆にいえば、「交差点の値より小さい要素の個数」を行と列でそれぞれ計算して、その最大値 (+1) を操作後の交差点の値にできます。これは行と列を事前にソートしておけば二分探索によって実行できて、1操作あたり O(log N) 時間です。
交差点の値が求まったら、同様に最大値も「交差点以上の要素の個数」を二分探索で求めることによって、操作後の最大値も決定できます。
筆者の回答 (Rust, AC): https://codeforces.com/contest/1138/submission/51120901
lower_bound と upper_bound の良い練習になりました。
反省:
これはうまくいったみたいです。
D. Camp Schedule
問題概要: 0, 1 からなる文字列 S, T が与えられる。S の文字の順番を適当に並び替えるとき、T が S の部分文字列として出現する回数の最大値を求めよ。
考察:
これは自力では解けなかったので解説を読んで実装しました。
例えば S=1111000, T=101 のとき、S を 1010101 と並び替えれば T=101 は3回出現するので最大になります。ポイントは 101 の最後の 1 が2回目に出現する T の先頭の文字になっていることです。この「重なり」を最大化することで T の出現回数が最大になります。
一般化すると、T の前からの M 文字と後ろからの M 文字が一致するような最大の M について、T の前から M 文字を x、T の後ろから (|T| - M) 文字を y とするとき、S = x + y + y + .. という繰り返しの文字列を作ることで T の出現回数を最大化できます。いや、できそうです。証明してないので断言できない。
問題は最大の M を計算することです。これは Z Algorithm という名前がついている DP の一種を使うことで解けます。理解できたかは怪しいのでリンクだけ……
筆者の回答 (Rust, AC): https://codeforces.com/contest/1138/submission/51220447
今回の教訓
- A: 与えられたデータを必要な情報だけ抜き出したデータに変換すると、楽に解けるかも
- B: 1つの変数の値を全列挙すると、残りが簡単に解けるかも
- C: 二分探索を「数える」ことに使えるかも