t8m8-mem8

競プロとか、学んだことを書いていきます。

SRM 396 Div1 Medium: FixImage

問題

白('.')と黒('#')のピクセルで構成されたテーブル(alteredImage)が与えられる。黒のピクセル同士が上下左右のいずれかで接しているとき、それらのピクセルは連結しているとする。連結した黒のピクセルの中から任意の2点を選んだとき、その2点のパスの長さがマンハッタン距離と等しくなるようなテーブルに変換したい。

できる操作は白のピクセルを黒のピクセルに変換することのみ。最小の操作回数で変換を行ったテーブルを求めよ。

制約

 1{\leq}|alteredImage|{\leq}50

解法

コの字やロの字のようになっている連結した黒のピクセルは、任意の2点でパスの長さとマンハッタン距離が一致しないので、このような部分を探して変換する。黒のピクセル同士が連結しているかどうかはUnion Find Treeで管理する。

ある黒のピクセルAから上下左右の4方向を探索していき、白のピクセルを挟んでAと連結している黒のピクセルBを見つけたら、AとBの間の白のピクセルをすべて黒に変換する。これを全ピクセルに対して行い、更新が止まるまで続ける。

黒に変換することによって、違う塊だった黒ピクセル同士が連結することがあり得るので、変換操作の度に連結処理を行う。

import java.util.*;

public class FixImage {

    DisjointSet ds;
    char[][] pixel;
    int h, w;
    int[] dy = {0,1,0,-1};
    int[] dx = {1,0,-1,0};


    public String[] originalImage(String[] alteredImage) {
        h = alteredImage.length;
        w = alteredImage[0].length();

        pixel = new char[h][];
        for (int i=0; i<h; i++) pixel[i] = alteredImage[i].toCharArray();

        ds = new DisjointSet(h*w);

        for (int i=0; i<h; i++) {
            for (int j=0; j<w; j++) {

                if (pixel[i][j] == '.') continue;

                for (int k=0; k<2; k++) {
                    int ni = i + dy[k];
                    int nj = j + dx[k];
                    if (ni < 0 || nj < 0 || h <= ni || w <= nj || pixel[ni][nj] == '.') continue;

                    ds.unite(i*w+j, ni*w+nj);
                }
            }
        }

        boolean flag = true;

        while (flag) {
            flag = false;
            for (int i=0; i<h; i++) {
                for (int j=0; j<w; j++) {
                    if (pixel[i][j] == '.') continue;

                    for (int k=0; k<4; k++) {
                        int ni = i + dy[k];
                        int nj = j + dx[k];
                        if (ni < 0 || nj < 0 || h <= ni || w <= nj) continue;
                        if (pixel[ni][nj] == '#') continue;
                        if (check(ni, nj, dy[k], dx[k], i*w+j)) {
                            flag = true;
                        }
                    }
                }
            }
        }

        String[] res = new String[h];
        for (int i=0; i<h; i++) {
            res[i] = new String(pixel[i]);
        }
        return res;
    }


    boolean check(int i, int j, int di, int dj, int s) {
        if (i < 0 || j < 0 || h <= i || w <= j) return false;
        if (pixel[i][j] == '#') {
            if (ds.same(s, i*w+j)) return true;
            else return false;
        }

        if (check(i+di, j+dj, di, dj, s)) {
            pixel[i][j] = '#';
            for (int k=0; k<4; k++) {
                int ni = i + dy[k];
                int nj = j + dx[k];
                if (ni < 0 || nj < 0 || h <= ni || w <= nj || pixel[ni][nj] == '.') continue;
                ds.unite(i*w+j, ni*w+nj);
            }
            return true;
        }
        return false;
    }

    class DisjointSet {
        int[] data;

        public DisjointSet(int n){
            data = new int[n];
            for (int i=0; i<n; i++) data[i] = i;
        }

        public int find(int x){
            if(data[x] == x) return x;
            return data[x] = find(data[x]);
        }

        public boolean same(int x,int y){
            return find(x) == find(y);
        }

        public void unite(int x,int y){
            if (find(x) == find(y)) return;
            data[find(x)] = find(y);
        }

        public String toString() {
            return Arrays.toString(data);
        }
    }
}

感想

バグらせることもなく、さくっと解けていい感じ。

同じような問題をどこかでやったような気がするけど忘れた。

SRM 398 Div1 Medium: CountPaths

問題

r×cマスのテーブル上にいくつかの特別なマスがある。この特別なマスを踏んだ回数ごとに(1,1)から(r,c)への経路数を求める。

移動は(i,j)から(i+1,j)または(i,j+1)へのみ可能で、特別なマスは与えられた順番を戻るように踏むことはできない(i番目の特別なマスを踏んだあとにj番目の特別なマスを踏むとき、i<jでないといけない)。

制約

 { \displaystyle
1{\leq} r,c {\leq}50
}

 { \displaystyle
0{\leq}特別なマスの個数{\leq}50
}

解法

DP

dp[r][c][k][n] := k番目の特別なマスを最後に踏んで、合計n個の特別なマスを踏んだ状態での(r,c)までの経路数

感想

Div1 Medにしては簡単なDPだった気がする。

import java.util.*;

public class CountPaths {

    static final int MOD = 1000007;

    public int[] difPaths(int r, int c, int[] fieldrow, int[] fieldcol) {
        int n = fieldrow.length;
        int[][] sf = new int[r][c];

        for (int i=0; i<n; i++) {
            sf[fieldrow[i]-1][fieldcol[i]-1] = i+1;
        }

        int[][][][] dp = new int[r][c][n+1][n+1];
        if (sf[0][0] == 0) dp[0][0][0][0] = 1;
        else dp[0][0][sf[0][0]][1] = 1;

        for (int i=0; i<r; i++) {
            for (int j=0; j<c; j++) {
                for (int k=0; k<=n; k++) {
                    for (int l=0; l<=n; l++) {
                        if (i+1 < r && sf[i+1][j] > k && l+1 <= n) {
                            dp[i+1][j][sf[i+1][j]][l+1] = (dp[i+1][j][sf[i+1][j]][l+1] + dp[i][j][k][l])%MOD;
                        } else if (i+1 < r && sf[i+1][j] == 0) {
                            dp[i+1][j][k][l] = (dp[i+1][j][k][l] + dp[i][j][k][l])%MOD;
                        }

                        if (j+1 < c && sf[i][j+1] > k && l+1 <= n) {
                            dp[i][j+1][sf[i][j+1]][l+1] = (dp[i][j+1][sf[i][j+1]][l+1] + dp[i][j][k][l])%MOD;
                        } else if (j+1 < c && sf[i][j+1] == 0) {
                            dp[i][j+1][k][l] = (dp[i][j+1][k][l] + dp[i][j][k][l])%MOD;
                        }
                    }
                }
            }
        }

        int[] res = new int[n+1];

        for (int i=0; i<=n; i++) {
            for (int j=0; j<=n; j++) {
                res[i] = (res[i] + dp[r-1][c-1][j][i])%MOD;
            }
        }

        return res;
    }
}

SRM 399 Div1 Medium: BinarySum

問題

整数a,b,cが与えられる。それぞれを2進表現(no leading zeros)にしたあと桁数を一番大きいものに合わせて0で埋める。a,b,cのビットの順番を入れ替えたものをそれぞれa',b',c'としたときに、a'+b'=c'となる最小のc'を求める。解がなければ-1を返す。

制約

 1 {\leq} a,b,c {\leq} {2}^{30}

解法

dp[i][j][k][l][ub] := a,b,cの1のビットをそれぞれj,k,l個使用し、下の桁からの繰り上がりがubであるときの、i桁までの最小のc'。

a,bの(i+1)桁目がそれぞれ0か1かの4パターンで状態推移していく。

import java.util.*;

public class BinarySum {

    static final int INF = Integer.MAX_VALUE;

    public int rearrange(int a, int b, int c) {

        int n = Math.max(Integer.toBinaryString(a).length(),Math.max(Integer.toBinaryString(b).length(),Integer.toBinaryString(c).length()));

        int x = Integer.bitCount(a);
        int y = Integer.bitCount(b);
        int z = Integer.bitCount(c);

        int[][][][][] dp = new int[n+1][x+2][y+2][z+2][2];
        for (int i=0; i<=n; i++)
            for (int j=0; j<=x; j++)
                for (int k=0; k<=y; k++)
                    for (int l=0; l<=z; l++)
                        Arrays.fill(dp[i][j][k][l], INF);
        dp[0][0][0][0][0] = 0;

        for (int i=0; i<n; i++) {
            for (int j=0; j<=x; j++) {
                for (int k=0; k<=y; k++) {
                    for (int l=0; l<=z; l++) {
                        for (int ub=0; ub<2; ub++) {

                            if (dp[i][j][k][l][ub] == INF) continue;

                            for (int aBit=0; aBit<2; aBit++) {
                                for (int bBit=0; bBit<2; bBit++) {
                                    int cBit = aBit + bBit + ub;

                                    dp[i+1][j+aBit][k+bBit][l+(cBit&1)][cBit>>1] = Math.min(dp[i+1][j+aBit][k+bBit][l+(cBit&1)][cBit>>1], dp[i][j][k][l][ub] + ((cBit&1)<<i));

                                }
                            }
                        }
                    }
                }
            }
        }

        return dp[n][x][y][z][0] == INF ? -1 : dp[n][x][y][z][0];
    }
}

SRM 400 Div1 Medium: ReversalChain

問題

0と1から成る文字列initをgoalに変換する。できる操作は区間(i, j)の反転(ビットの反転ではなく、文字列の反転)のみで、これをr(i, j)と書く。  r(i_1, j_1),r(i_2,j_2),..,r(i_m,j_m) が与えられた時に { \displaystyle
i_1{\leq}i_2{\leq} ... {\leq}i_m\  {\land} \ \  j_1{\geq}j_2{\geq}...{\geq}j_m
} が成り立つとき、これをreversal chainと呼ぶ。initをgoalに変換する際の最小のreversal chainの長さ(操作の回数)を求めよ。

制約

 1{\leq}|init|{\leq}50

解法

dp[len][i][j][k] := initのi番目の文字から始まる長さlenの部分文字列と、goalのj番目の文字から始まる長さlenの部分文字列を一致させるのに必要な最小の操作回数。k=0で偶数回反転、k=1で奇数回反転。

final int INF = Integer.MAX_VALUE/2;

public int minReversal(String init, String goal) {
    int n = init.length();

    int[][][][] dp = new int[n+1][n][n][2];

    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++) {
            for (int k=0; k<2; k++) {
                if (init.charAt(i) != goal.charAt(j))
                    dp[1][i][j][k] = INF;
            }
        }
    }

    for (int len=2; len<=n; len++) {
        for (int i=0; i<=n-len; i++) {
            for (int j=0; j<=n-len; j++) {
                for (int k=0; k<2; k++) {
                    int a = init.charAt(i) != goal.charAt(j) ? INF : dp[len-1][i+1][j+1][0] + k;
                    int b = init.charAt(i+len-1) != goal.charAt(j+len-1) ? INF : dp[len-1][i][j][0] + k;
                    int c = init.charAt(i) != goal.charAt(j+len-1) ? INF : dp[len-1][i+1][j][1] + (k+1)%2;
                    int d = init.charAt(i+len-1) != goal.charAt(j) ? INF : dp[len-1][i][j+1][1] + (k+1)%2;

                    dp[len][i][j][k] = Math.min(Math.min(a,b),Math.min(c,d));
                }
            }
        }
    }

    return dp[n][0][0][0] == INF ? -1 : dp[n][0][0][0];
}

TopCoder SRM 664 Div2 Hard : BearSorts

問題


TopCoder Statistics - Problem Statement
大小比較の際に、真偽が50%の確率でランダムに返ってくる恐ろしいマージソートがある。
入力として、このマージソートでソート済みの配列seqが与えられる。
[1,2..N]の配列をこのマージソートにかけたときに、seqになる確率の自然対数をとった値を求める。

制約


素数N: 1<=N<=40

解法


真偽の確率が等しいから比較回数をカウントして0.5をその数だけかければ良い。あとはlogをとって返す。
seqから普通のマージソートを行うとカウント数が異なるので注意。

int[] T,sorted;
int n,cnt = 0;

public double getProbability(int[] seq) {
    n = seq.length;
    sorted = seq.clone();
    T = new int[n];
    for (int i=0; i<n; i++) {
        T[i] = i+1;
    }
    merge(0,n);
    return Math.log(Math.pow(0.5,cnt));
}

void merge(int l, int r) {
    if (l+1 >= r) return;
    int m = (l+r)/2;
    merge(l,m);
    merge(m,r);
    ArrayList<Integer> list = new ArrayList<Integer>();
    int p1 = l;
    int p2 = m;
    while (p1 < m || p2 < r) {
        if (p1 == m) {
            list.add(T[p2]);
            p2++;
        }else if (p2 == r) {
            list.add(T[p1]);
            p1++;
        }else {
            cnt++;
            if (less(T[p1],T[p2])) {
                list.add(T[p1]);
                p1++;
            }else {
                list.add(T[p2]);
                p2++;
            }
        }
    }

    for (int i=l; i<r; i++) {
        T[i] = list.get(i-l);
    }
}

boolean less(int a, int b) {
    for (int i=0; i<n; i++) {
        if (sorted[i] == a) {
            return true;
        }else if (sorted[i] == b){
            return false;
        }
    }
    return false;
}

TCO 2015 Round 2C in Tokyo

初めての記事。
TCO 2015 Round 2Cの東京オンサイトに参加してきた。オンサイトイベントは少ないから行けるだけで嬉しい。

先着100人と言われたから早めに行ってTシャツ貰ったけど、結局みんな貰えたっぽい(?)。会場に入ると既に結構人がいる。みんな強そうに見える。みんな赤く見える。

肝心のTCOの結果は0完だった。challenge phaseの終了とともに会場に広がるため息。同じような人が多いらしい。
Easyの解法はiwiさんのスライドの3問目。解説を聞いてしまえばDPするだけだけど、それまでの考察ができなかった。悔しい。

Hackathonはやっぱりkenkooooさんのやつ(AtCoder Problems)がとても良かった。すぐにブックマークした。

交流会では普段できない話ができて楽しかった。でも今思うともっといろんな人と話してみたかったなーという感じ。既にできている輪の中に入っていくのは意外と難易度が高かった。また今度誰かお話ししましょう・・。あと、お酒を飲むとすぐ顔が赤くなるのでいろんな人に心配された。もっと(レート的に)赤い人がそのへんにいるぞー。

// TCO 2015 Round 2C Easy 

    public int maxCards(int[] petr, int[] snuke) {
    	int n = petr.length;

    	int[][] dp = new int[n*2+1][101];
    	for (int i=0; i<n*2+1; i++) {
    		Arrays.fill(dp[i], -1);
    	}

    	dp[0][0] = 0;
    	int[][] cards = new int[][]{petr, snuke};

    	for (int i=0; i<n*2; i++) {
    		for (int j=0; j<n; j++) {
    			int card = cards[i%2][j];

    			for (int k=0; k<101; k++) {
    				dp[i+1][k] = Math.max(dp[i+1][k], dp[i][k]);

    				if (dp[i][k] != -1 && card > k) {
    					dp[i+1][card] = Math.max(dp[i+1][card], dp[i][k] + 1);
    				}
    			}
    		}
    	}

    	int ans = 0;
    	for (int i=0; i<101; i++) {
    		ans = Math.max(ans, dp[n*2][i]);
    	}

    	return ans;
    }