初回 -> はじめに
ACL Beginner Contestに参加しました。
3完です！
D問題はコンテスト後に解きました。
| 問題 | 時間 | アルゴリズム | 実行時間 |
|---|---|---|---|
| A | 1min | - | 4ms |
| B | 1min | - | 7ms |
| C | 3min | Union-Find木 | 31ms |
| D | - | セグメント木 | 207ms |
まとめ
先にまとめを載せます。これ自体は最後に書いてます。
セグメント木についてこれまで避けていたのですが、ちょうどいい難易度でコンテストに出てきましたね。
これを機にしっかり勉強したので、その定着の意味でもこの記事を書きました。
(コンテストから時間がたっているのは勉強していたためです)
セグメント木を使うことで長さ$N$の範囲への一部の演算を $O(\ log\ N)$でできます。
A - Repeat ACL
int k;
cin >> k;
for(int i = 0; i < k; ++i) cout << "ACL";
"ACL"という文字列をk回出力すれば答えになります。
$1 \le k \le 5$ なので、計算量なども気にしなくていいですね。
B - Integer Preference
ll a, b, c, d;
cin >> a >> b >> c >> d;
cout << (max(a, c) <= min(b, d) ? "Yes" : "No");
2つの範囲が重複しているかを判定する問題ですね。
どちらかの左端がどちらかの右端よりも左側にあれば重複しています。
「どちらかの左端」はmax(a, c)
「どちらかの右端」はmin(b, d)で見ることができます。
制約が大きく、int型では足りないことに注意です。
似た問題をABC070-Bで解いていたのでラッキー問題でした。
C - Connect Cities
ll n, m, a, b;
cin >> n >> m;
UnionFind uf(n);
for(int i = 0; i < m; ++i)
{
cin >> a >> b;
a--; b--;
uf.unite(a, b);
}
cout << uf.root_num() - 1;
グラフで考える問題ですね。
グラフ上の連結成分(互いに連結な頂点の集合)の個数がわかれば、連結成分同士に辺をつなぐことで求める状態になります。
つまり、連結成分がいくつあるかを求める問題に帰着できますね。
これはUnion-Find木やDFSなどで解くことができます。
私はUnion-Find木で解きました。
AtCoder社の公式ライブラリにもDSU(Disjoint Set Union)という名前で用意されているのですが、私は自分で用意したものを使っています。
使ったUnion-Find木をこの記事の最後に載せているので、よろしければご覧ください。
D - Flat Subsequence
ll n, k;
cin >> n >> k;
init();
vector<ll> a(n);
for(int i = 0; i < n; ++i)
{
cin >> a[i];
}
for(int i = 0; i < n; ++i)
{
ll le = max(0LL, a[i] - k);
ll re = min(a[i] + k, 300000LL);
ll score = query(le, re + 1);
update(a[i], score + 1);
}
cout << query(0, N);
セグメント木の問題ですね。
これについて書きたくて記事にしました笑
セグメント木について
セグメント木というのは、数列のある範囲への演算を高速に実行できるデータ構造です。
この演算には和・積・最大値・最小値などが使えます。
(正確には数列がモノイドであることですが、競プロでは上の4つができると思っていれば大丈夫そうです)。
(モノイドは代数学の用語です。こちらがシンプルでわかりやすかったので、気になる方はご覧ください。)
セグメント木ができる操作は「数列の値の更新」と、「任意の範囲の演算結果を取得」です。
どちらも$O(\ log\ N)$です。
また、「任意の1要素を取得」を$O(1)$でできます。
例えば長さ$N$の数列全体の最大値を求めたいとき、通常なら$O(N)$かかります。
しかし、セグメント木で実装していた場合は$O(log\ N)$で計算することができます。
ただし準備に$O(N\ log\ N)$かかるので注意です。
(1回求めるだけなら通常通りの$O(N)$のほうが速いです。)
セグメント木は、このような最大値を$N$回求めるといった場合に使えます。
愚直にやれば$O(N^2)$かかるところを$O(N\ log\ N)$に抑えられます。つよい。
使ったセグメント木をこの記事の最後に載せているので、よろしければご覧ください。
個人的に、コメントにあるサイトがわかりやすかったです。
D問題について
この問題はDPですね。
dp[i][j] = i番目まで見たとき、末尾がjで終わる部分列の最大長
というDP配列を使いましょう。
ある値$A_i$から絶対値が$K$の範囲にある数値で終わる部分列のうち、最も長いものの後ろに$A_i$をくっつけます。
そうすると、$j = A_i$としてdp[i][j]を更新できます。
しかし、ここで問題なのが制約です。
数列の長さ $N = 3 \times 10^5$
値の取りうる範囲 $K = 3 \times 10^5$
に対して上のDPは空間量と計算量が $O(NK)$ です。メモリも速度もダメなので解けませんね......。
......となっていたのがコンテスト時の私です。
実は上の方針はあっています。
ここでするべきは、さらなる高速化です。
dp[i][j] = i番目まで見たとき、末尾がjで終わる部分列の最大長
としたときに、iをひとつ進めた時の配列がどのように更新されるかを考えます。
すると、dp[i][j]の1か所は変わるのですが他のK-1箇所は変わらないことがわかります。
つまり、dp[i-1][j]の値をそのままコピーする形になります。
また、最終的な答えを出すときもdp[N][0~K]の配列があれば答えがわかりますね。
(dp[0~N-1][...]には計算してきた過程が入っているのですが、答えを出すときには不要です。)
これはとてもとてもメモリの無駄遣いです。削減しましょう。
以上から、
dp[i] = 末尾がiで終わる部分列の最大長
とすればメモリは大丈夫なことがわかりました。
ですが、まだ計算量が $O(NK)$ です。困りました。
......ここで出てくるのがセグメント木です！
この計算過程では「ある値$A_i$から絶対値が$K$の範囲にある数値で終わる部分列のうち最も長いもの」を使いますね。
ここに「任意の範囲の最大値」が出てきます。セグメント木の出番です。
セグメント木を使うことで、「ある値$A_i$から絶対値が$K$の範囲にある数値で終わる部分列のうち最も長いもの」を $O(\ log\ K)$で求められます。
これにより、この問題の計算量は $O(N\ log\ K)$になります。
メモリ使用量も計算量も実現的なものになり、この問題が解けます。
以上です。ありがとうございました。
最後に、使用しているUnion-Find木とSegment木を貼っておきます。
Union-Find木
class UnionFind{
public:
vector<int> p; // 親
vector<int> rank; // サイズ・各集合の根のみ有効
UnionFind(int n){
p.resize(n, -1);
rank.resize(n, 1);
}
int root(int x){
if(p[x] == -1) return x;
else return p[x] = root(p[x]); // 深さを 1 にしている
}
void unite(int x, int y){
x = root(x); y = root(y);
if(x == y)return;
if(rank[x] > rank[y]) swap(x, y); // rankの小さいものを下につける
rank[y] += rank[x];
p[x] = y;
}
// グループの数
ll root_num() {
ll num = 0;
for(ll x : p) if (x < 0) num++;
return num;
}
//xが属すグループのサイズ
int size(int x){ return rank[root(x)]; }
bool same(int x, int y){ return (root(x) == root(y)); }
};
セグメント木
// Segment Tree
// https://www.creativ.xyz/segment-tree-entrance-999/
// 使用関数の引数は全て1-index
// =================== 問題ごとに設定 ====================
const int N = 1 << 22; // 葉の数、2の累乗数
const ll E = 0; // 演算での単位元
ll op(ll a, ll b) { return max(a, b); } // 使用する演算、可換
// =======================================================
ll node[N * 2 + 1];
void init(){
for(int i = 0; i < N * 2 + 1; ++i) node[i] = E;
}
ll get(int i) { return node[i + N - 1]; }
void update(int i, ll x){ // i 番目の葉の値を x に変える
i += N - 1; // i 番目の葉のノード番号
node[i] = x;
while (i > 0) {
i = (i - 1) / 2; // ノード i の親ノードの番号に変える
node[i] = op(node[i * 2 + 1], node[i * 2 + 2]); // 左右の子の min を計算しなおす
}
}
ll query(int a, int b, int k = 0, int l = 0, int r = N){
// [a, b) の区間に対するクエリについてノード k （区間 [l, r) 担当）が答える
if (r <= a || b <= l) return E; // 区間が被らない場合は単位元を返す
if (a <= l && r <= b) return node[k]; // ノード k の担当範囲がクエリ区間 [a, b) に完全に含まれる
// 一部だけ範囲が被る場合は左右の子に委託する
ll c1 = query(a, b, 2 * k + 1, l, (l + r) / 2); // 左の子に値を聞く
ll c2 = query(a, b, 2 * k + 2, (l + r) / 2, r); // 右の子に値を聞く
return op(c1, c2);
}