Hatena::Grouptopcoder

Topcoderと数オリを目指す日記

2017-03-24

AtCoder Beginner Contest D問題

11:59

4:マーブル

部分点解法(40/100):1≦R,G,B≦40

マーブルが入っている最初の3つの箱の両側に均等に配置していく事が最適なGreedy戦略である。

import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int R = sc.nextInt();
    int G = sc.nextInt();
    int B = sc.nextInt();
    int r1 = (R - 1) / 2;
    int r2 = R - 1 - r1;
    int rsum = (r1 * (r1 + 1)) / 2 + (r2 * (r2 + 1)) / 2;
    int g1 = (G - 1) / 2;
    int g2 = G - 1 - g1;
    int gsum = (g1 * (g1 + 1)) / 2 + (g2 * (g2 + 1)) / 2;
    int b1 = (B - 1) / 2;
    int b2 = B - 1 - b1;
    int bsum = (b1 * (b1 + 1)) / 2 + (b2 * (b2 + 1)) / 2;
    System.out.println(rsum + gsum + bsum);
  }
}

AC

満点解法(100/100):1≦R,G,B≦300

緑のマーブルの左端を決めれば、最適な置き方は一意的に定まる。

import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int R = sc.nextInt();
    int G = sc.nextInt();
    int B = sc.nextInt();
    int minCost = Integer.MAX_VALUE;
    // 緑のマーブルの左端を全探索
    for(int i = -349; i <= 50; i++) {
      int rcost = 0;
      int gcost = 0;
      int bcost = 0;
      for(int j = i; j < i + G; j++) {
        gcost += (int)Math.abs(j);
      }
      if(i <= -99) {
        for(int j = i - R; j < i; j++) {
          rcost += (int)Math.abs(j + 100);
        } 
      } else {
        int s = (R - 1) / 2;
        int t = (R - 1) - s;
        if(s <= i + 99) {
          rcost = (s * (s + 1)) / 2 + (t * (t + 1)) / 2;
        } else {
          for(int j = i - R; j < i; j++) {
            rcost += (int)Math.abs(j + 100);
          }
        }
      }
      if(i + G >= 100) {
        for(int j = i + G; j < i + G + B; j++) {
          bcost += (int)Math.abs(j - 100);
        }
      } else {
        int u = (B - 1) / 2;
        int v = (B - 1) - u;
        if(u <= 100 - (i + G)) {
          bcost = (u * (u + 1)) / 2 + (v * (v + 1)) / 2;
        } else {
          for(int j = i + G; j < i + G + B; j++) {
            bcost += (int)Math.abs(j - 100);
          }
        }
      }
      minCost = Math.min(minCost, rcost + gcost + bcost);
    }
    System.out.println(minCost);
  }
}

AC

5:おいしいたこ焼きの焼き方

累積和をDPで求めておく(計算量はO(N^2))。全体の計算量はO(N^5)である。

import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int[][] D = new int[N][N];
    int[][] takoyaki = new int[N][N];
    for(int i = 0; i < N; i++) {
      for(int j = 0; j < N; j++) {
        D[i][j] = sc.nextInt();
      }
    }
    takoyaki[0][0] = D[0][0];
    for(int j = 1; j < N; j++) {
      takoyaki[0][j] = takoyaki[0][j - 1] + D[0][j];
    }
    for(int i = 1; i < N; i++) {
      for(int j = 0; j < N; j++) {
        if(j == 0) {
          takoyaki[i][j] = takoyaki[i - 1][j] + D[i][j];
        } else {
          takoyaki[i][j] = takoyaki[i][j - 1] + takoyaki[i - 1][j] - takoyaki[i - 1][j - 1] + D[i][j];
        }
      }
    }
    int Q = sc.nextInt();
    for(int i = 0; i < Q; i++) {
      int p = sc.nextInt();
      int tasteSum = 0;
      for(int j = 1; j <= N; j++) {
        int c = Math.min(N, p / j);
        if(c > 0) {
          for(int k = 0; k <= N - j; k++) {
            for(int l = 0; l <= N - c; l++) {
              int s = 0;
              int t = 0;
              int u = 0;
              if(l > 0) s = takoyaki[k + j - 1][l - 1];
              if(k > 0) t = takoyaki[k - 1][l + c - 1];
              if(k > 0 && l > 0) u = takoyaki[k - 1][l - 1];
              tasteSum = Math.max(tasteSum, takoyaki[k + j - 1][l + c - 1] - s - t + u);
            }
          }
        }
      }
      System.out.println(tasteSum);
    }
  }
}

AC

2017-03-23

AtCoder Beginner Contest D問題

18:41

2:派閥

最大クリーク問題である。bitを利用して全パターンを調べれば良い。

import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int M = sc.nextInt();
    int[][] friend = new int[N][N];
    for(int i = 0; i < M; i++) {
      int x = sc.nextInt() - 1;
      int y = sc.nextInt() - 1;
      friend[x][y] = 1;
      friend[y][x] = 1;
    }
    int group = 1;
    for(int i = 1; i < (int)Math.pow(2, N); i++) {
      ArrayList<Integer> list = new ArrayList<Integer>();
      for(int j = 0; j < N; j++) {
        if((i & (1 << j)) != 0) list.add(j);
      }
      boolean flg = true;
      for(int j = 0; j < list.size(); j++) {
        int id = list.get(j);
        for(int k = 0; k < list.size(); k++) {
          int id2 = list.get(k);
          if(j != k && friend[id][id2] == 0) flg = false;
        }
      }
      if(flg) group = Math.max(group, list.size());
    }
    System.out.println(group);
  }
}

AC

3:AtCoder社の冬

部分点解法(100/101):D+L=X×Y

組み合わせの計算を行うだけである。Cの求め方は、パスカルの三角形を利用するものとフェルマーの小定理を利用するものがある。

フェルマーの小定理

import java.util.*;

public class Main {
  static long MOD = 1000000007;
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    long R = sc.nextLong();
    long C = sc.nextLong();
    long X = sc.nextLong();
    long Y = sc.nextLong();
    long D = sc.nextLong();
    long L = sc.nextLong();
    long ans = (R - X + 1) * (C - Y + 1);
    long r1 = 1;
    long r2 = 1;
    for(long i = 1; i <= D; i++) {
      r1 = (r1 * (L + i)) % MOD;
      r2 = (r2 * i) % MOD;
    }
    ans = (ans * r1) % MOD;
    ans = (ans * func(r2, MOD - 2)) % MOD;
    System.out.println(ans);
  }

  // 繰り返し二乗法(逆元を求める為)
  public static long func(long a, long x) {
    if(x == 0) return 1;
    if(x % 2 == 0) {
      long t = func(a, x / 2);
      return (t * t) % MOD;
    } else {
      long t = func(a, x / 2);
      t = (t * t) % MOD;
      return (t * a) % MOD;
    }
  }
}

AC

パスカルの三角形

import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    long R = sc.nextLong();
    long C = sc.nextLong();
    long X = sc.nextLong();
    long Y = sc.nextLong();
    int D = sc.nextInt();
    int L = sc.nextInt();
    long MOD = 1000000007;
    long ans = (R - X + 1) * (C - Y + 1);
    long[][] dp = new long[D + L + 1][D + L + 1];
    dp[0][0] = 1;
    for(int i = 1; i < D + L + 1; i++) {
      for(int j = 0; j <= i; j++) {
        if(j == 0 || j == i) {
          dp[i][j] = 1;
        } else {
          dp[i][j] = (dp[i - 1][j] + dp[i - 1][j - 1]) % MOD;
        }
      }
    }
    ans = (ans * dp[D + L][D]) % MOD;
    System.out.println(ans);
  }
}

AC

満点解法(101/101)

包除原理を利用して、境界に置かれていない場合の数を求める。

import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    long R = sc.nextLong();
    long C = sc.nextLong();
    long X = sc.nextLong();
    long Y = sc.nextLong();
    int D = sc.nextInt();
    int L = sc.nextInt();
    long MOD = 1000000007;
    long ans = (R - X + 1) * (C - Y + 1);
    long[][] dp = new long[901][901];
    dp[0][0] = 1;
    for(int i = 1; i < 901; i++) {
      for(int j = 0; j <= i; j++) {
        if(j == 0 || j == i) {
          dp[i][j] = 1;
        } else {
          dp[i][j] = (dp[i - 1][j] + dp[i - 1][j - 1]) % MOD;
        }
      }
    }
    long sum = 0;
    long sub = 0;
    // 上の辺、右の辺、下の辺、左の辺をそれぞれA,B,C,Dとおく。
    // X*Yに置く置き方
    sum = (dp[(int)(X * Y)][D + L] * dp[D + L][D]) % MOD;

    // Aに置かない置き方
    sub = (sub + dp[(int)((X - 1) * Y)][D + L] * dp[D + L][D]) % MOD;
    // Bに置かない置き方
    sub = (sub + dp[(int)(X * (Y - 1))][D + L] * dp[D + L][D]) % MOD;
    // Cに置かない置き方
    sub = (sub + dp[(int)((X - 1) * Y)][D + L] * dp[D + L][D]) % MOD;
    // Dに置かない置き方
    sub = (sub + dp[(int)(X * (Y - 1))][D + L] * dp[D + L][D]) % MOD;

    // A,Bに置かない置き方
    long t1 = (dp[(int)((X - 1) * (Y - 1))][D + L] * dp[D + L][D]) % MOD;
    if(sub >= t1) {
      sub = (sub - t1) % MOD;
    } else {
      sub = (sub - t1 + MOD) % MOD;
    }
    // A,Cに置かない置き方
    if(X > 2) {
      long t2 = (dp[(int)((X - 2) * Y)][D + L] * dp[D + L][D]) % MOD;
      if(sub >= t2) {
        sub = (sub - t2) % MOD;
      } else {
        sub = (sub - t2 + MOD) % MOD;
      }
    }
    // A,Dに置かない置き方
    long t3 = (dp[(int)((X - 1) * (Y - 1))][D + L] * dp[D + L][D]) % MOD;
    if(sub >= t3) {
      sub = (sub - t3) % MOD;
    } else {
      sub = (sub - t3 + MOD) % MOD;
    }
    // B,Cに置かない置き方
    long t4 = (dp[(int)((X - 1) * (Y - 1))][D + L] * dp[D + L][D]) % MOD;
    if(sub >= t4) {
      sub = (sub - t4) % MOD;
    } else {
      sub = (sub - t4 + MOD) % MOD;
    }
    // B,Dに置かない置き方
    if(Y > 2) {
      long t5 = (dp[(int)(X * (Y - 2))][D + L] * dp[D + L][D]) % MOD;
      if(sub >= t5) {
        sub = (sub - t5) % MOD;
      } else {
        sub = (sub - t5 + MOD) % MOD;
      }
    }
    // C,Dに置かない置き方
    long t6 = (dp[(int)((X - 1) * (Y - 1))][D + L] * dp[D + L][D]) % MOD;
    if(sub >= t6) {
      sub = (sub - t6) % MOD;
    } else {
      sub = (sub - t6 + MOD) % MOD;
    }

    // A,B,Cに置かない置き方
    if(X > 2 && Y > 1) {
      sub = (sub + dp[(int)((X - 2) * (Y - 1))][D + L] * dp[D + L][D]) % MOD;
    }
    // A,B,Dに置かない置き方
    if(X > 1 && Y > 2) {
      sub = (sub + dp[(int)((X - 1) * (Y - 2))][D + L] * dp[D + L][D]) % MOD;
    }
    // A,C,Dに置かない置き方
    if(X > 2 && Y > 1) {
      sub = (sub + dp[(int)((X - 2) * (Y - 1))][D + L] * dp[D + L][D]) % MOD;
    }
    // B,C,Dに置かない置き方
    if(X > 1 && Y > 2) {
      sub = (sub + dp[(int)((X - 1) * (Y - 2))][D + L] * dp[D + L][D]) % MOD;
    }

    // A,B,C,Dに置かない置き方
    if(X > 2 && Y > 2) {
      long t7 = (dp[(int)((X - 2) * (Y - 2))][D + L] * dp[D + L][D]) % MOD;
      if(sub >= t7) {
        sub = (sub - t7) % MOD;
      } else {
        sub = (sub - t7 + MOD) % MOD;
      }
    }

    long t8 = 0;
    if(sum >= sub) {
      t8 = (sum - sub) % MOD;
    } else {
      t8 = (sum - sub + MOD) % MOD;
    }
    ans = (ans * t8) % MOD;
    System.out.println(ans);
  }
}

AC

AtCoder Beginner Contest C問題

08:50

20:壁抜け

100個のマスに対し、ワーシャル・フロイドで全点対最短距離を求める。そして条件を満たすxの最大値を二分探索する。

import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int H = sc.nextInt();
    int W = sc.nextInt();
    int T = sc.nextInt();
    int start = 0;
    int end = 0;
    char[] board = new char[H * W];
    for(int i = 0; i < H; i++) {
      String s = sc.next();
      for(int j = 0; j < W; j++) {
        board[i * W + j] = s.charAt(j);
        if(board[i * W + j] == 'S') start = i * W + j;
        if(board[i * W + j] == 'G') end = i * W + j;
      }
    }
    int l = 1;
    int r = T;
    int ans = 0;
    while(l < r) {
      int med = (l + r) / 2;
      long[][] dp = new long[H * W][H * W];
      for(int i = 0; i < H * W; i++) {
        for(int j = 0; j < H * W; j++) {
          if(i % W == 0) {
            if(i == 0) {
              if(board[i + 1] == '#') {
                dp[i][i + 1] = med;
              } else {
                dp[i][i + 1] = 1;
              }
              if(board[i + W] == '#') {
                dp[i][i + W] = med;
              } else {
                dp[i][i + W] = 1;
              }
            } else if(i == (H - 1) * W) {
              if(board[i + 1] == '#') {
                dp[i][i + 1] = med;
              } else {
                dp[i][i + 1] = 1;
              }
              if(board[i - W] == '#') {
                dp[i][i - W] = med;
              } else {
                dp[i][i - W] = 1;
              }
            } else {
              if(board[i + 1] == '#') {
                dp[i][i + 1] = med;
              } else {
                dp[i][i + 1] = 1;
              }
              if(board[i - W] == '#') {
                dp[i][i - W] = med;
              } else {
                dp[i][i - W] = 1;
              }
              if(board[i + W] == '#') {
                dp[i][i + W] = med;
              } else {
                dp[i][i + W] = 1;
              }
            }
          } else if(i % W == W - 1) {
            if(i == W - 1) {
              if(board[i - 1] == '#') {
                dp[i][i - 1] = med;
              } else {
                dp[i][i - 1] = 1;
              }
              if(board[i + W] == '#') {
                dp[i][i + W] = med;
              } else {
                dp[i][i + W] = 1;
              }
            } else if(i == H * W - 1) {
              if(board[i - 1] == '#') {
                dp[i][i - 1] = med;
              } else {
                dp[i][i - 1] = 1;
              }
              if(board[i - W] == '#') {
                dp[i][i - W] = med;
              } else {
                dp[i][i - W] = 1;
              }
            } else {
              if(board[i - 1] == '#') {
                dp[i][i - 1] = med;
              } else {
                dp[i][i - 1] = 1;
              }
              if(board[i - W] == '#') {
                dp[i][i - W] = med;
              } else {
                dp[i][i - W] = 1;
              }
              if(board[i + W] == '#') {
                dp[i][i + W] = med;
              } else {
                dp[i][i + W] = 1;
              }
            }
          } else {
            if(i > 0 && i < W) {
              if(board[i - 1] == '#') {
                dp[i][i - 1] = med;
              } else {
                dp[i][i - 1] = 1;
              }
              if(board[i + 1] == '#') {
                dp[i][i + 1] = med;
              } else {
                dp[i][i + 1] = 1;
              }
              if(board[i + W] == '#') {
                dp[i][i + W] = med;
              } else {
                dp[i][i + W] = 1;
              }
            } else if(i > (H - 1) * W && i < H * W - 1) {
              if(board[i - 1] == '#') {
                dp[i][i - 1] = med;
              } else {
                dp[i][i - 1] = 1;
              }
              if(board[i + 1] == '#') {
                dp[i][i + 1] = med;
              } else {
                dp[i][i + 1] = 1;
              }
              if(board[i - W] == '#') {
                dp[i][i - W] = med;
              } else {
                dp[i][i - W] = 1;
              }
            } else {
              if(board[i - 1] == '#') {
                dp[i][i - 1] = med;
              } else {
                dp[i][i - 1] = 1;
              }
              if(board[i + 1] == '#') {
                dp[i][i + 1] = med;
              } else {
                dp[i][i + 1] = 1;
              }
              if(board[i - W] == '#') {
                dp[i][i - W] = med;
              } else {
                dp[i][i - W] = 1;
              }
              if(board[i + W] == '#') {
                dp[i][i + W] = med;
              } else {
                dp[i][i + W] = 1;
              }
            }
          }
        }
      }
      for(int i = 0; i < H * W; i++) {
         for(int j = 0; j < H * W; j++) {
           if(i != j && dp[i][j] == 0) dp[i][j] = (long)Math.pow(10, 12);
        }
      }
      // ワーシャル・フロイド
      for(int k = 1; k <= H * W; k++) {
        for(int i = 0; i < H * W; i++) {
          for(int j = 0; j < H * W; j++) {
            dp[i][j] = Math.min(dp[i][j], dp[i][k - 1] + dp[k - 1][j]);
          }
        }
      }
      if(dp[start][end] <= T) {
        ans = med;
        l = med + 1;
      } else {
        r = med;
      }  
    }
    System.out.println(ans);
  }
}

AC

17:ハイスコア

宝石iを含む遺跡の合計得点scoreをいもす法で求め、scoreの最小値minを求める。後は全得点からminを引いたものが求める最高得点となる。

import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int M = sc.nextInt();
    int[] score = new int[M];
    int sum = 0;
    // いもす
    for(int i = 0; i < N; i++) {
      int l = sc.nextInt() - 1;
      int r = sc.nextInt();
      int s = sc.nextInt();
      sum += s;
      score[l] += s;
      if(r < M) score[r] -= s; 
    }
    int min = score[0];
    for(int i = 1; i < M; i++) {
      score[i] += score[i - 1];
      min = Math.min(min, score[i]);
    }
    System.out.println(sum - min);
  }
}

AC

16:友達の友達

友達関係をグラフで表した時、最短距離が2であれば「友達の友達」である。

import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int M = sc.nextInt();
    int[][] dp = new int[N][N];
    for(int i = 0; i < M; i++) {
      int a = sc.nextInt() - 1;
      int b = sc.nextInt() - 1;
      dp[a][b] = 1;
      dp[b][a] = 1;
    }
    for(int i = 0; i < N; i++) {
      for(int j = 0; j < N; j++) {
        if(i != j && dp[i][j] == 0) dp[i][j] = 100;
      }
    }
    // ワーシャル・フロイド
    for(int k = 1; k <= N; k++) {
      for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++) {
          dp[i][j] = Math.min(dp[i][j], dp[i][k - 1] + dp[k - 1][j]);
        }
      }
    }
    for(int i = 0; i < N; i++) {
      int count = 0;
      for(int j = 0; j < N; j++) {
        if(dp[i][j] == 2) count++;
      }
      System.out.println(count);
    }
  }
}

AC

15:高橋くんのバグ探し

DFSの練習問題。計算量はO(K^N*N)だから間に合う。

import java.util.*;

public class Main {
  static int[][] question;
  static int[] answer;
  static int N;
  static int K;
  static String ret = "Nothing";
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    N = sc.nextInt();
    K = sc.nextInt();
    question = new int[N][K];
    for(int i = 0; i < N; i++) {
      for(int j = 0; j < K; j++) {
        question[i][j] = sc.nextInt();
      }
    }
    answer = new int[N];
    dfs(0);
    System.out.println(ret);
  }

  public static void dfs(int n) {
    if(n == N) {
      int p = 0;
      for(int i = 0; i < N; i++) {
        p = p ^ question[i][answer[i]];
      }
      if(p == 0) ret = "Found";
    } else {
      for(int i = 0; i < K; i++) {
        answer[n] = i;
        dfs(n + 1);
      }
    }
  }
}

AC

14:AtColor

いもす法の練習問題。

import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int[] color = new int[1000001];
    for(int i = 0; i < n; i++) {
      int a = sc.nextInt();
      int b = sc.nextInt() + 1;
      color[a]++;
      if(b < 1000001) color[b]--;
    }
    int max = color[0];
    for(int i = 1; i < 1000001; i++) {
      color[i] += color[i - 1];
      max = Math.max(max, color[i]);
    }
    System.out.println(max);
  }
}

AC

13:節制

普通の食事をx日としたとき、質素な食事の最低日数yを求める。

import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int H = sc.nextInt();
    long A = sc.nextLong();
    long B = sc.nextLong();
    long C = sc.nextLong();
    long D = sc.nextLong();
    long E = sc.nextLong();
    long minCost = Long.MAX_VALUE;
    for(int x = 0; x <= N; x++) {
      long y = 0;
      if(E * N - (B + E) * x - H >= 0) {
        y = (E * N - (B + E) * x - H + D + E) / (D + E);
      } else {
        y = 0;
      }
      minCost = Math.min(minCost, A * x + C * y); 
    }
    System.out.println(minCost);
  }
}

AC

7:幅優先探索

BFSの練習問題。

import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int R = sc.nextInt();
    int C = sc.nextInt();
    int sy = sc.nextInt() - 1;
    int sx = sc.nextInt() - 1;
    int gy = sc.nextInt() - 1;
    int gx = sc.nextInt() - 1;
    int[] start = {sy, sx};
    int[] goal = {gy, gx};
    char[][] maze = new char[R][C];
    for(int i = 0; i < R; i++) {
      String s = sc.next();
      for(int j = 0; j < C; j++) {
        maze[i][j] = s.charAt(j);
      }
    }
    LinkedList<int[]> que = new LinkedList<int[]>();
    int[][] minStep = new int[R][C];
    for(int i = 0; i < R; i++) {
      for(int j = 0; j < C; j++) {
        minStep[i][j] = Integer.MAX_VALUE;
      }
    }
    minStep[sy][sx] = 0;
    que.add(start);
    while(que.size() > 0) {
      int[] mass = que.poll();
      int[] movey = {-1, 0, 1, 0};
      int[] movex = {0, 1, 0, -1};
      for(int i = 0; i < 4; i++) {
        int y = mass[0] + movey[i];
        int x = mass[1] + movex[i];
        if(y >= 0 && y < R && x >= 0 && x < C && maze[y][x] == '.' && minStep[y][x] == Integer.MAX_VALUE) {
          minStep[y][x] = minStep[mass[0]][mass[1]] + 1;
          int[] move = {y, x};
          que.add(move);
        }
      }
    }
    System.out.println(minStep[gy][gx]);
  }
}

AC

2017-03-22

AtCoder Beginner Contest C問題

08:20

29:Brute-force Attack

DFS(深さ優先探索)の練習問題。

import java.util.*;

public class Main {
  static int N;

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    N = sc.nextInt();
    dfs("");
  }

  public static void dfs(String s) {
    if(s.length() == N) {
      System.out.println(s);
    } else {
      dfs(s + "a");
      dfs(s + "b");
      dfs(s + "c");
    }
  }
}

AC

25:双子と○×ゲーム

ゲーム木の探索問題。一つの評価値をDFS(深さ優先探索)により各盤面に対し求めていく。

import java.util.*;

public class Main {
  static int[][] b = new int[2][3];
  static int[][] c = new int[3][2];
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    // 先手と後手の得点の和
    int sum = 0;
    for(int i = 0; i < 2; i++) {
      for(int j = 0; j < 3; j++) {
        b[i][j] = sc.nextInt();
        sum += b[i][j];
      }
    }
    for(int i = 0; i < 3; i++) {
      for(int j = 0; j < 2; j++) {
        c[i][j] = sc.nextInt();
        sum += c[i][j];
      }
    }
    char[][] board = new char[3][3];
    for(int i = 0; i < 3; i++) {
      for(int j = 0; j < 3; j++) {
        board[i][j] = '.';
      }
    }
    int score = dfs(1, board);
    System.out.println((sum + score) / 2);
    System.out.println((sum - score) / 2);
  }

  // n手目の盤面の評価値(先手の得点-後手の得点)
  public static int dfs(int n, char[][] board) {
    if(n == 10) {
      int sente = 0;
      int koute = 0;
      for(int i = 0; i < 2; i++) {
        for(int j = 0; j < 3; j++) {
          if(board[i][j] == board[i + 1][j]) {
            sente += b[i][j];
          } else {
            koute += b[i][j];
          }
        }
      }
      for(int i = 0; i < 3; i++) {
        for(int j = 0; j < 2; j++) {
          if(board[i][j] == board[i][j + 1]) {
            sente += c[i][j];
          } else {
            koute += c[i][j];
          }
        }
      }
      return sente - koute;
    } else {
      if(n % 2 == 0) {
        int score = Integer.MAX_VALUE;
        for(int i = 0; i < 3; i++) {
          for(int j = 0; j < 3; j++) {
            if(board[i][j] == '.') {
              board[i][j] = 'x';
              score = Math.min(score, dfs(n + 1, board));
              board[i][j] = '.';
            }
          }
        }
        return score;
      } else {
        int score = -10000;
        for(int i = 0; i < 3; i++) {
          for(int j = 0; j < 3; j++) {
            if(board[i][j] == '.') {
              board[i][j] = 'o';
              score = Math.max(score, dfs(n + 1, board));
              board[i][j] = '.';
            }
          }
        }
        return score;
      }
    }
  }
}

AC

22:Blue Bird

頂点0に繋がる道を削除して、ワーシャル・フロイドで全点対最短距離を求める。そして、頂点0に繋がる任意の2点i,jを考え、閉路の最短距離を更新していく。

import java.util.*;
 
public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int M = sc.nextInt();
    long[][] road = new long[N][N];
    long[][] dp = new long[N][N];
    for(int i = 0; i < M; i++) {
      int u = sc.nextInt() - 1;
      int v = sc.nextInt() - 1;
      long l = sc.nextLong();
      road[u][v] = l;
      road[v][u] = l;
      dp[u][v] = l;
      dp[v][u] = l;
    }
    for(int i = 0; i < N; i++) {
      for(int j = 0; j < N; j++) {
        if(i != j && dp[i][j] == 0) {
          dp[i][j] = 1000000000;
          road[i][j] = 1000000000;
        }
      }
    }
    // 頂点0に繋がる道を削除する
    for(int i = 1; i < N; i++) {
      dp[0][i] = 1000000000;
      dp[i][0] = 1000000000;
    }
    // ワーシャル・フロイド
    for(int k = 1; k <= N; k++) {
      for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++) {
          dp[i][j] = Math.min(dp[i][j], dp[i][k - 1] + dp[k - 1][j]);
        }
      }
    }
    // 閉路の最短距離
    long min = Long.MAX_VALUE;
    for(int i = 1; i < N; i++) {
      for(int j = 1; j < N; j++) {
        if(i != j) {
          min = Math.min(min, road[0][i] + road[0][j] + dp[i][j]);
        }
      }
    }
    if(min > 100000000) min = -1;
    System.out.println(min);
  }
}

AC

21:正直者の高橋くん

全点対最短距離をワーシャル・フロイドにより求め、それを基に最短路DAGを構成する。DAGからDPにより最短経路の個数を求めていく。

import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int a = sc.nextInt() - 1;
    int b = sc.nextInt() - 1;
    int M = sc.nextInt();
    int[] x = new int[M];
    int[] y = new int[M];
    long MOD = 1000000007;
    int[][] dp = new int[N][N];
    for(int i = 0; i < M; i++) {
      x[i] = sc.nextInt() - 1;
      y[i] = sc.nextInt() - 1;
      dp[x[i]][y[i]] = 1;
      dp[y[i]][x[i]] = 1;
    }
    for(int i = 0; i < N; i++) {
      for(int j = 0; j < N; j++) {
        if(i != j && dp[i][j] == 0) dp[i][j] = 1000;
      }
    }
    // ワーシャル・フロイド
    for(int k = 1; k <= N; k++) {
      for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++) {
          dp[i][j] = Math.min(dp[i][j], dp[i][k - 1] + dp[k - 1][j]);
        }
      }
    }
    // 最短路DAG
    int[][] dag = new int[N][N];
    for(int i = 0; i < M; i++) {
      if(dp[a][x[i]] == dp[a][y[i]] + 1) dag[y[i]][x[i]] = 1;
      if(dp[a][x[i]] == dp[a][y[i]] - 1) dag[x[i]][y[i]] = 1; 
    }
    // 最短距離マップ
    HashMap<Integer, ArrayList<Integer>> map = new HashMap<Integer, ArrayList<Integer>>();
    for(int i = 0; i < N; i++) {
      int d = dp[a][i];
      if(map.containsKey(d)) {
        ArrayList<Integer> list = map.get(d);
        list.add(i);
        map.put(d, list);
      } else {
        ArrayList<Integer> list = new ArrayList<Integer>();
        list.add(i);
        map.put(d, list);
      }
    }
    long[] minStep = new long[N];
    minStep[a] = 1;
    for(int i = 0; i < dp[a][b]; i++) {
      ArrayList<Integer> list = map.get(i);
      for(int j = 0; j < list.size(); j++) {
        int town = list.get(j);
        for(int k = 0; k < N; k++) {
          if(dag[town][k] == 1) minStep[k] = (minStep[k] + minStep[town]) % MOD;
        }
      } 
    }
    System.out.println(minStep[b]);
  }
}

AC

2017-03-21

AtCoder Beginner Contest C問題

13:07

54:One-stroke Path

DFS(深さ優先探索)で全順列を列挙する。まだDFSの記述に慣れていないので、練習が必要である。

import java.util.*;

public class Main {
  static int N = 0;
  static int[][] edge;
  static int ans = 0;
  static int[] permutation = new int[8];
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    N = sc.nextInt();
    edge = new int[N][N];
    int M = sc.nextInt();
    for(int i = 0; i < M; i++) {
      int a = sc.nextInt() - 1;
      int b = sc.nextInt() - 1;
      edge[a][b] = 1;
      edge[b][a] = 1;
    }
    dfs(1, 1);
    System.out.println(ans);
  }

  public static void dfs(int pos, int mask) {
    if(pos == N) {
      int count = 0;
      for(int i = 0; i < N - 1; i++) {
        if(edge[permutation[i]][permutation[i + 1]] == 0) count++;
      }
      if(count == 0) ans++;
    } else {
      for(int i = 0; i < N; i++) {
        if((mask & (1 << i)) == 0) {
          permutation[pos] = i;
          dfs(pos + 1, mask ^ (1 << i));
        } 
      }
    }
  }
}

AC

49:白昼夢 / Daydream

Sの後ろから見ていけば、結合が一意的に定まる事が分かる。よって、Sの後ろから結合出来るか否かを判定していく。

import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    String S = sc.next();
    int pos = S.length();
    String ans = "YES";
    while(pos > 0) {
      String s5 = "";
      String s6 = "";
      String s7 = "";
      int count = 0;
      if(pos - 7 >= 0) {
        s7 = S.substring(pos - 7, pos);
        s6 = S.substring(pos - 6, pos);
        s5 = S.substring(pos - 5, pos);
        if(s7.equals("dreamer")) {
          pos -= 7;
          count++;
        } else if(s6.equals("eraser")) {
          pos -= 6;
          count++;
        } else if(s5.equals("dream") || s5.equals("erase")) {
          pos -= 5;
          count++;
        }
      } else if(pos - 6 >= 0) {
        s6 = S.substring(pos - 6, pos);
        s5 = S.substring(pos - 5, pos);
        if(s6.equals("eraser")) {
          pos -= 6;
          count++;
        } else if(s5.equals("dream") || s5.equals("erase")) {
          pos -= 5;
          count++;
        }
      } else if(pos - 5 >= 0) {
        s5 = S.substring(pos - 5, pos);
        if(s5.equals("dream") || s5.equals("erase")) {
          pos -= 5;
          count++;
        }
      }
      if(count == 0) {
        ans = "NO";
        break;
      }
    }
    System.out.println(ans);
  }
}

AC

46:AtCoDeerくんと選挙速報 / AtCoDeer and Election Report

a/bの切り上げは(a+b-1)/bによって行う。Math.ceilはあまり使わないほうが良い。

import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    long[] t = new long[N];
    long[] a = new long[N];
    for(int i = 0; i < N; i++) {
      t[i] = sc.nextLong();
      a[i] = sc.nextLong();
    }
    // (i+1)回目の最小票数を(t[i]*dp[i],a[i]*dp[i])とする
    long[] dp = new long[N];
    dp[0] = 1;
    for(int i = 1; i < N; i++) {
      long takahashi = (t[i - 1] * dp[i - 1] + t[i] - 1) / t[i];
      long aoki = (a[i - 1] * dp[i - 1] + a[i] - 1) / a[i];
      dp[i] = Math.max(takahashi, aoki); 
    }
    System.out.println((t[N - 1] + a[N - 1]) * dp[N - 1]);
  }
}

AC

42:こだわり者いろはちゃん / Iroha's Obsession

答えはN~100Nに存在するので、全探索すれば良い。

import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int K = sc.nextInt();
    ArrayList<Integer> dislike = new ArrayList<Integer>();
    for(int i = 0; i < K; i++) {
      dislike.add(sc.nextInt());
    }
    int ans = N;
    for(int i = N; i < 100 * N; i++) {
      int count = 0;
      int temp = i;
      while(temp > 0) {
        int digit = temp % 10;
        temp /= 10;
        if(dislike.contains(digit)) count++;
      }
      if(count == 0) {
        ans = i;
        break;
      }
    }
    System.out.println(ans);
  }
}

AC

37:総和

いもす法の練習問題。計算量はO(N)となり間に合う。

import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int K = sc.nextInt();
    long[] a = new long[N];
    for(int i = 0; i < N; i++) {
      a[i] = sc.nextLong();
    }
    long[] b = new long[N];
    for(int i = 0; i < N - K + 1; i++) {
      b[i]++;
      if(i + K < N) b[i + K]--;
    }
    long sum = a[0] * b[0];
    for(int i = 1; i < N; i++) {
      b[i] += b[i - 1];
      sum += a[i] * b[i];
    }
    System.out.println(sum);
  }
}

AC

36:座圧

座標圧縮は連想配列(HashMap)を使って行う。

import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    HashMap<Integer, ArrayList<Integer>> map = new HashMap<Integer, ArrayList<Integer>>();
    for(int i = 0; i < N; i++) {
      int a = sc.nextInt();
      if(map.containsKey(a)) {
        ArrayList<Integer> list = map.get(a);
        list.add(i);
        map.put(a, list);
      } else {
        ArrayList<Integer> list = new ArrayList<Integer>();
        list.add(i);
        map.put(a, list);
      }
    }
    ArrayList<Integer> key = new ArrayList<>(map.keySet());
    Collections.sort(key);
    int[] b = new int[N];
    for(int i = 0; i < key.size(); i++) {
      int a = key.get(i);
      ArrayList<Integer> list = map.get(a);
      for(int j = 0; j < list.size(); j++) {
        b[list.get(j)] = i;
      }
    }
    for(int i = 0; i < N; i++) {
      System.out.println(b[i]);
    }
  }
}

AC

35:オセロ

いもす法の練習問題。

import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int Q = sc.nextInt();
    int[] board = new int[N];
    for(int i = 0; i < Q; i++) {
      int l = sc.nextInt() - 1;
      int r = sc.nextInt();
      board[l]++;
      if(r < N) board[r]--;
    }
    if(board[0] % 2 == 0) {
      System.out.print("0");
    } else {
      System.out.print("1");
    }
    for(int i = 1; i < N; i++) {
      board[i] += board[i - 1];
      if(board[i] % 2 == 0) {
        System.out.print("0");
      } else {
        System.out.print("1");
      }
    }
    System.out.println();
  }
}

AC

34:経路

aのmod 1000000007(=MOD)における逆元はフェルマーの小定理より、a^(MOD-2)となる。a^(MOD-2)は繰り返し二乗法よりO(logMOD)で計算出来る。

import java.util.*;

public class Main {
  static long MOD = 1000000007;
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    long W = sc.nextLong();
    long H = sc.nextLong();
    long r1 = 1;
    long r2 = 1;
    for(long i = 1; i < H; i++) {
      r1 = (r1 * (W + i - 1)) % MOD;
      r2 = (r2 * i) % MOD;
    }
    long inverse = func(r2, MOD - 2);
    System.out.println((r1 * inverse) % MOD);
  }

  public static long func(long a, long x) {
    if(x == 0) return 1;
    if(x % 2 == 0) {
      long t = func(a, x / 2);
      return (t * t) % MOD; 
    } else {
      long t = func(a, x / 2);
      t = (t * t) % MOD;
      return (a * t) % MOD;
    }
  }
}

AC

32:列

しゃくとり法の練習問題。計算量はO(N)なので間に合う。

import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int K = sc.nextInt();
    long[] s = new long[N];
    int count = 0;
    for(int i = 0; i < N; i++) {
      s[i] = sc.nextLong();
      if(s[i] == 0) count++;
    }
    long prod = 1;
    int ans = 0;
    if(count > 0) {
      ans = N;
    } else {
      int start = 0;
      int end = 0;
      while(end < N) {
        prod *= s[end];
        if(prod <= K) {
          end++;
          ans = Math.max(ans, end - start);
        } else {
          prod /= s[end];
          if(start == end) {
            start++;
            end++;
          } else {
            prod /= s[start];
            start++;
          }
        }
      }
    }
    System.out.println(ans);
  }
}

AC

30:飛行機乗り

現時刻で乗れる直近のフライトを二分探索で探す。計算量はO((N+M)*20)で間に合う。

import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int M = sc.nextInt();
    int X = sc.nextInt();
    int Y = sc.nextInt();
    int[] a = new int[N];
    int[] b = new int[M];
    for(int i = 0; i < N; i++) {
      a[i] = sc.nextInt();
    }
    for(int i = 0; i < M; i++) {
      b[i] = sc.nextInt();
    }
    int time = 0;
    int airport = 0;
    int ans = 0;
    while(time <= 1000000000) {
      if(airport == 0) {
        int l = 0;
        int r = N;
        int flight = -1;
        while(l < r) {
          int med = (l + r) / 2;
          if(a[med] >= time) {
            flight = med;
            r = med;
          } else {
            l = med + 1;
          }
        }
        if(flight == -1) {
          break;
        } else {
          time = a[flight] + X;
          airport = 1;
        }
      } else {
        int l = 0;
        int r = M;
        int flight = -1;
        while(l < r) {
          int med = (l + r) / 2;
          if(b[med] >= time) {
            flight = med;
            r = med;
          } else {
            l = med + 1;
          }
        }
        if(flight == -1) {
          break;
        } else {
          time = b[flight] + Y;
          airport = 0;
          ans++;
        }
      }
    }
    System.out.println(ans);
  }
}

AC

AtCoder Beginner Contest055

11:35

A:Restaurant

import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int x = 800 * N;
    int y = 200 * (N / 15);
    System.out.println(x - y);
  }
}

AC

B:Training Camp

import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    long ans = 1;
    for(int i = 1; i <= N; i++) {
      ans = (ans * (long)i) % 1000000007;
    }
    System.out.println(ans);
  }
}

AC

C:Scc Puzzle

出来るだけ元々あるSを使うようにする事が最適なGreedy戦略である。

import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    long N = sc.nextLong();
    long M = sc.nextLong();
    long ans = 0;
    if(2 * N <= M) {
      ans = N;
      M -= 2 * N;
      ans += M / 4;
    } else {
      ans = M / 2;
    }
    System.out.println(ans);
  }
}

AC

AtCoder Beginner Contest020 AB問題

10:48

A:クイズ

import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int Q = sc.nextInt();
    String ans = "ABC";
    if(Q == 2) ans = "chokudai";
    System.out.println(ans);
  }
}

AC

B:足し算

import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int A = sc.nextInt();
    int B = sc.nextInt();
    int ans = 0;
    if(B < 10) {
      ans = 10 * A + B;
    } else if(B < 100) {
      ans = 100 * A + B;
    } else {
      ans = 1000 * A + B;
    }
    System.out.println(ans * 2);
  }
}

AC

AtCoder Beginner Contest021 AB問題

10:24

A:足し算

import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int[] power = {1, 2, 4, 8};
    ArrayList<Integer> ans = new ArrayList<Integer>();
    while(N > 0) {
      for(int i = 3; i >= 0; i--) {
        if(N >= power[i]) {
          ans.add(power[i]);
          N -= power[i];
          break;
        }
      }
    }
    System.out.println(ans.size());
    for(int i = 0; i < ans.size(); i++) {
      System.out.println(ans.get(i));
    }
  }
}

AC

B:嘘つきの高橋くん

import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int a = sc.nextInt();
    int b = sc.nextInt();
    int K = sc.nextInt();
    HashSet<Integer> set = new HashSet<Integer>();
    set.add(a);
    set.add(b);
    for(int i = 0; i < K; i++) {
      int p = sc.nextInt();
      set.add(p);
    }
    String ans = "NO";
    if(set.size() == K + 2) ans = "YES";
    System.out.println(ans);
  }
}

AC

AtCoder Beginner Contest022 AB問題

10:00

A:Best Body

import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int S = sc.nextInt();
    int T = sc.nextInt();
    int W = sc.nextInt();
    int[] a = new int[N];
    a[0] = 0;
    for(int i = 1; i < N; i++) {
      a[i] = sc.nextInt();
    }
    int ans = 0;
    for(int i = 0; i < N; i++) {
      W += a[i];
      if(W >= S && W <= T) ans++;
    }
    System.out.println(ans);
  }
}

AC

B:Bumble Bee

import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int[] flower = new int[100001];
    int ans = 0;
    for(int i = 0; i < N; i++) {
      int a = sc.nextInt();
      if(flower[a] > 0) ans++;
      flower[a]++;
    }
    System.out.println(ans);
  }
}

AC

2017-03-20

AtCoder Beginner Contest C問題

09:36

22:Blue Bird

最初に、街1に繋がる道を通らない全点対最短距離dpをワーシャル・フロイドで求めておく。次に、街1以外の任意の2つの街(i,j)のペアを考え、閉路の最短距離をdist(1,i)+dist(1,j)+dp(i,j)で更新していく。

import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int M = sc.nextInt();
    long[][] dp = new long[N][N];
    for(int i = 0; i < M; i++) {
      int u = sc.nextInt() - 1;
      int v = sc.nextInt() - 1;
      long l = sc.nextLong();
      dp[u][v] = l;
      dp[v][u] = l;
    }
    for(int i = 0; i < N; i++) {
      for(int j = 0; j < N; j++) {
        if(i != j && dp[i][j] == 0) dp[i][j] = 100000000;
      }
    }
    long[] dis = new long[N];
    for(int i = 1; i < N; i++) {
      dis[i] = dp[0][i];
      dp[0][i] = 100000000;
    }
    for(int k = 1; k <= N; k++) {
      for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++) {
          dp[i][j] = Math.min(dp[i][j], dp[i][k - 1] + dp[k - 1][j]);
        }
      }
    }
    long min = Long.MAX_VALUE;
    for(int i = 1; i < N; i++) {
      for(int j = 1; j < N; j++) {
        if(i != j) min = Math.min(min, dis[i] + dis[j] + dp[i][j]);
      }
    }
    if(min >= 100000000) min = -1;
    System.out.println(min);
  }
}

AC

20:壁抜け

部分点解法(40/100):2 ≦ H, W ≦ 3, 2 ≦ T ≦ 30

DFS(深さ優先探索)で全ての経路を探索すれば良い。

import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int H = sc.nextInt();
    int W = sc.nextInt();
    int T = sc.nextInt();
    char[][] maze = new char[H][W];
    int[] start = new int[2];
    int[] goal = new int[2];
    int[][] mask = new int[H][W];
    for(int i = 0; i < H; i++) {
      String s = sc.next();
      for(int j = 0; j < W; j++) {
        maze[i][j] = s.charAt(j);
        if(maze[i][j] == 'S') {
          start[0] = i;
          start[1] = j;
        }
        if(maze[i][j] == 'G') {
          goal[0] = i;
          goal[1] = j;
        }
      }
    }
    mask[start[0]][start[1]] = 1;
    int ans = 0;
    for(int x = T - 1; x >= 1; x--) {
      if(dfs(H, W, maze, mask, start, goal, x, T)) {
        ans = x;
        break;
      }
    }
    System.out.println(ans);
  }
  
  // startからgoalまでT秒以内に移動出来るかどうかを返す(黒マスへの移動にx秒かかるとする)
  public static boolean dfs(int H, int W, char[][] maze, int[][] mask, int[] start, int[] goal, int x, int T) {
    if(Arrays.equals(start, goal)) {
      if(T >= 0) {
        return true;
      } else {
        return false;
      }
    } else {
      int Y = start[0];
      int X = start[1];
      int[] movey = {-1, 0, 1, 0};
      int[] movex = {0, 1, 0, -1};
      boolean flg = false;
      for(int i = 0; i < 4; i++) {
        int move1 = Y + movey[i];
        int move2 = X + movex[i];
        int[] s = {move1, move2};
        if(move1 >= 0 && move1 < H && move2 >= 0 && move2 < W && mask[move1][move2] == 0) {
          int t = 0;
          if(maze[move1][move2] == '#') {
            t = x;
          } else {
            t = 1;
          }
          mask[move1][move2] = 1;
          boolean f = dfs(H, W, maze, mask, s, goal, x, T - t);
          mask[move1][move2] = 0;
          flg = flg || f;
        }
      }
      return flg;
    }
  }
}

AC

部分点解法(70/100):2 ≦ T ≦ 30

マスが100個あるので、DFSは使えない。代わりにワーシャル・フロイドを使う。計算量は高々3*10^7で間に合う。

import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int H = sc.nextInt();
    int W = sc.nextInt();
    int T = sc.nextInt();
    char[] maze = new char[H * W];
    int start = 0;
    int goal = 0;
    for(int i = 0; i < H; i++) {
      String s = sc.next();
      for(int j = 0; j < W; j++) {
        maze[i * W + j] = s.charAt(j);
        if(maze[i * W + j] == 'S') {
          start = i * W + j;
        }
        if(maze[i * W + j] == 'G') {
          goal = i * W + j;
        }
      }
    }
    int ans = 0;
    for(int x = T - 1; x >= 1; x--) {
      long[][] dp = new long[H * W][H * W];
      for(int i = 0; i < H * W; i++) {
        for(int j = 0; j < H * W; j++) {
          if(i % W == 0) {
            if(i == 0) {
              if(j == i + 1 || j == i + W) {
                if(maze[j] == '#') {
                  dp[i][j] = x;
                } else {
                  dp[i][j] = 1;
                }
              } else {
                if(i != j) dp[i][j] = 1000000; 
              }
            } else if(i == (H - 1) * W) {
              if(j == i + 1 || j == i - W) {
                if(maze[j] == '#') {
                  dp[i][j] = x;
                } else {
                  dp[i][j] = 1;
                }
              } else {
                if(i != j) dp[i][j] = 1000000; 
              }
            } else {
              if(j == i + 1 || j == i + W || j == i - W) {
                if(maze[j] == '#') {
                  dp[i][j] = x;
                } else {
                  dp[i][j] = 1;
                }
              } else {
                if(i != j) dp[i][j] = 1000000; 
              }
            }
          } else if(i % W == W - 1) {
            if(i == W - 1) {
              if(j == i - 1 || j == i + W) {
                if(maze[j] == '#') {
                  dp[i][j] = x;
                } else {
                  dp[i][j] = 1;
                }
              } else {
                if(i != j) dp[i][j] = 1000000; 
              }
            } else if(i == H * W - 1) {
              if(j == i - 1 || j == i - W) {
                if(maze[j] == '#') {
                  dp[i][j] = x;
                } else {
                  dp[i][j] = 1;
                }
              } else {
                if(i != j) dp[i][j] = 1000000; 
              }
            } else {
              if(j == i - 1 || j == i + W || j == i - W) {
                if(maze[j] == '#') {
                  dp[i][j] = x;
                } else {
                  dp[i][j] = 1;
                }
              } else {
                if(i != j) dp[i][j] = 1000000; 
              }
            }
          } else {
            if(i < W - 1) {
              if(j == i - 1 || j == i + 1 || j == i + W) {
                if(maze[j] == '#') {
                  dp[i][j] = x;
                } else {
                  dp[i][j] = 1;
                }
              } else {
                if(i != j) dp[i][j] = 1000000; 
              }
            } else if(i > (H - 1) * W) {
              if(j == i - 1 || j == i + 1 || j == i - W) {
                if(maze[j] == '#') {
                  dp[i][j] = x;
                } else {
                  dp[i][j] = 1;
                }
              } else {
                if(i != j) dp[i][j] = 1000000; 
              }
            } else {
              if(j == i - 1 || j == i + 1 || j == i + W || j == i - W) {
                if(maze[j] == '#') {
                  dp[i][j] = x;
                } else {
                  dp[i][j] = 1;
                }
              } else {
                if(i != j) dp[i][j] = 1000000; 
              }
            }
          }
        }
      }
      // ワーシャル・フロイド
      for(int k = 1; k <= H * W; k++) {
        for(int i = 0; i < H * W; i++) {
          for(int j = 0; j < H * W; j++) {
            dp[i][j] = Math.min(dp[i][j], dp[i][k - 1] + dp[k - 1][j]);
          }
        }
      }
      if(dp[start][goal] <= T) {
        ans = x;
        break;
      }
    }
    System.out.println(ans);
  }
}

AC

満点解法(100/100)

条件を満たすxは単調性があるので、二分探索すれば良い。計算量は高々3*10^7で間に合う。

import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int H = sc.nextInt();
    int W = sc.nextInt();
    int T = sc.nextInt();
    char[] maze = new char[H * W];
    int start = 0;
    int goal = 0;
    for(int i = 0; i < H; i++) {
      String s = sc.next();
      for(int j = 0; j < W; j++) {
        maze[i * W + j] = s.charAt(j);
        if(maze[i * W + j] == 'S') {
          start = i * W + j;
        }
        if(maze[i * W + j] == 'G') {
          goal = i * W + j;
        }
      }
    }
    int ans = 0;
    int l = 1;
    int r = T;
    while(l < r) {
      int med = (l + r) / 2;
      long[][] dp = new long[H * W][H * W];
      for(int i = 0; i < H * W; i++) {
        for(int j = 0; j < H * W; j++) {
          if(i % W == 0) {
            if(i == 0) {
              if(j == i + 1 || j == i + W) {
                if(maze[j] == '#') {
                  dp[i][j] = med;
                } else {
                  dp[i][j] = 1;
                }
              } else {
                if(i != j) dp[i][j] = (long)Math.pow(10, 12); 
              }
            } else if(i == (H - 1) * W) {
              if(j == i + 1 || j == i - W) {
                if(maze[j] == '#') {
                  dp[i][j] = med;
                } else {
                  dp[i][j] = 1;
                }
              } else {
                if(i != j) dp[i][j] = (long)Math.pow(10, 12); 
              }
            } else {
              if(j == i + 1 || j == i + W || j == i - W) {
                if(maze[j] == '#') {
                  dp[i][j] = med;
                } else {
                  dp[i][j] = 1;
                }
              } else {
                if(i != j) dp[i][j] = (long)Math.pow(10, 12); 
              }
            }
          } else if(i % W == W - 1) {
            if(i == W - 1) {
              if(j == i - 1 || j == i + W) {
                if(maze[j] == '#') {
                  dp[i][j] = med;
                } else {
                  dp[i][j] = 1;
                }
              } else {
                if(i != j) dp[i][j] = (long)Math.pow(10, 12); 
              }
            } else if(i == H * W - 1) {
              if(j == i - 1 || j == i - W) {
                if(maze[j] == '#') {
                  dp[i][j] = med;
                } else {
                  dp[i][j] = 1;
                }
              } else {
                if(i != j) dp[i][j] = (long)Math.pow(10, 12); 
              }
            } else {
              if(j == i - 1 || j == i + W || j == i - W) {
                if(maze[j] == '#') {
                  dp[i][j] = med;
                } else {
                  dp[i][j] = 1;
                }
              } else {
                if(i != j) dp[i][j] = (long)Math.pow(10, 12); 
              }
            }
          } else {
            if(i < W - 1) {
              if(j == i - 1 || j == i + 1 || j == i + W) {
                if(maze[j] == '#') {
                  dp[i][j] = med;
                } else {
                  dp[i][j] = 1;
                }
              } else {
                if(i != j) dp[i][j] = (long)Math.pow(10, 12); 
              }
            } else if(i > (H - 1) * W) {
              if(j == i - 1 || j == i + 1 || j == i - W) {
                if(maze[j] == '#') {
                  dp[i][j] = med;
                } else {
                  dp[i][j] = 1;
                }
              } else {
                if(i != j) dp[i][j] = (long)Math.pow(10, 12); 
              }
            } else {
              if(j == i - 1 || j == i + 1 || j == i + W || j == i - W) {
                if(maze[j] == '#') {
                  dp[i][j] = med;
                } else {
                  dp[i][j] = 1;
                }
              } else {
                if(i != j) dp[i][j] = (long)Math.pow(10, 12); 
              }
            }
          }
        }
      }
      // ワーシャル・フロイド
      for(int k = 1; k <= H * W; k++) {
        for(int i = 0; i < H * W; i++) {
          for(int j = 0; j < H * W; j++) {
            dp[i][j] = Math.min(dp[i][j], dp[i][k - 1] + dp[k - 1][j]);
          }
        }
      }
      if(dp[start][goal] <= T) {
        ans = med;
        l = med + 1;
      } else {
        r = med;
      }
    }
    System.out.println(ans);
  }
}

AC

21:正直者の高橋くん

全点対最短距離をワーシャル・フロイドで求め、最短路DAG(有向グラフで閉路を持たないもの)を構成する。そして最短経路の個数をDPにより求めていく。

import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int a = sc.nextInt() - 1;
    int b = sc.nextInt() - 1;
    int M = sc.nextInt();
    int[] x = new int[M];
    int[] y = new int[M];
    int[][] dp = new int[N][N];
    for(int i = 0; i < M; i++) {
      x[i] = sc.nextInt() - 1;
      y[i] = sc.nextInt() - 1;
      dp[x[i]][y[i]] = 1;
      dp[y[i]][x[i]] = 1;
    }
    for(int i = 0; i < N; i++) {
      for(int j = 0; j < N; j++) {
        if(i != j && dp[i][j] == 0) dp[i][j] = 1000;
      }
    }
    // ワーシャル・フロイド
    for(int k = 1; k <= N; k++) {
      for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++) {
          dp[i][j] = Math.min(dp[i][j], dp[i][k - 1] + dp[k - 1][j]);
        }
      }
    }
    // 最短路DAG
    int[][] dag = new int[N][N];
    for(int i = 0; i < M; i++) {
      if(dp[a][x[i]] == dp[a][y[i]] + 1) dag[y[i]][x[i]] = 1;
      if(dp[a][x[i]] == dp[a][y[i]] - 1) dag[x[i]][y[i]] = 1;
    }
    // 最短距離Map
    HashMap<Integer, ArrayList<Integer>> map = new HashMap<Integer, ArrayList<Integer>>();
    for(int i = 0; i < N; i++) {
      int dist = dp[a][i];
      if(map.containsKey(dist)) {
        ArrayList<Integer> list = map.get(dist);
        list.add(i);
        map.put(dist, list);
      } else {
        ArrayList<Integer> list = new ArrayList<Integer>();
        list.add(i);
        map.put(dist, list);
      }
    }
    // 最短経路の数
    long[] dp2 = new long[N];
    dp2[a] = 1;
    int d = dp[a][b];
    long MOD = 1000000007;
    for(int i = 0; i < d; i++) {
      ArrayList<Integer> list = map.get(i);
      for(int j = 0; j < list.size(); j++) {
        int v = list.get(j);
        for(int k = 0; k < N; k++) {
          if(dag[v][k] == 1) dp2[k] = (dp2[k] + dp2[v]) % MOD;
        }
      }
    }
    System.out.println(dp2[b]);
  }
}

AC