https://csacademy.com/contest/round-25/
0-Sum Array
N個の数列Aがある。
i番目だけ-1倍して数列の総和を取ると0になるような最小のiを求めよ。
無ければ"-1"
Suspect Interval
N個の全ての要素が異なる数列Xがある。
以下の性質を満たすA,Bの中で、B-A+1の最大値を答えよ。
- 1 ≦ A ≦ B ≦ 10^5
- 区間[A,B]に数列Xの要素がただ1つだけ含まれる
Rectangle Path
N行M列の盤面があり、0だと空、1だとブロックがある。
この盤面に横H縦Wの長方形のブロックが置いてあり、パズルの箱入り娘のようにスライドさせて、(Sr,Sc)から(Fr,Fc)に移動させる。
最短、何回のスライドで移動できるか。無理ならば"-1"
Min Ends Subsequence
N個の順列Aがある。
この順列の部分列の中で最初と最後の要素が他の要素よりも大きい数列を取り出す。
このような数列の要素数の最大は？
Zone Capture
N行M列の盤面があり、0は白、1は黒で着色されている。
この盤面のうち1マスを白から黒に着色できる。
この時、白の連結成分のうち、盤面の端に接していないものは黒に変化する（囲碁で碁石が取れる感覚）。
盤面全体で黒のマスを最大何個作れるか。
以下、解説
0-Sum Array
int N, A[1010]; //----------------------------------------------------------------------------------- int main() { cin >> N; rep(i, 0, N) scanf("%d", &A[i]); int sm = 0; rep(i, 0, N) sm += A[i]; rep(i, 0, N) { sm -= A[i]; if (sm == A[i]) { printf("%d\n", i + 1); return 0; } sm += A[i]; } printf("-1\n"); }
題意は「Aの総和-A[i]=A[i]となる最小のi」と言い換えることができる。
その為、予め総和をとっておき、題意を満たすかチェックすれば良い。
Suspect Interval
int N, A[101010]; //----------------------------------------------------------------------------------- int main() { cin >> N; rep(i, 0, N) scanf("%d", &A[i]); A[N] = 0; N++; A[N] = 100001; N++; sort(A, A + N); int ans = 0; rep(i, 1, N - 1) { ans = max(ans, A[i + 1] - 1 - (A[i - 1] + 1) + 1); } cout << ans << endl; }
数列Xはソートしておく。
X[i]の要素が含まれて、B-A+1が最大となるA,Bの組を貪欲に探していく。
X[i]が含まれて、B-A+1が最大なのは、[X[i-1]+1,X[i+1]-1]の区間である。
前と後ろに番兵として0と100001を置いておくと簡潔に書ける。
Rectangle Path
template<int VW, int VH> struct Ruisekiwa2D { int v[VH][VW]; void set(int x, int y, int c) { v[y][x] = c; } void build() { rep(y, 0, VH) rep(x, 0, VW) { if (0 < y) v[y][x] += v[y - 1][x]; if (0 < x) v[y][x] += v[y][x - 1]; if (0 < y && 0 < x) v[y][x] -= v[y - 1][x - 1]; } } int get(int sx, int sy, int tx, int ty) { assert(sx <= tx && sy <= ty); int rs = v[ty][tx]; if (0 < sx) rs -= v[ty][sx - 1]; if (0 < sy) rs -= v[sy - 1][tx]; if (0 < sx && 0 < sy) rs += v[sy - 1][sx - 1]; return rs; } }; //----------------------------------------------------------------------------------- int N, M, B[1010][1010], H, W, Sx, Sy, Fx, Fy; Ruisekiwa2D<1010, 1010> sum; int vis[1010][1010], dst[1010][1010]; int dx[4] = { 0, 1, 0, -1 }; int dy[4] = { -1, 0, 1, 0 }; int bfs() { rep(y, 0, N) rep(x, 0, M) sum.set(x, y, B[y][x]); sum.build(); queue<int> que; que.push(Sy * 1010 + Sx); vis[Sy][Sx] = 1; dst[Sy][Sx] = 0; while (!que.empty()) { int q = que.front(); que.pop(); int y = q / 1010; int x = q % 1010; if (Fx == x && Fy == y) return dst[y][x]; rep(i, 0, 4) { int xx = x + dx[i]; int yy = y + dy[i]; if (xx < 0 || M <= xx) continue; if (yy < 0 || N <= yy) continue; if (M <= xx + W - 1) continue; if (N <= yy + H - 1) continue; if (sum.get(xx, yy, xx + W - 1, yy + H - 1)) continue; if (vis[yy][xx]) continue; dst[yy][xx] = dst[y][x] + 1; vis[yy][xx] = 1; que.push(yy * 1010 + xx); } } return -1; } //----------------------------------------------------------------------------------- int main() { cin >> N >> M; rep(y, 0, N) rep(x, 0, M) scanf("%d", &B[y][x]); cin >> H >> W >> Sy >> Sx >> Fy >> Fx; Sy--; Sx--; Fy--; Fx--; printf("%d\n", bfs()); }
最短経路問題だが、辺のコストが全て1なのでダイクストラまでいかず、BFSをすればよい。
遷移は上下左右で、枠をはみ出さないかというチェックと盤面の箱に引っかからないかというチェックをする。
盤面の箱に引っかかるかのチェックは二次元累積和を使うとO(1)で処理できる。
paiza.hatenablog.com
Min Ends Subsequence
int N, A[101010]; //----------------------------------------------------------------------------------- int orderN3() { int ans = min(N, 2); rep(a, 0, N) rep(b, a + 1, N) { int cnt = 0; rep(i, a + 1, b) if (A[i] < min(A[a], A[b])) cnt++; ans = max(ans, cnt + 2); } return ans; } //----------------------------------------------------------------------------------- int orderN2() { int ans = min(N, 2); rep(x, 1, N + 1) { int L = 0; while (L < N) { if (x <= A[L]) break; L++; } int R = N - 1; while (0 <= R) { if (x <= A[R]) break; R--; } if (R <= L) continue; int cnt = 0; rep(i, L + 1, R) if (A[i] < x) cnt++; ans = max(ans, cnt + 2); } return ans; } //----------------------------------------------------------------------------------- int orderN1() { int ans = min(N, 2); int L = 0, R = N - 1; rep(x, 1, N + 1) { while (L < N) { if (x <= A[L]) break; L++; } while (0 <= R) { if (x <= A[R]) break; R--; } if (R <= L) break; int cnt = 0; int left = L; int right = N - 1 - R; cnt = (x - 1) - (left + right); ans = max(ans, cnt + 2); } return ans; } //----------------------------------------------------------------------------------- int main() { cin >> N; rep(i, 0, N) scanf("%d", &A[i]); printf("%d\n", orderN1()); }
公式解説通りの実装
O(N^3)実装(orderN3関数)
部分列の両端を全探索する方法。部分列の両端の列挙がO(N^2)で両端より小さい数のカウントにO(N)かかる。
O(N^2)実装(orderN2関数)
部分列の両端よりもそれ以外が小さいということなので、部分列の両端の数の下限を全探索する。
部分列の両端の数の下限をxとして、[1,N]で全探索。
つまり、両端がx以上で、それ以外がx未満である部分列を探していけば良いのだが、これは貪欲に取れる。
範囲が大きいほど、x未満である個数が増えるので、x以上である数は左から初めて現れる所L、右から初めて現れる所Rを探し、[L+1,R-1]の範囲でx未満の個数をカウントすれば良い。
O(N)実装(orderN1関数)
O(N^2)を良くしていくのだが、尺取り法的なテクニックを適用していく。
「L,Rの探索」と「x未満の数のカウント」をそれぞれ最適化していく。
まずxのとき範囲が[L,R]であると分かった場合、x+1の時の範囲はこの[L,R]の内部に含まれることが分かる。
つまり、Lの[0,L-1]部分とRの[R+1,N-1]部分のチェックは省略できるということ。
これはA[0,L-1] < xでA[R+1,N-1] < xであることを考えると自明。
なので、以前のL,Rを覚えておくことで、「L,Rの探索」は全体でならしO(N)で行える。
「x未満のカウント」はO(1)で行う方法がある。
まず、x未満の数は全体で(x-1)個ある。
そして、A[0,L-1]は全てx未満なので、左側ではL個x未満の数がある。
同様に、A[R+1, N-1]も全てx未満なので、右側では(N-1-R)個x未満の数がある。
よって、範囲内のx未満の数は(x-1)-L-(N-1-R)個と計算できる。
これでAC
Zone Capture
int N, M, B[1010][1010]; vector<int> G[1010101]; void add_edge(int a, int b) { G[a].push_back(b); G[b].push_back(a); } //----------------------------------------------------------------------------------- #define NV 1010101 int timer = 0, ord[NV], lowlink[NV], used[NV], sz[NV]; vector<int> art; int ans; void dfs(int v, int p = -1) { used[v] = true; ord[v] = lowlink[v] = timer++; sz[v] = 1; for (int to : G[v]) { if (to == p) continue; if (used[to]) lowlink[v] = min(lowlink[v], ord[to]); else { dfs(to, v); sz[v] += sz[to]; lowlink[v] = min(lowlink[v], lowlink[to]); if (lowlink[to] >= ord[v] && p != -1) { ans = max(ans, sz[to]); art.push_back(v); } } } } //----------------------------------------------------------------------------------- int main() { cin >> N >> M; rep(y, 0, N) rep(x, 0, M) scanf("%d", &B[y][x]); rep(y, 0, N) rep(x, 0, M) if (B[y][x] == 0) { if (x < M - 1) if (B[y][x + 1] == 0) add_edge(y * M + x, y * M + x + 1); if (y < N - 1) if (B[y + 1][x] == 0) add_edge(y * M + x, (y + 1) * M + x); } rep(y, 0, N) if (B[y][0] == 0) add_edge(y * M + 0, N * M); rep(y, 0, N) if (B[y][M - 1] == 0) add_edge(y * M + M - 1, N * M); rep(x, 1, M - 1) if (B[0][x] == 0) add_edge(x, N * M); rep(x, 1, M - 1) if (B[N - 1][x] == 0) add_edge((N - 1) * M + x, N * M); dfs(N*M); rep(y, 0, N) rep(x, 0, M) if (B[y][x] == 1) ans++; ans++; cout << ans << endl; }
関節点についての知識が無いと解答するのは難しい。参考文献はこのあたり。
http://www.npca.jp/works/magazine/2014_1/
http://kagamiz.hatenablog.com/entry/2013/10/05/005213
関節点とは、無向グラフの消すと全体が連結でなくなる頂点のこと。
白マスを黒にすると外から離れている白マスが黒くなるという条件は無向グラフで考えると非連結になるということに置き換えられる。
その為、関節点を黒にするとき離れている白マスの個数が高速に得られれば答えが求まる。
外側の頂点と特殊点との間に辺を貼っておき、特殊点からDFSをしていけば答えられる。
関節点を黒にするときに離れている白マスの個数は、その関節点の子の頂点の数と等しいので、それをDFSしながら、カウントして答える。
