Codeforces Round #641 Div. 2 E - Binary Subsequence Rotation
公式解説: Editorial — Codeforces Round #651 - Codeforces
問題概要
長さ $n (1 \leq n \leq 10^6)$ の 01 文字列 $s. t$ が与えられる。この文字列 $s$ に次の操作を繰り返し， $t$ と等しくする。
- 操作: $s$ の部分文字列を選び，右に回転させる。(1110100→1100110)
最低何回操作すれば良いか。
解法概要
まず前提として，$s$ と $t$ の $i$ 文字目をそれぞれ $s_i$, $t_i$ とすると，
- $s_i = 0$ かつ $t_i = 1$ となる $i$ の数
- $s_i = 1$ かつ $t_i = 0$ となる $i$ の数
は互いに等しくなければ，$s$ と $t$ を等しくすることはできない (出力がすべき値が $-1$ になる)。 以下はこの2つが等しいことを前提に考える。
1回の操作でできるだけ$s_i \neq t_i$ となる $i$ を減らすには，010101... (または 101010...) となるように $s$ の部分列を選び，その部分列について1回操作を適用すれば良い (この発想がすごい……本番で全く思いつかなかった)。 ここでは，$s_i = 0$ かつ $t_i = 1$ となる $i$ の数と$s_i = 1$ かつ $t_i = 0$ となる $i$ の数は等しいとしているので，1回の操作用の部分列 0 と 1 を同数ずつ採用している限りは片方が足りなくて 0101... (1010...) が作れないということはないはず。
したがって，$s_i \neq t_i$ となる $s_i$ が 0101... (1010...) という形の部分列いくつ分からできるかを計算すればよい。これは，$s_i$ を前から見ていき，$s_i \neq t_i$ のときに最後が 0 となる部分列の数と最後が 1 となる部分列の数をそれぞれ更新しながら数えれば良い。ソースコード参照。
ソースコード
#include <iostream> #include <vector> #include <string> using namespace std; int main() { int n; cin >> n; string s, t; cin >> s >> t; int s_cnt = 0, t_cnt = 0; for(int i=0;i<n;++i) { s_cnt += int(s[i] - '0'); t_cnt += int(t[i] - '0'); } if(s_cnt != t_cnt) { cout << -1 << endl; return 0; } vector<int> v(2, 0); // v[0]: 最後が 0 になる部分列の数, v[1]: 最後が 1 になる部分列の数 for(int i=0;i<n;++i) { if(s[i] == t[i]) continue; // 等しければ操作を適用する必要はない int j = int(s[i] - '0'); if(v[1-j]) { // 今見ている数字と異なる (= 0 と 1 を交互にするときに，今見ている数字を追加可能な) 文字列があるか？ --v[1-j]; ++v[j]; } else { ++v[j]; // 末尾に今見ている数字を追加可能な文字列がなければ，文字列を増やす } } cout << v[0]+v[1] << endl; }
所感
問題を見た瞬間にこれ無理なやつだと思ったんですが，後からやってみるとそうでもないし面白いですね。
AtCoder Grand Contest 044 B - Joker
問題: B - Joker
公式解説: 解説 pdf
問題概要
$N \times N$ の正方形の座席を持つ劇場に $N^2$ 人の客が座っている。客が席を立つ順番が与えられるので，以下を求めよ。
- 客が自席から外周へと出るまでに通る，人の座っている座席の数の，すべての客についての総和。
解法概要
愚直にシミュレートすると時間計算量が $O(N^4)$ となってしまい，間に合わない。しかし，最初の状態における各座席の客が外周に出るまでに通る席の数に着目すると，例えば $N = 6$ なら
000000 011110 012210 012210 011110 000000
である。もう少し正確に言うと，$N$ に対する「最初の状態における各座席の客が外周に出るまでに通る席の数」 (以降，「初期コスト」と表現する) の総和は $N$ が偶数なら $(N-2) ^2 + (N-4)^2 + \cdots + 2^2$ ，奇数なら $(N-2) ^2 + (N-4)^2 + \cdots + 1^2$ である。$\sum_{k=1}^n k^2 = \frac{1}{6} n(n+1)(2n+1)$ であることから，初期コストの総和も $O(n^3)$ で抑えられる。
ここから，ある客が席を立ったときに，その影響範囲の数のみ減らせるような解法であれば通りそうだと考えられる。
ある客が席を立ったときに，影響を受ける範囲でだけ数を減らすには，席を立った客の席から BFS や DFS でコスト (外周に出るまでに通る，人が座っている席の数) が減るような席について値を更新していけば良い。ある席でコストが削減できなかったときに，その先でもコスト削減はできていないはずなのでその先は見に行かなくていい。コストの更新はソースコード参照。まだ人が座っている席を通るたびに値を増やすイメージ。
ソースコード
#include <iostream> #include <algorithm> #include <vector> #include <queue> using namespace std; constexpr int dyx[4][2] = { { 0, 1}, {-1, 0}, {0,-1}, {1, 0} }; int main() { int n; cin >> n; auto f = [n](int y, int x) { return y * n + x; }; vector<int> p(n*n), cost(n*n, 0); vector<bool> sit(n*n, true); for(int i=0;i<n*n;++i) { cin >> p[i]; --p[i]; } for(int i=0;i<n*n;++i) { int y = i / n, x = i % n; cost[i] = min({y, n-1-y, x, n-1-x}); } int ans = 0LL; for(int i=0;i<n*n;++i) { ans += cost[p[i]]; queue<int> que; que.push(p[i]); sit[p[i]] = false; while(!que.empty()) { int j = que.front(); que.pop(); int y = j / n, x = j % n; for(int k=0;k<4;++k) { int yy = y + dyx[k][0], xx = x + dyx[k][1]; if(0 <= yy && yy < n && 0 <= xx && xx < n && cost[f(yy,xx)] > cost[f(y,x)] + int(sit[f(y,x)])) { cost[f(yy,xx)] = cost[f(y,x)] + int(sit[f(y,x)]); que.push(f(yy,xx)); } } } } cout << ans << endl; }
所感
解けてしまえば青 diff も納得なのだが，本番はまったくわからなかった。
それにしても，社会人になってから週1で解説記事を書く習慣が崩壊してるな。
AtCoder Beginner Contest 168 F - . (Single Dot)
公式解説: 解説 pdf
問題概要
無限に広がる平面上に $N (\leq 1000)$ 本の縦線と $M (\leq 1000)$ 本の横線がある。 縦線と横線の端点の座標の値は$-10^9$ 以上 $10^9$ 以下の範囲に収まる。
座標 $(0, 0)$ から動くことのできる範囲の面積を求めよ。
解法概要
座標の範囲が広いが，線の本数，つまり出てくる座標の種類数は多くない。 このような性質を持つ問題では，座標を圧縮したくなる。
座標圧縮とは，座標の数値を「出てくる値の中で何番目に小さいか」という順位で置き換えることで値の範囲を狭めるテクニックである。実装方法についてはここでは立ち入らないので，下記のソースコード やけんちょんさんのブログ記事などを参考に。
今回は $x$ 軸 $y$ 軸それぞれで出てくる値の数がせいぜい $3000 + 1$ 種類なので，座標圧縮することで以下のような行列を使って問題で与えられた平面を表すことができるようになる。
1111111111111111111 1111101111111111111 1111101111111111111 1111101111111011111 1111101111111011111 1000000000000000001 1111101111111011111 1111101110001011111 1111101110101011111 1111101000100000111 1111101011101011111 1111101000001011111 1111101111111011111 1110000000000000111 1111101111111011111 1111101111111011111 1111111111111011111 1111111111111011111 1111111111111111111
(Sample 1 の例。マス目とマス目の境界，またはマス目の中を両方1文字分の幅で扱っている。 0 は境界上かつ線が引かれていることであることを表し，1 はマス目または「境界上だが線が引かれていない場所」を意味する)
上のように入力を表すことができれば，後は BFS なり DFS なりを適用させれば良い。 なのでここからの目標は上のような行列を作ることである。
「線分と線分の間」と「線分上」を両方扱うので，目標となる行列のサイズは ($x$座標の値の種類数 $\times 2 + 1$) $\times$ ($y$座標の値の種類数 $ \times 2 + 1$) とすることができる。
また，座標圧縮後の座標の値を $0$ 始まりで $1$ 刻みに割り当てるとすると，座標圧縮後の座標と目標となる行列上の座標は，座標圧縮後の座標を $(x, y)$ とすると $(2\times x + 1, 2 \times y + 1)$ とすることができる。
この座標の値の対応に合わせて，目標の行列で線分上に対応している要素を 0 で塗っていく。
すると，ここで言う「目標となる行列」が完成。
しかしこの行列，圧縮前の値と値の間隔の情報が落ちてしまっている。例えば，$(1, 0)$ と $(10^9, 0)$ のような 2 つの座標が登場したとして，圧縮後には $(0, 0)$, $(1, 0)$ とかになってしまい，「両者の幅が $10^9-1$ もあった」という情報は落ちる。
これに対処するために，$x$ 座標方向の幅， $y$ 座標方向の幅をそれぞれ持っておく。例えば $x = x_1$ となる座標がマス目の境界に相当するなら幅を 0 にしておき，そうでないならその両側に対応する圧縮前の座標の差を幅としておけば良い。 また，添字が 0 または最大の行 (列) に関しては幅を無限大にしておく。無限大の幅のマスにもし移動することができたら，その地点で答えは INF である。本段落の話は，$y$ 座標についても同様。
こうすることで，BFS や DFS をするときに，今いる座標の「面積」$x$ 座標方向の幅と $y$ 座標方向の幅の積で求められる。BFS や DFS で動ける範囲全体を動き，動けたマスの面積の総和をとったものが答えになる。
ソースコード
#include <iostream> #include <vector> #include <algorithm> #include <queue> #include <map> #include <set> #include <tuple> using namespace std; using ll = long long; using Pii = pair<int, int>; constexpr int INF = 1 << 30; constexpr int dyx[4][2] = { { 0, 1}, {-1, 0}, {0,-1}, {1, 0} }; struct Segment { ll x1, x2, y1, y2; Segment(ll a, ll b, ll c, bool is_vertical) { if(is_vertical) { x1 = a; x2 = b; y1 = y2 = c; } else { x1 = x2 = a; y1 = b; y2 = c; } } }; int main() { int n, m; ll a, b, c; cin >> n >> m; vector<Segment> segs; set<ll> xs, ys; xs.insert(0); ys.insert(0); for(int i=0;i<n+m;++i) { cin >> a >> b >> c; segs.push_back(Segment(a, b, c, i < n)); xs.insert(segs.back().x1); xs.insert(segs.back().x2); ys.insert(segs.back().y1); ys.insert(segs.back().y2); } int nx = xs.size()*2+1, ny = ys.size()*2+1; map<ll, ll> mpx, mpy; // 圧縮後の座標への変換 vector<ll> widthx(nx, 0), widthy(ny, 0); // 変換後のフィールドでの各マスの幅 { int i = 0; ll prev = -INF; for(ll x: xs) { mpx[x] = i*2+1; widthx[i*2] = (prev == -INF) ? INF : (x - prev); prev = x; i++; } widthx[i*2] = INF; i = 0; prev = -INF; for(ll y: ys) { mpy[y] = i*2+1; widthy[i*2] = (prev == -INF) ? INF : (y - prev); prev = y; i++; } widthy[i*2] = INF; } vector<vector<bool>> matrix(nx, vector<bool>(ny, true)); // 変換後の草原 vector<vector<bool>> used(nx, vector<bool>(ny, false)); for(int i=0;i<n+m;++i) { // x と y のいずれかは単一の値しか取らないはず for(ll x=mpx[segs[i].x1];x<=mpx[segs[i].x2];++x) { for(ll y=mpy[segs[i].y1] ;y<=mpy[segs[i].y2] ;++y) { matrix[x][y] = false; } } } // 変換後の草原の上で BFS ll ans = 0LL; queue<Pii> que; que.emplace(mpx[0], mpy[0]); used[mpx[0]][mpy[0]] = true; { ll x, y; while(!que.empty()) { tie(x, y) = que.front(); que.pop(); if(widthx[x] == INF || widthy[y] == INF) { ans = -1; break; } ans += widthx[x] * widthy[y]; for(int k=0;k<4;++k) { ll xx = x + dyx[k][0], yy = y + dyx[k][1]; if(0 <= xx && xx < nx && 0 <= yy && yy < ny && !used[xx][yy] && matrix[xx][yy]) { que.emplace(xx, yy); used[xx][yy] = true; } } } } if(ans == -1) { cout << "INF" << endl; return 0; } cout << ans << endl; }
所感
ほどよく筋肉な問題で好き。コンテスト中に解きたかった。
