Codeforces Round #403 (Div. 2)

本番ではAしか通らなかった。反省。それ以外はEditorialを読みながら解く。

A

Problem - 782A - Codeforces

#include <bits/stdc++.h>
 
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);++i)
typedef long long int ll;
using namespace std;

int main(void) {
    int n;
    cin >> n;
    vector<int> x(n, 0);
    int count = 0;
    int ans = 0;
    int t;
    REP(i, 2*n) {
        cin >> t;
        t--;
        if(x[t]==1) {
            x[t] = 0;
            count--;
        } else {
            count++;
            ans = max(ans, count);
            x[t] = 1;
        }
    }
    cout << ans << endl;
}

B

Problem - B - Codeforces

#include <bits/stdc++.h>
 
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);++i)
typedef long long int ll;
using namespace std;

int main(void) {
    int n;
    cin >> n;
    vector<int> x(n), v(n);
    REP(i, n) cin >> x[i];
    REP(i, n) cin >> v[i];
    

    double lb = 0, ub = 1e9;;
    for(int i=0; i<100; ++i) {
        double t = (lb + ub) / 2.0;
        double L = -numeric_limits<double>::max();
        double R = numeric_limits<double>::max();
        REP(i, n) {
            L = max(x[i] - t * v[i], L);
            R = min(x[i] + t * v[i], R);
        }
        if(L <= R) ub = t;
        else lb = t;
    }
    printf("%.10f\n", lb);
}
  • 二分探索は探索回数で抑えるべき。

C

Problem - A - Codeforces (div1ではA問題）

#include <bits/stdc++.h>
 
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);++i)
typedef long long int ll;
using namespace std;

vector<vector<int>> G;
vector<int> C;
vector<set<int>> ban;
int ans = 1;

void dfs(int v, int c, int p) {
    C[v] = c;
    int t = 0;
    for(auto i : G[v]) {
        if(C[i] == -1) {
            do {t++;} while(t==c || t==p);
            dfs(i, t, c);
        }
    }
    ans = max(t, ans);
}

int main(void) {
    int n;
    scanf("%d", &n);
    G.resize(n);
    C.resize(n, -1);
    ban.resize(n);
    REP(i, n-1) {
        int x, y;
        scanf("%d %d", &x, &y);
        x--; y--;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    dfs(0, 1, -1);
    cout << ans << endl;
    cout << C[0];
    for(int i=1; i<n; ++i) printf(" %d", C[i]);
    printf("\n");
}
  • 方針は合っていたみたいだが実装が良くなかった。反省。

ABC 008

abc008.contest.atcoder.jp

A問題

#include <bits/stdc++.h>
 
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
#define RREP(i,n) for(int i=(int)(n); i>=0; --i)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);++i)
typedef long long int ll;
using namespace std;
 
int main(void) {
    int S, T;
    cin >> S >> T;
    cout << T-S+1 << endl;
}

Submission #1025991 - AtCoder Beginner Contest 008 | AtCoder

B問題

#include <bits/stdc++.h>
 
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
#define RREP(i,n) for(int i=(int)(n); i>=0; --i)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);++i)
typedef long long int ll;
using namespace std;
 
int main(void) {
    int N;
    cin >> N;
    map<string, int> S;
    REP(i, N) {
        string s;
        cin >> s;
        S[s]++;
    }
    string name;
    int ans = 0;
    for(map<string, int>::iterator it = S.begin(); it != S.end(); ++it) {
        if(it->second > ans) {
            ans = it->second;
            name = it->first;
        }
    }
    cout << name << endl;
}

Submission #1026002 - AtCoder Beginner Contest 008 | AtCoder

C問題

C問題とは思えない難易度。解説を見てその通りに実装した

#include <bits/stdc++.h>
 
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
#define RREP(i,n) for(int i=(int)(n); i>=0; --i)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);++i)
typedef long long int ll;
using namespace std;

int main(void) {
    int N;
    cin >> N;
    vector<int> C(N);
    REP(i, N) cin >> C[i];
    double ans = 0;
    REP(i, N) {
        int S = 0;
        REP(j, N) {
            if(i != j && C[i] % C[j] == 0) S++;
        }
        if(S%2 == 1) ans += 0.5;
        else ans += double(S+2.0)/(2.0*S+2.0);
    }
    printf("%.10f\n", ans);
}

Submission #1030429 - AtCoder Beginner Contest 008 | AtCoder

D問題

領域内にある採掘機全てについて、「その採掘機で取れる金塊+残りの長方形4つについての最大金塊数」の最大値を求める関数を作ってメモ化再帰。 座標圧縮のためにtupleを使った。

#include <bits/stdc++.h>
#include <tuple>
 
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
#define RREP(i,n) for(int i=(int)(n); i>=0; --i)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);++i)
typedef long long int ll;
using namespace std;
 
int W, H;
int N;
int X[81], Y[81];
 
typedef tuple<int, int, int, int> T;
map<T, int> c;
 
int dp(int i, int j, int w, int h) {
    T t = make_tuple(i, j, w, h);
    if(c.count(t) == 1) return c[t];
    int ret = 0;
    REP(k, N) {
        int s = X[k]; int t = Y[k];
        if(s >= i && s <= w && t >= j && t <= h) {
            ret = max(ret, w+h-i-j+1 + dp(i, j, s-1, t-1) + dp(s+1, j, w, t-1)
                                     + dp(i, t+1, s-1, h) + dp(s+1, t+1, w, h));
        }
    }
    return (c[t] = ret);
}
 
int main(void) {
    cin >> W >> H;
    cin >> N;
    REP(i, N) cin >> X[i] >> Y[i];
    cout << dp(1, 1, W, H) << endl;
}

Submission #1033456 - AtCoder Beginner Contest 008 | AtCoder

ABC 007

abc007.contest.atcoder.jp

A問題

#include <bits/stdc++.h>
 
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);++i)
typedef long long int ll;
using namespace std;
 
int main(void) {
    int n;
    cin >> n;
    cout << n-1 << endl;
}

Submission #1025099 - AtCoder Beginner Contest 007 | AtCoder

B問題

#include <bits/stdc++.h>
 
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);++i)
typedef long long int ll;
using namespace std;
 
int main(void) {
    string A;
    cin >> A;
    if(A == "a") cout << -1 << endl;
    else cout << "a" << endl;
}

Submission #1025101 - AtCoder Beginner Contest 007 | AtCoder

C問題

#include <bits/stdc++.h>
 
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);++i)
typedef long long int ll;
using namespace std;
 
typedef pair<int, int> P;
 
char c[51][51];
int v[51][51];
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
int main(void) {
    int R, C, sx, sy, gx, gy;
    cin >> R >> C >> sy >> sx >> gy >> gx;
 
    REP(i, R) {
        REP(j, C) {
            cin >> c[i][j];
            v[i][j] = -1;
        }
    }
 
    sx--; sy--; gy--; gx--;
 
    queue<P> que;
    que.push(P(sy, sx));
    v[sy][sx] = 0;
    while(true) {
        P p = que.front(); que.pop();
        int y = p.first;
        int x = p.second;
        int s = v[y][x];
        if(x == gx && y == gy) {
            cout << s << endl;
            return 0;
        }
        REP(i, 4) {
            int nx = x+dx[i];
            int ny = y+dy[i];
            if(nx < 0 || nx >= C || ny < 0 || ny >= R
                || v[ny][nx] != -1 || c[ny][nx] == '#') continue;
            que.push(P(ny, nx));
            v[ny][nx] = s+1;
        }
    }
}

Submission #1025116 - AtCoder Beginner Contest 007 | AtCoder

D問題

  • [A, B]に含まれる禁止された数（4または9が含まれる数）の個数を数え上げる
  • [0, A]に含まれる禁止された数を求める関数f(A)を作ればf(B)-f(A-1)が答え
  • f(A)の作り方を考えるために例としてA=3456の場合を考える
  • A=3256のときは、A=2999までの禁止された数とA=456までの禁止された数を数えればよい。
  • このように、同じ桁数の数についてのカウントと、違う桁数の数についてのカウントを分けて再帰的に数えていく。
  • A=2999までのときは0〜999、1000〜1999、2000〜2999にそれぞれ 1000 - 8^3個の禁止された数がある
  • A=456までのときは最上位が禁止された数なのでA=399までの禁止された数の個数と400〜456の数の個数の和が禁止された数の個数である。
  • したがって、最上位の数が4 or 9のときとそれ以外のときで再帰するかどうかが変わる
  • 「同じ桁数の数についてのカウント」で最上位の桁が4 or 9の数は全て禁止された数になるのでカウント時に8のべき乗を引かなくて良い。それを表すために最上位の桁に応じた引く回数を配列cntに入れておく。
#include <bits/stdc++.h>
 
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
#define RREP(i,n) for(int i=(int)(n); i>=0; --i)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);++i)
typedef long long int ll;
using namespace std;
 
int cnt[] = {0, 1, 2, 3, 4, 4, 5, 6, 7, 8};
 
ll f(ll n) {
    if(n == 0) return 0;
 
    ll size = 1;
    ll ok = 1;
    while(n/size >= 10) {
        size *= 10;
        ok *= 8;
    }
    ll msd = n / size;
 
    ll ret = size * msd - ok * cnt[msd];
 
    ll rem_digit = n - msd * size;
 
    if(msd == 4 || msd == 9) {
        return ret + (rem_digit + 1);
    } else {
        return ret + f(rem_digit);
    }
}
 
 
int main(void) {
    ll A, B;
    cin >> A >> B;
    cout << f(B) - f(A-1) << endl;
}

Submission #1025963 - AtCoder Beginner Contest 007 | AtCoder

ABC 006

abc006.contest.atcoder.jp

A問題

#include <bits/stdc++.h>
 
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);++i)
typedef long long int ll;
using namespace std;
 
int main(void) {
    int N;
    cin >> N;
    cout << (N%3 == 0 ? "YES" : "NO") << endl;
}

Submission #1025003 - AtCoder Beginner Contest 006 | AtCoder

B問題

#include <bits/stdc++.h>
 
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);++i)
typedef long long int ll;
using namespace std;
 
int a[1000010];
int main(void) {
    int n;
    cin >> n;
    a[1] = a[2] = 0;
    a[3] = 1;
    FOR(i, 4, n+1) {
        a[i] = (a[i-1] + a[i-2] + a[i-3]) % 10007;
    }
    cout << a[n] << endl;
}

Submission #1025009 - AtCoder Beginner Contest 006 | AtCoder

C問題

全てのbに対して解が存在するか調べる。

#include <bits/stdc++.h>
 
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);++i)
typedef long long int ll;
using namespace std;
 
int main(void) {
    int N, M;
    cin >> N >> M;
    int a, b, c;
    REP(b, N+1) {
        int t = M - 3*b;
        if(t % 2 != 0) continue;
        c = t/2 - (N-b);
        a = (N-b) - c;
        if(a >= 0 && c >= 0) {
            printf("%d %d %d\n", a, b, c);
            return 0;
        }
    }
    a = b = c = -1;
    printf("%d %d %d\n", a, b, c);
}

D問題

最長増加部分列問題 (Longest Increasing Subsequence) という典型問題らしい。

  • k枚抜いたらソート済みになる最小のkが求まれば、k枚を適切な位置に挿入することで全てソート済みの列が作れるからkが答えになる。
  • 「今まで見たカードまでで作れる長さiのソート済み部分列の最後の数字の最小値」を格納するdp[i]を用意しておいてカードを前から見て埋めていく。
  • カードcを見ているとき、「dp[i-1] < c < dp[i+1]を満たす最小のi」に埋めるので二分探索で行う
  • 埋まっている数の最大値が最小数のカードを抜いた後の残り枚数なので、Nから最大値を引くと答えになる
#include <bits/stdc++.h>
 
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);++i)
typedef long long int ll;
using namespace std;
int main(void) {
    int N;
    cin >> N;
    vector<int>c(N);
    REP(i, N) cin >> c[i];
    vector<int> dp(N+1, 1e9);
    dp[0] = -1e9;
    REP(i, N) {
        int k = c[i];
        int l = 0, r = N+1;
        while(l < r) {
            int m = (l + r) / 2;
            if(k < dp[m]) r = m;
            else l = m+1;
        }
        dp[l] = k;
    }
    int ans = 0;
    REP(i, N+1) {
        if(dp[i] != 1e9) ans = i;
    }
    cout << N-ans << endl;
}

Submission #1025896 - AtCoder Beginner Contest 006 | AtCoder

http://abc006.contest.atcoder.jp/submissions/1025896

ABC 004

abc004.contest.atcoder.jp

A問題

#include <bits/stdc++.h>
 
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);++i)
typedef long long int ll;
using namespace std;
 
int main(void) {
    int N;
    cin >> N;
    cout << 2*N << endl;
}

Submission #1024943 - AtCoder Beginner Contest 004 | AtCoder

B問題

#include <bits/stdc++.h>
 
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
typedef long long int ll;
using namespace std;
 
int main(void) {
    char c[4][4];
    REP(i, 4) REP(j, 4) cin >> c[i][j];
    for(int i=3; i>=0; --i) {
        for(int j=3; j>0; --j) cout << c[i][j] << " ";
        cout << c[i][0] << endl;
    }
}

Submission #1024944 - AtCoder Beginner Contest 004 | AtCoder

C問題

観察すると30回ごとに同じパターンになることからNを30で割った余りを求めてからシミュレーション

#include <bits/stdc++.h>
 
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
typedef long long int ll;
using namespace std;
 
int main(void) {
    int N;
    cin >> N;
    int c[6];
    N %= 30;
    REP(i, 6) c[i] = i+1;
    REP(i, N) {
        swap(c[i%5], c[i%5+1]);
    }
    REP(i, 6) cout << c[i];
    cout << endl;
}

Submission #1024949 - AtCoder Beginner Contest 004 | AtCoder

D問題

dp[pos][remain]を「0からposまでの箱を使ってマーブルを配置したときに必要な最小の移動数」として動的計画法を行う（ただしposは-400を0とするようにずらしてある）

  • 初期化はdp[i][R+G+B]=0、その他は大きい数。
  • 漸化式はdp[i][j] = min(dp[i-1][j], dp[i-1][j+1] + cost(i, j))。（コメントの指摘を受けて修正しました）
  • cost(i, j)はj個残っているときにi番目の箱に入れるための最小の移動数を表す。左から順に入れているので、残りの数によってどの色を入れるのが移動数最小になるのかは一意に定まり、その色の箱の位置とposの差の絶対値が移動量になる。
#include <bits/stdc++.h>
 
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);++i)
typedef long long int ll;
using namespace std;
 
int R, G, B;
int dp[1000][1000]; // dp[pos][remain] = number of move
 
int cost(int pos, int remain) {
    if(remain >= G+B) return abs(400-pos);
    else if(remain >= B) return abs(500-pos);
    else return abs(600-pos);
}
 
int main(void) {
    cin >> R >> G >> B;
    int total = R + G + B;
    REP(i, 1000) REP(j, 1000) dp[i][j] = 1e9;
    REP(i, 1000) dp[i][total] = 0;
    FOR(i, 1, 1000) {
        REP(j, total) {
            dp[i][j] = min(dp[i-1][j], dp[i-1][j+1] + cost(i, j));
        }
    }
    int ans = 1e9;
    REP(i, 1000) {
        ans = min(ans, dp[i][0]);
    }
    cout << ans << endl;
}

Submission #1024931 - AtCoder Beginner Contest 004 | AtCoder

ABC 005

abc005.contest.atcoder.jp

A問題

#include <bits/stdc++.h>
 
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);++i)
typedef long long int ll;
using namespace std;
 
int main(void) {
    int x, y;
    cin >> x >> y;
    cout << y / x << endl;
}

Submission #1024248 - AtCoder Beginner Contest 005 | AtCoder

B問題

#include <bits/stdc++.h>
 
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);++i)
typedef long long int ll;
using namespace std;
 
int main(void) {
    int N;
    cin >> N;
    vector<int> T(N);
    REP(i, N) cin >> T[i];
    sort(T.begin(), T.end());
    cout << T[0] << endl;
}

Submission #1024251 - AtCoder Beginner Contest 005 | AtCoder

C問題

#include <bits/stdc++.h>
 
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);++i)
typedef long long int ll;
using namespace std;
 
int main(void) {
    int T, N, M;
    cin >> T >> N;
    vector<int> A(N);
    REP(i, N) cin >> A[i];
    cin >> M;
    vector<int> B(M);
    REP(i, M) cin >> B[i];
 
    bool ok = true;
    if(M > N) ok = false;
 
    int idx = 0;
    REP(i, M) {
        bool serve = false;
        while(idx < N && A[idx] < B[i] - T) idx++;
        if(A[idx] >= B[i] - T && A[idx] <= B[i]) {
            idx++;
        } else {
            ok = false;
        }
    }
    cout << (ok ? "yes" : "no") << endl;
}

Submission #1024261 - AtCoder Beginner Contest 005 | AtCoder

D問題

  • 左上(0, 0)右下(i, j)の長方形のおいしさの和をacc[i][j]に入れる。 O(N^2)
  • (x, y, w, h)を指定したらその長方形のおいしさの和を返す関数がarea。 O(1)
  • 全ての高さ・幅の長方形に対して最大のおいしさを求める。 O(N^4)
  • 各たこ焼き数以下で達成できる最大のおいしさを求める。 O(N^2)
  • 以上の準備をすれば、各店員の焼けるたこ焼き数に対する最大のおいしさが O(1)で求まる。
#include <bits/stdc++.h>
 
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);++i)
typedef long long int ll;
using namespace std;
 
int D[55][55];
int acc[55][55];
int P[2501];
int memo[2501];
 
int area(int x, int y, int w, int h) {
    return acc[x+w][y+h] - acc[x+w][y] - acc[x][y+h] + acc[x][y];
}
 
int main(void) {
    int N, Q;
    cin >> N;
    REP(i, N) REP(j, N) cin >> D[i][j];
    cin >> Q;
    REP(i, Q) cin >> P[i];
 
 
    REP(j, N+1) acc[0][j] = 0;
    FOR(i, 1, N+1) {
        int row = 0;
        acc[i][0] = 0;
        FOR(j, 1, N+1) {
            row += D[i-1][j-1];
            acc[i][j] = acc[i-1][j] + row;
        }
    }
    REP(i, 2501) memo[i] = 0;
    REP(w, N+1) {
        REP(h, N+1) {
            REP(x, N-w+1) {
                REP(y, N-h+1) {
                    memo[w*h] = max(memo[w*h], area(x, y, w, h));
                }
            }
        }
    }
    FOR(i, 1, 2501) memo[i] = max(memo[i], memo[i-1]);
    REP(i, Q) cout << memo[P[i]] << endl;
}

Submission #1025052 - AtCoder Beginner Contest 005 | AtCoder

ABC 003

abc003.contest.atcoder.jp

A問題

#include <bits/stdc++.h>
 
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);++i)
typedef long long int ll;
using namespace std;
 
int main(void) {
    int N;
    cin >> N;
    double s;
    REP(i, N) {
        s += 10000*double(i+1)/N;
    }
    printf("%.10f\n", s);
}

Submission #1024144 - AtCoder Beginner Contest 003 | AtCoder

B問題

"string"[i]というテクニックを学んだ

#include <bits/stdc++.h>
 
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);++i)
typedef long long int ll;
using namespace std;

int main(void) {
    string S, T;
    cin >> S >> T;
    bool win = true;
    map<char, bool> ok;
    REP(i, 7) ok["atcoder"[i]] = true;
    REP(i, S.size()) {
        if(S[i] != T[i]) {
            if(S[i] == '@' && ok[T[i]]) continue;
            if(T[i] == '@' && ok[S[i]]) continue;
            win = false;
        }
    }
    if(win) cout << "You can win" << endl;
    else cout << "You will lose" << endl;
}

Submission #1024159 - AtCoder Beginner Contest 003 | AtCoder

C問題

#include <bits/stdc++.h>
 
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);++i)
typedef long long int ll;
using namespace std;

int main(void) {
    int N, K;
    cin >> N >> K;
    vector<int> R(N);
    REP(i, N) {
        cin >> R[i];
    }

    sort(R.begin(), R.end());
    double ans = 0;
    FOR(i, N-K, N) {
        ans = (ans + R[i]) / 2.0;
    }
    printf("%.10f\n", ans);
}

Submission #1024161 - AtCoder Beginner Contest 003 | AtCoder

D問題

100点解法。nCrをパスカルの三角形を使って求める。

#include <bits/stdc++.h>
 
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);++i)
typedef long long int ll;
using namespace std;
 
const ll mod = 1000000007;
 
vector<vector<int> > C(1000, vector<int>(1000, -1));
ll combination(int n, int r) {
    if(r == 0 || r == n) return 1;
    if(C[n][r] != -1) return C[n][r];
    return (C[n][r] = (combination(n-1, r-1)+combination(n-1, r))%mod);
}
int main(void) {
    int R, C, X, Y, D, L;
    cin >> R >> C >> X >> Y >> D >> L;
 
    cout << ((R-X+1) * (C-Y+1) * combination(D+L, D)) % mod << endl;
}

101点解法 Submission #740595 - AtCoder Beginner Contest 003 | AtCoderを見た

上下左右の壁にくっついているパターンの数を、包除原理を用いて上下左右にくっついていないパターンを取り除くことで求める。

#include <bits/stdc++.h>
 
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);++i)
typedef long long int ll;
using namespace std;

const ll mod = 1e9+7;

int R, C, X, Y, D, L;

vector<vector<int> > memo(1000, vector<int>(1000, -1));

ll nCr(int n, int r) {
    if(n < 0 || r < 0 || n < r) return 0;
    if(r == 0 || r == n) return 1;
    if(memo[n][r] != -1) return memo[n][r];
    return (memo[n][r] = (nCr(n-1, r-1) + nCr(n-1, r))%mod);
}

int main(void) {
    cin >> R >> C >> X >> Y >> D >> L;
    const int N = D + L;

    if(X*Y == N) {
        cout << (C-Y+1)*(R-X+1) * nCr(N, L) % mod << endl;
    } else {
        ll t = ( (
                 nCr(X*Y, N) - (
                    2 * (nCr((X-1)*Y, N) + nCr(X*(Y-1), N))
                ) + (
                    nCr((X-2)*Y, N) + nCr(X*(Y-2), N) + 4 * nCr((X-1)*(Y-1), N)
                ) - (
                    2 * (nCr((X-2)*(Y-1), N) + nCr((X-1)*(Y-2), N))
               ) + (
                   nCr((X-2)*(Y-2), N)
                )
            ) * nCr(N, L) % mod * (C-Y+1) % mod * (R-X+1)
        ) % mod;
        while(t < 0) t += mod;
        cout << t << endl;
    }
}