Local Onsite - tsubosakaの日記

行ってきた。Dのsmallしか解けず惨敗。

D

木が2つ与えられた時に、木Aが木Bに含まれているかどうか判定せよという問題。
smallはNが8個しかないので8!通りラベルづけを試せばよい。
largeはルートをそれぞれの木に対して決めた後、Aのそれぞれの部分木がそれぞれのBの部分木に含まれているかで二部グラフを作ってマッチングが存在していればAはBに含まれているというのを部分木に対して再帰的に計算していけばよいらしい。
(追記)とりあえず上の方針でコードを書いてみたところlargeの入力に対して1分かからなかった。
計算量に関してはおおざっぱに見積もると入力がバランスされたk分木だとした場合

T(n) = k^2 T(n / k) + O(k^3 (マッチングの計算量))

でkを定数とするとT(n) =n^2 lg n でそれ掛けるn^2でn <= 100なら、nが小さいテストケースもかなり入っているので間に合う。

C

5 * 1000000 * 1000000のDPとかしか思いつかなかった。

B

問題を読んでないんだが解いた人から聞くと全探索で間に合うらしい。
(追記)問題文どおりに各ターンをシミュレーションして自分の5通りの選択肢については全探索で書くと3秒程度でlargeのデータセットが通った、あと探索は最も長く生き残れる手を探したいので深さ優先でよい。
出力をみるとforeverでない場合は長くても9ターンしか生き残れないので5^9ぐらいしか分岐をみてないようです。
(さらに追記)問題文をよく読むと5通りではなくて、攻撃する際に相手へのダメージを選択することができて分岐はもっと多くなるのですが、実は最適手順は何もしないかMAXで4方向のどれかに攻撃するかの5通りだけで書けて、この条件に気付かなかった人のほうが有利だったかもしれない。(largeの場合与えるダメージも考えると1+4*1000通りの選び方があって、これだと間に合わない)(つっこみが入ったけどフルパワーでしか攻撃できないです)

A

間違った方針でコードを書いてしまって死亡。方針としてはBIRDに関してバウンディングボックスを作ってその中であればBIRDと判定。そうでないとき、質問点を入れてバウンディングボックスを拡大して、その中にNON BIRDが入っているかどうか判定、入っていればNON BIRDそうでなければUNKNOWN
とりあえずAだけ書き直した。方針をうまく定めておいたら意外と簡潔に書けた。
A.java

import java.util.*;
import static java.lang.Math.*;

class Point {
  int x, y;
  Point(int a, int b) {
    x = a;y = b;
  }
}

public class A {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);  
    int C = sc.nextInt();
    for(int i = 1 ; i <= C ; i++){
      int N = sc.nextInt();
      System.out.println("Case #"+i+":");
      List<Point> nonBirds = new ArrayList<Point>();
      int birdBound[] = new int[4];
      birdBound[0] = birdBound[1] = Integer.MAX_VALUE;
      for(int j = 0 ; j < N ; j++){
        int x = sc.nextInt();
        int y = sc.nextInt();
        String s = sc.next();
        Point p = new Point(x , y);
        if(s.equals("BIRD")){
          birdBound = extendBox(birdBound, p);
        }else{
          sc.next();
          nonBirds.add(p);
        }
      }
      int M = sc.nextInt();
      List<Point> query = new ArrayList<Point>();
      for(int j = 0 ; j < M ; j++){
        query.add(new Point(sc.nextInt() , sc.nextInt()));
      }
      for(Point q : query){
        if(inBox(birdBound, q)){
          System.out.println("BIRD");          
        }else{
          boolean notBird = false;
          int[] extendBox = extendBox(birdBound, q);
          for(Point nb : nonBirds){
            if(inBox(extendBox, nb)){
              notBird = true;
              break;
            }
          }
          if(notBird){
            System.out.println("NOT BIRD");
          }else{
            System.out.println("UNKNOWN");
          }
        }
      }
    }
  }

  static boolean inBox(int birdBound[], Point q) {
    return birdBound[0] <= q.x && q.x <= birdBound[2] 
        && birdBound[1] <= q.y && q.y <= birdBound[3];
  }

  static int[] extendBox(int box[], Point p) {
    int res[] = new int[4];
    res[0] = min(p.x, box[0]); res[1] = min(p.y, box[1]);
    res[2] = max(p.x, box[2]); res[3] = max(p.y, box[3]);
    return res;
  }
}

D.java

import java.util.*;

class Vertex implements Iterable<Integer>{
  List<Integer> adjoint;
  Vertex(){
    adjoint = new ArrayList<Integer>();
  }
  void add(int e){
    adjoint.add(e);
  }
  @Override
  public Iterator<Integer> iterator() {
    return adjoint.iterator();
  }
  int size(){
    return adjoint.size();
  }
}
public class D {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int C = sc.nextInt();
    for(int cn = 1 ; cn <= C ; cn++){
      int N = sc.nextInt();
      Vertex lTree[] = new Vertex[N];
      for(int i = 0 ; i < N ; i++)
        lTree[i] = new Vertex();
      for(int i = 0 ; i < N - 1 ; i++){
        int a = sc.nextInt() - 1;
        int b = sc.nextInt() - 1;
        lTree[a].add(b);
        lTree[b].add(a);
      }
      int M = sc.nextInt();      
      Vertex sTree[] = new Vertex[M];
      for(int i = 0 ; i < M ; i++)
        sTree[i] = new Vertex();
      for(int i = 0 ; i < M - 1 ; i++){
        int a = sc.nextInt() - 1;
        int b = sc.nextInt() - 1;
        sTree[a].add(b);
        sTree[b].add(a);
      }
      boolean f = false;
      for(int lRoot = 0 ; lRoot < lTree.length ; lRoot++){
        for(int sRoot = 0 ; sRoot < sTree.length ; sRoot++){
          if(isPart(lTree, -1, lRoot, sTree, -1, sRoot)){
            f = true;
            break;
          }
        }
        if(f)break;
      }
      System.out.printf("Case #%d: %s\n", cn , f ? "YES" : "NO");
    }
  }
  static boolean isPart(Vertex[] lT , int lparent , int lpos , Vertex[] sT , int sparent , int spos){
    Vertex lp = lT[lpos];
    Vertex sp = sT[spos];
    int lsub = lp.size();
    int ssub = sp.size();
    lsub -= lparent < 0 ? 0 : 1;
    ssub -= lparent < 0 ? 0 : 1;
    if(lsub < ssub)return false;
    if(ssub == 0)return true;
    boolean g[][] = new boolean[lsub + ssub][lsub + ssub];
    int li = 0;
    for(int a : lp){
      if(a == lparent)continue;
      int si = 0;
      for(int b : sp){
        if(b == sparent)continue;
        g[li][lsub + si] = isPart(lT, lpos, a, sT, spos, b);
        si++;
      }
      li++;
    }
    return bipartite_matching(g, lsub) == ssub;
  }
  static int bipartite_matching(boolean adj[][], int leftSize) {
    int match = 0;
    int matchTo[] = new int[adj.length];
    Arrays.fill(matchTo, -1);
    boolean visited[] = new boolean[adj.length];
    for (int u = 0; u < leftSize; u++) {
      Arrays.fill(visited, false);
      if (augment(adj, u, matchTo, visited))
        match++;
    }
    return match;
  }

  static boolean augment(boolean adj[][], int u, int matchTo[], boolean visited[]) {
    if (u < 0)
      return true;
    for(int i = 0 ; i < adj[u].length ; i++){
      if(adj[u][i] && !visited[i]){
        visited[i] = true;
        if (augment(adj, matchTo[i], matchTo, visited)) {
          matchTo[u] = i;
          matchTo[i] = u;
          return true;
        }        
      }
    }
    return false;
  }
}

B.java

import java.util.Scanner;

public class B {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);    
    int N = sc.nextInt();
    for(int i = 1 ; i <= N ; i++){
      int C = sc.nextInt();
      int R = sc.nextInt();
      int c = sc.nextInt() - 1;
      int r = sc.nextInt() - 1;
      int map[][] = new int[R][C];
      for(int j = 0 ; j < map.length ; j++)
        for(int k = 0 ; k < map[j].length ; k++)
          map[j][k] = sc.nextInt();
      res = 0;
      dfs(c, r, 0, map);
      if(res == Integer.MAX_VALUE){
        System.out.printf("Case #%d: forever\n", i);        
      }else{
        System.out.printf("Case #%d: %d day(s)\n", i , res);        
      }
    }
  }
  static int res;
  static int dx[] = { 0 , -1 , 1 , 0};
  static int dy[] = {-1 , 0 , 0 , 1 };
  static void dfs(int c , int r ,int depth, int map[][]){    
    if(res == Integer.MAX_VALUE)return ;
    boolean f = true;
    for(int k = 0 ; k < dx.length ; k++){
      int ax = c + dx[k];
      int ay = r + dy[k];
      if(ax < 0 || ay < 0 || ax >= map[0].length || ay >= map.length)continue;
      if(map[ay][ax] > 0){
        f = false;
        break;
      }
    }
    if(f){
      res = Integer.MAX_VALUE;
      return ;
    }
    int next[][] = new int[map.length][map[0].length];
    for(int i = 0 ; i < map.length ; i++)
      for(int j = 0 ; j < map[i].length ; j++)
        next[i][j] = map[i][j];
    for(int i = 0 ; i < map.length ; i++){
      for(int j = 0 ; j < map[i].length ; j++){
        if(i == r && j == c)continue;
        int mindex = 0;
        int max = -1;
        for(int k = 0 ; k < dx.length ; k++){
          int ax = j + dx[k];
          int ay = i + dy[k];
          if(ax < 0 || ay < 0 || ax >= map[0].length || ay >= map.length)continue;
          if(max < map[ay][ax]){
            mindex = k;
            max = map[ay][ax];
          }
        }
        next[i + dy[mindex]][j + dx[mindex]] = Math.max(0, next[i + dy[mindex]][j + dx[mindex]] - map[i][j]);
      }
    }
    if(next[r][c] == 0){
      res = Math.max(depth, res);
      return ;
    }
    dfs(c, r, depth + 1, next);
    for(int k = 0 ; k < dx.length ; k++){
      int ax = c + dx[k];
      int ay = r + dy[k];
      if(ax < 0 || ay < 0 || ax >= map[0].length || ay >= map.length)continue;
      int v = next[ay][ax];
      next[ay][ax] = Math.max(0, next[ay][ax] - map[r][c]);
      dfs(c, r, depth + 1, next);
      next[ay][ax] = v;
    }
  }
}

(追記)9/23:Dの解説とコードを追加
(追記)9/23:Bの解説とコードを追加