SRM 396 Div1 Medium: FixImage
問題
白('.')と黒('#')のピクセルで構成されたテーブル(alteredImage)が与えられる。黒のピクセル同士が上下左右のいずれかで接しているとき、それらのピクセルは連結しているとする。連結した黒のピクセルの中から任意の2点を選んだとき、その2点のパスの長さがマンハッタン距離と等しくなるようなテーブルに変換したい。
できる操作は白のピクセルを黒のピクセルに変換することのみ。最小の操作回数で変換を行ったテーブルを求めよ。
制約
解法
コの字やロの字のようになっている連結した黒のピクセルは、任意の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でないといけない)。
制約
解法
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を返す。
制約
解法
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)と書く。 が与えられた時に が成り立つとき、これをreversal chainと呼ぶ。initをgoalに変換する際の最小のreversal chainの長さ(操作の回数)を求めよ。
制約
解法
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; }