C.Traveling(300)

問題

https://beta.atcoder.jp/contests/arc089/tasks/arc089_a

x-y二次元平面を考える。t=0で(0,0)にいる。1秒後に(x+1,y),(x-1,y),(x,y+1),(x,y-1)のいずれかになる。t_i秒時に( x_i, y_i )にいることができるか判定せよ。

方針

       public void solve(int testNumber, InputReader in, PrintWriter out) {

            int n = in.nextInt();
            int[] t = new int[n+1], x = new int[n+1], y = new int[n+1];
            for (int i = 1; i < n+1; i++) {
                t[i] = in.nextInt();
                x[i] = in.nextInt();
                y[i] = in.nextInt();
            }

            for (int i = 1; i < n+1; i++) {
                int dt = t[i] - t[i-1];
                int dx = x[i] - x[i-1];
                int dy = y[i] - y[i-1];
                if (dx + dy > dt) {
                    out.println("No");
                    return;
                }
                if ((dt - abs(dx + dy)) % 2 == 0) {
                    continue;
                } else {
                    out.println("No");
                    return;
                }
            }
            out.println("Yes");

        }

雑記

列の差分を求めれば、貪欲に求まる問題でした。

D.Checker(500)

問題

https://beta.atcoder.jp/contests/arc089/tasks/arc089_b

x,y座標上にN個の要素が与えられる。i 番目の要素はそれぞれ x_i,y_i,c_i (c_i = {'B', 'W'})である。辺Kの市松模様でx,y座標を塗る時、x_i.y_iのc_iと同じ色になるように塗られている個数の最大値を求めよ。

方針

x_i,y_iが大きい(10⁹)ので、普通にx_i,y_iの2次元グリッド上でシミュレーションすることはできない。よく考えると、座標は2K周期になっていることがわかる。また、x_iをKだけx軸の正の方向に動かすと色が反転する。この性質を利用すると、求める内容は2K×2Kの範囲に存在するどちらかの色('B' or 'W')の個数になる。
市松模様で塗るときの最大個数は2K×2Kの範囲を(0,0)を起点にして全探索すればよい。ただしその時、各( i , j ) を起点して色の個数を求めるときに1回あたりO(K²)かかると、全体としてO(K⁴)となりTLEする。色の個数を求める時、事前に2次元累積和を求めておくと、それぞれの起点ごとに色の個数はO(1)で求められ、全体の計算量はO(K²)となり間に合う。

       public void solve(int testNumber, InputReader in, PrintWriter out) {

            int n = in.nextInt(), k = in.nextInt();
            int[][] mat = new int[4*k+1][4*k+1];
            int[][] sum = new int[4*k+1][4*k+1];
            for (int i = 0; i < n; i++) {
                int x = in.nextInt();
                int y = in.nextInt();
                String c = in.nextString();

                if (c.equals("W")) {
                    y += k;
                }

                mat[x%(2*k)][y%(2*k)]++;
            }

            for (int x = 0; x <= 4*k; x++) {
                for (int y = 0; y <= 4*k; y++) {
                    mat[x][y] = mat[x%(2*k)][y%(2*k)];
                }
            }

            for (int i = 0; i <= 4*k; i++) {
                for (int j = 0; j <= 4*k; j++) {
                    sum[i][j] = mat[i][j];
                    if (j-1 >= 0) sum[i][j] += sum[i][j-1];
                    if (i-1 >= 0) sum[i][j] += sum[i-1][j];
                    if (i-1 >= 0 && j-1 >= 0) sum[i][j] -= sum[i-1][j-1];
                }
            }

            int ans = 0;
            for (int x = 0; x <= 2*k; x++) {
                for (int y = 0; y <= 2*k; y++) {
                    int tmp = 0;
                    tmp += get(x, y, x+k-1, y+k-1, sum);
                    tmp += get(x+k, y+k, x+2*k-1, y+2*k-1, sum);
                    ans = Math.max(ans, tmp);
                }
            }

            out.println(ans);
        }

        int get(int x1, int y1, int x2, int y2, int[][] sum) {

            int res = sum[x2][y2];
            if (x1 > 0) res -= sum[x1-1][y2];
            if (y1 > 0) res -= sum[x2][y1-1];
            if (x1 > 0 && y1 > 0) res += sum[x1-1][y1-1];

            return res;
        }

雑記

以下がポイントと思われる。

2次元累積和
(グリッド上の)周期性

典型の組み合わせですが、500点問題は難しいですね。

数学/競プロメモ

AtCoder Beginner Contest 086

C.Traveling(300)

問題

方針

雑記

D.Checker(500)

問題

方針

雑記