Time Sale(AOJ No.0245), Bara-Bara Manju(AOJ No.0246), Ice Maze(AOJ No.0247)
Time Sale(AOJ No.0245)
店のマップが横x、縦yのマスで構成される2次元 グリッドが与えられ、マスごとに通路、商品棚の どちらかが割り当てられている。
一つの商品棚には 1種類の商品があり、それは商品番号gで区別される。
同じ商品番号の商品を複数買ってはいけない。
商品棚からは、上下左右に隣接する通路のマスならどんな向きでも商品を取れる。
商品番号gによって 区別され、タイムセールの値引き額d、タイムセールの開始時刻sと売り切れ時刻eが与えられる。
時間は入店した時点で0から始まりまる。
移動は、何もないマスを４近傍で移動可能。
１回移動する毎に１単位時間経過する。商品を取る時間は考えない。
初期位置と商品のタイムセール情報を入力とし、取ることのできた商品の値引き額の合計の最大値を求める。
制約
2 < x, y < 21
0 < タイムセール情報の数n < 9
コード
座標と購入した商品のビットフィールドで一度来た場所を覚えて幅優先。
タイムセール開始前に商品がとれる位置に来た場合は、その場でまつパターンを入れてあるが、移動しないと時間経過しないのでは？
行ったり来たりして時間経過させることができるかもしれないが、そうするとその場所に到達して偶数時間たたないと元の場所に戻れない気がする。
他のルートを通って、商品の販売開始時間にその場所に到達かもしれないが、地形によってはできないこともある？
そうなると、座標と購入済み商品情報だけでなく、経過時間もあわせて既着判定しないといけないような。
なんでAcceptされたの？テストケースが緩いだけか？それともただの勘違いか？
import java.util.*; public class aoj0245 { static final Scanner stdin = new Scanner(System.in); static final int dx[] = {0, 0, -1, 1}, dy[] = {-1, 1, 0, 0}, id2idx[] = new int[10]; static final boolean visited[][][] = new boolean[20][20][(1<<8)]; static int W, H, N; public static void main(String[] args) { while (true) { W = stdin.nextInt(); H = stdin.nextInt(); if ((W|H) == 0) break; char map[][] = new char[H][W]; int sx = -1, sy = -1; for (int i = 0; i < H; ++i) { for (int j = 0; j < W; ++j) { Arrays.fill(visited[i][j], false); char c = stdin.next().charAt(0); if (c == 'P') { sy = i; sx = j; } map[i][j] = c; } } N = stdin.nextInt(); Sale sale[] = new Sale[N]; for (int i = 0; i < N; ++i) { int g = stdin.nextInt(); sale[i] = new Sale(stdin.nextInt(), stdin.nextInt(), stdin.nextInt()); id2idx[g] = i; } System.out.println(solve(sy, sx, map, sale)); } } static int solve(int sy, int sx, char[][] map, Sale[] sale) { int ans = 0; for (int i = 0; i < H; ++i) for (int j = 0; j < W; ++j) Arrays.fill(visited[i][j], false); Queue<State> q = new LinkedList<State>(); q.add(new State(sy, sx, 0, 0, 0)); visited[sy][sx][0] = true; while (!q.isEmpty()) { State p = q.poll(); for (int i = 0; i < 4; ++i) { int nextY = p.y + dy[i], nextX = p.x + dx[i]; State n = new State(p.y, p.x, p.time, p.sum, p.buy); if (!(0 <= nextY && nextY < H && 0 <= nextX && nextX < W) || visited[nextY][nextX][p.buy]) continue; if (!Character.isDigit(map[nextY][nextX])) { //move n.x = nextX; n.y = nextY; n.time++; visited[n.y][n.x][n.buy] = true; if (n.time <= 100) q.add(n); continue; } //don't move int idx = id2idx[map[nextY][nextX] - '0']; if (!n.isPurchased(idx)) { switch (n.onSale(idx, sale)) { case 0: //on sale visited[n.y][n.x][n.buy] = true; n.buy(idx, sale); visited[n.y][n.x][n.buy] = true; ans = Math.max(ans, n.sum); if (!n.isAllPurchased()) q.add(n); break; case -1: //early n.wait(idx, sale); q.add(n); break; case 1: default: } } } } return ans; } static class State { int y, x, time, sum, buy; State(int y, int x, int time, int sum, int buy) { this.y = y; this.x = x; this.time = time; this.sum = sum; this.buy = buy; } boolean isPurchased(int idx) { return ((buy & (1 << idx)) != 0); } int onSale(int idx, Sale[] sales) { Sale s = sales[idx]; return time < s.s ? -1 : s.s <= time && time < s.e ? 0 : 1; } void buy(int idx, Sale[] sales) {; this.buy |= (1<<idx); this.sum += sales[idx].d; } boolean isAllPurchased() { return buy == (1<<N)-1; } void wait(int idx, Sale[] sales) { this.time = sales[idx].s; } } static class Sale { int d = 0, s = 0, e = 0; Sale(int d, int s, int e) { this.d = d; this.s = s; this.e = e; } } }
Bara-Bara Manju(AOJ No.0246)
１桁の自然数がn個与えられて、和が10になるグループを最大いくつつくれるかを答える。
制約
1 < n < 101
アルゴリズム
10の作り方は41個あるので、あらかじめそのパターンを作っとく。
そのパターンでDFS。
また、残っている自然数の総和sumを各イテレーションで計算しておいて、現在作られているグループの数 + が現在求まっている最大グループ数を超えた時点で枝刈りできる。
なお、正しいかどうかは証明してないけど、自然数を２つ作って10を作るパターン(1, 9), (2, 8), (3, 7), (4, 6), (5, 5)があれば、先にグループ化しておいても良さそう。
コード
import java.util.*; public class aoj0246 { static final Scanner stdin = new Scanner(System.in); static final int twoPair[][][] = { {{1,1}, {9,1}}, {{2,1}, {8,1}}, {{3,1}, {7,1}}, {{4,1}, {6,1}}, {{5,2}}}; static final int pair[][][] = { {{1, 2}, {8, 1}}, {{1,1}, {2,1}, {7,1}}, {{1,1}, {3,1}, {6,1}}, {{1,1}, {4,1}, {5,1}}, {{2,2}, {6,1}}, {{2,1}, {3,1}, {5,1}}, {{2,1}, {4,2}}, {{3,2}, {4,1}}, {{1,3}, {7,1}}, {{1,2}, {2,1}, {6,1}}, {{1,2}, {3,1}, {5,1}}, {{1,2}, {4,2}}, {{1,1}, {2,2}, {5,1}}, {{1,1}, {2,1}, {3,1}, {4,1}}, {{1,1}, {3,3}}, {{2,3}, {4,1}}, {{2,2}, {3,2}}, {{1,4}, {6,1}}, {{1,3}, {2,1}, {5,1}}, {{1,3}, {3,1}, {4,1}}, {{1,2}, {2,2}, {4,1}}, {{1,2}, {2,1}, {3,2}}, {{1,1}, {2,3}, {3,1}}, {{2,5}}, {{1,5}, {5,1}}, {{1,4}, {2,1}, {4,1}}, {{1,4}, {3,2}}, {{1,3}, {2,2}, {3,1}}, {{1,2}, {2,4}}, {{1,6}, {4,1}}, {{1,5}, {2,1}, {3,1}}, {{1,4}, {2,3}}, {{1,7}, {3,1}}, {{1,6}, {2,2}}, {{1,8}, {2,1}}, {{1,10}} }; static final int freq[] = new int[10]; static int sum, ans, candidate; static boolean use(int[][] pat) { for (int[] f : pat) if (freq[f[0]] < f[1]) return false; for (int i = 0; i < pat.length; ++i) freq[pat[i][0]] -= pat[i][1]; sum -= 10; candidate++; return true; } static void back(int[][] pat) { sum += 10; candidate--; for (int i = 0; i < pat.length; ++i) freq[pat[i][0]] += pat[i][1]; } public static void main(String[] args) { while (true) { int n = stdin.nextInt(); if (n == 0) break; Arrays.fill(freq, 0); ans = 0; sum = 0; candidate = 0; while (n-- > 0) { int tmp = stdin.nextInt(); freq[tmp]++; sum += tmp; } for (int i = 0; i < twoPair.length;) if (!use(twoPair[i])) i++; ans = candidate; DFS(0); System.out.println(ans); } } static void DFS(int prek) { for (int k = prek; ans < sum/10 + candidate && k < pair.length; ++k) { if (use(pair[k])) { DFS(k); back(pair[k]); } } ans = Math.max(ans, candidate); } }
Ice Maze(AOJ No.0247)
平原、山、氷の属性があるx×yのマップが与えられ、スタート地点からゴール地点まで４近傍移動できる。（スタートとゴールは平原）
平原は移動可能、山は移動不可能、氷は４近傍で一つの氷としてつながっており、氷の面積の半分を超える回数移動するとその氷が割れて、ガメオベラ。
ゴールに到達するまでに掛かる最小の移動回数を求める。
制約
1 < x, y < 13
アルゴリズム
地形によってはかなり遠回りしないと行けなさそうなので、IDDFSとかやってみようとおもった。
氷ははじめにグループ化しておき、グループ毎に耐久度を覚えとく。
まだ、計算量が心配だったので、Iterative Deepneing A*:IDA*。
ヒューリスティック関数h*はゴールまでのマンハッタン距離でもいいかもしれないが、氷が無いときのゴールまでの最短距離をh*とした。
はじめに、ゴール地点からBFSして求めとけば良いだけだし、こちらの方が制限が強くて早めにバックトラックできるはず。
また、周りが既に到達済み（前にいた位置を除く）の場合は、無駄に迂回しているので枝刈り。
現在位置または近傍が氷の場合(氷を迂回する場合)でも、４近傍で氷がつながっているので、無駄に氷を踏んで耐久度を下げてることになる。
なのでこの枝刈りは正しいはず。
コード
デバッグめんどかった。
import java.util.*; public class aoj0247 { static final Scanner stdin = new Scanner(System.in); static int W, H, sidx, gidx, lim; static final char map[] = new char[12*12]; static final boolean visited[] = new boolean[12*12]; static final int dy[] = {-1, 0, 1, 0}, dx[] = {0, 1, 0, -1}, INF = Integer.MAX_VALUE/2; static final int hstar[] = new int[12*12], hardness[] = new int[12*12], ice[] = new int[12*12]; public static void main(String[] args) { while (true) { W = stdin.nextInt(); H = stdin.nextInt(); if ((W|H) == 0) break; for (int i = 0; i < H; ++i) { String s = stdin.next(); for (int j = 0; j < W; ++j) { char c = s.charAt(j); int idx = index(i,j); map[idx] = c; switch(c) { case 'S': sidx = index(i, j); map[idx] = '.'; break; case 'G': gidx = index(i, j); map[idx] = '.'; break; } } } calcHStar(gidx); Arrays.fill(hardness, 0); Arrays.fill(ice, -1); int iceNum = 0; for (int i = 0; i < H; ++i) for (int j = 0; j < W; ++j) { int idx = index(i,j); if (map[idx] == 'X' && ice[idx] == -1) { discoverIce(idx, iceNum); hardness[iceNum] /= 2; iceNum++; } } Arrays.fill(visited, false); visited[sidx] = true; for (lim = 0; !IDAStar(0, sidx, sidx) ;lim++); System.out.println(lim); } } static void calcHStar(int s) { //WFS Arrays.fill(hstar, INF); Queue<Integer> q = new LinkedList<Integer>(); hstar[s] = 0; q.add(s); while(!q.isEmpty()){ int v = q.poll(); for(int k = 0; k < 4; ++k) { int ny = getY(v) + dy[k], nx = getX(v) + dx[k], nv = index(ny, nx); if(inRange(ny, nx) && (map[nv] == '.' || map[nv] == 'X') && hstar[nv] > hstar[v] + 1){ hstar[nv] = hstar[v]+1; q.add(nv); } } } } static void discoverIce(int pos, int id) { //WFS Queue<Integer> q = new LinkedList<Integer>(); q.add(pos); ice[pos] = id; hardness[id]++; while (!q.isEmpty()) { int v = q.poll(); for (int k = 0; k < 4; ++k) { int ny = getY(v) + dy[k], nx = getX(v) + dx[k], npos = index(ny, nx); if (inRange(ny, nx) && map[npos] == 'X' && ice[npos] == -1) { q.add(npos); ice[npos] = id; hardness[id]++; } } } } static boolean IDAStar(int depth, int pos, int prepos) { if (pos == gidx) return true; if (depth + hstar[pos] > lim) return false; for (int k = 0; k < 4; ++k) { //前にいた位置を除いて、周りが既に到達済みならバックトラック int ny = getY(pos) + dy[k], nx = getX(pos) + dx[k], npos = index(ny, nx); if (!inRange(ny, nx) || npos == prepos) continue; if (visited[npos]) return false; } for (int k = 0; k < 4; ++k) { int ny = getY(pos) + dy[k], nx = getX(pos) + dx[k], npos = index(ny, nx); if (!inRange(ny, nx) || visited[npos]) continue; boolean nextIce = (map[npos] == 'X'); if (nextIce || map[npos] == '.') { if (nextIce && hardness[ice[npos]] <= 0) continue; if (nextIce) hardness[ice[npos]]--; visited[npos] = true; if (IDAStar(depth+1, npos, pos)) return true; if (nextIce) hardness[ice[npos]]++; visited[npos] = false; } } return false; } static int getX(int index) { return index%W; } static int getY(int index) { return index/W; } static int index(int y, int x) { return y * W + x; } static boolean inRange(int y, int x) { return 0 <= y && y < H && 0 <= x && x < W; } }
