ログインしてさらにmixiを楽しもう

コメントを投稿して情報交換!
更新通知を受け取って、最新情報をゲット!

情報オリンピックコミュのIOI 2005 Garden

  • mixiチェック
  • このエントリーをはてなブックマークに追加
2005年のGardenです。

問題(日本語訳)
http://219.117.234.210/ioi/2005/problems.html

入力データ
http://contest.ioi2005.pl/testdata/

スレッドが一緒だと、解答もみてしまうので、分けました。
↓解き終わってからみよう♪↓

コメント(5)

import java.io.*;
import java.util.*;

public class Garden {
  public static void main(String[] args) throws Exception {
    new Garden();
  }
  
  private int[][] garden;
  private int l,w,n,k;
  private int[] xy, minXWidth, minYWidth;

  private int xWayMin;

  private Garden() throws Exception {
    BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    
    // 初期化
    String line;
    line = in.readLine();
    l = getFirst(line); w = getSecond(line);
    //System.out.println("l = " + l + ", w = " + w);

    line = in.readLine();
    n = getFirst(line); k = getSecond(line); // バラ数、囲う数
    //System.out.println("n = " + n + ", k = " + k);
    
    garden = new int[l + 1][w + 1];
    for(int i=0; i<n; i++) {
      line = in.readLine();
      int x = getFirst(line), y = getSecond(line);
      garden[x][y]++;
    }
    
    calc1();
    int xWayMinBackup = xWayMin;
    
    // XとYを入れ替える。
    int[][] garden2 = new int[w + 1][l + 1];
    for(int y = 1; y <= w; y++) {
      for(int x=1; x<=l; x++) {
        garden2[y][x] = garden[x][y];
      }
    }
    garden = garden2;
    
    int tmp = l;
    l = w;
    w = tmp;
    
    calc1();
    
    xWayMin = Math.min(xWayMin, xWayMinBackup);
    if(xWayMin == Integer.MAX_VALUE) System.out.println("NO");
    else System.out.println(xWayMin * 2);
  }
  
  private void calc1() {
    xy = new int[l + 1]; //minXWidth = new int[l + 1]; minYWidth = new int[l + 1];
    for(int i=1; i<xy.length; i++) xy[i] = Integer.MAX_VALUE;
    calc();
    
    for(int i=2; i<xy.length; i++) {
      if(xy[i-1] < xy[i]) {
        xy[i] = xy[i-1];
        //minXWidth[i] = minXWidth[i-1];
        //minYWidth[i] = minYWidth[i-1];
      }
    }
    /*
    for(int i=1; i<xy.length; i++)
      System.out.println("xy = " + xy[i] + ", minXWidth = " + minXWidth[i] + ", minYWidth = " + minYWidth[i]);
    */
    int[] fromRight = new int[l + 1];
    System.arraycopy(xy, 0, fromRight, 0, fromRight.length);

    // X方向を入れ替える。
    for(int y=1; y <= w; y++) {
      for(int x=1; x <= l/2; x++) {
        int tmp = garden[x][y];
        garden[x][y] = garden[l - x + 1][y];
        garden[l - x + 1][y] = tmp;
      }
    }

    for(int i=1; i<xy.length; i++) xy[i] = Integer.MAX_VALUE;
    calc();
    
    for(int i=2; i<xy.length; i++) {
      if(xy[i-1] < xy[i]) {
        xy[i] = xy[i-1];
        //minXWidth[i] = minXWidth[i-1];
        //minYWidth[i] = minYWidth[i-1];
      }
    }
    /*
    for(int i=1; i<xy.length; i++)
      System.out.println("xy = " + xy[i] + ", minXWidth = " + minXWidth[i] + ", minYWidth = " + minYWidth[i]);
    */
    xWayMin = Integer.MAX_VALUE;
    for(int i=1; i<xy.length-1; i++) {
      if(fromRight[i] == Integer.MAX_VALUE || xy[l-i] == Integer.MAX_VALUE) continue;
      xWayMin = Math.min(xWayMin, fromRight[i] + xy[l-i]);
    }
    //System.out.println("xWayMin = " + xWayMin);
  }
  
  private void calc() {
    int[][] xWidth = new int[w + 1][l + 1]; // 必要なxの幅[y 座標][No]
    int[][] roseCount = new int[w + 1][l + 1]; // 必要なxの幅[y 座標][No]
    int[] xSumCount = new int[w + 1]; // [y座標]

    int[] countUp = new int[w+1];
    int[][] roseCountUp = new int[w*l][w+1];
    int[][] xWidthUp = new int[w*l][w+1];
    int[] countDown = new int[w+1];
    int[][] roseCountDown = new int[w*l][w+1], xWidthDown = new int[w*l][w+1];
    
    // X方向で分割
    
    for(int divZoneX = 1; divZoneX <= l; divZoneX++) {
      //System.out.println("divZoneX = " + divZoneX);
      
      // X方向のバラの数の合計を更新
      for(int y=1; y<=w; y++) {
        for(int i=1; i<=xSumCount[y]; i++) {
          xWidth[y][i]++;
        }
        if(garden[divZoneX][y] > 0) {
          for(int i=1; i<=xSumCount[y]; i++) {
            roseCount[y][i] += garden[divZoneX][y];
          }
          for(int i = xSumCount[y]; i>= 1; i--) {
            roseCount[y][i+1] = roseCount[y][i];
            xWidth[y][i+1] = xWidth[y][i];
          }
          xSumCount[y]++;
          xWidth[y][1] = 1; //garden[divZoneX][y];
          roseCount[y][1] = garden[divZoneX][y];
        }
      }
      
      // Y軸方向の探索(お尻から行う=>動的計画法)
      for(int y=w; y>=1; y--) {
        Arrays.fill(countUp, 0);
        for(int i=1; i<=xSumCount[y]; i++) {
          if(roseCount[y][i] <= k) {
            countUp[1]++;
            roseCountUp[countUp[1]][1] = roseCount[y][i];
            xWidthUp[countUp[1]][1] = xWidth[y][i];
            if(roseCount[y][i] == k) {
              int neoXY = xWidthUp[countUp[1]][1] + 1;
              if(neoXY < xy[divZoneX]) {
                xy[divZoneX] = neoXY;
                //minXWidth[divZoneX] = xWidthUp[countUp[1]][1];
                //minYWidth[divZoneX] = 1;
              }
            }
          }
        }
        //System.out.println("xSumCount = " + xSumCount[y]);
//        if(xSumCount[y] > 0) {
          for(int yy = 2; yy <= (w-y+1); yy++) {
            int upPos = 0, downPos = 0;
            while(true) {
              // System.out.println("upPos = " + upPos + ", downPos = " + downPos);
              int roseCountNeo = roseCount[y][upPos] + roseCountDown[downPos][yy-1];
              if(roseCountNeo >0 && roseCountNeo <= k) {
                countUp[yy]++;
                roseCountUp[countUp[yy]][yy] = roseCountNeo;
                xWidthUp[countUp[yy]][yy] = Math.max(xWidth[y][upPos], xWidthDown[downPos][yy-1]);
                if(roseCountNeo == k) {
                  int neoXY = xWidthUp[countUp[yy]][yy] + yy;
                  if(neoXY < xy[divZoneX]) {
                    xy[divZoneX] = neoXY;
                    //minXWidth[divZoneX] = xWidthUp[countUp[yy]][yy];
                    //minYWidth[divZoneX] = yy;
                  }
                }
              }
              
              if(upPos == xSumCount[y] && downPos == countDown[yy-1]) break;
              
              int incDownPos = 0, incUpPos = 0;
              if(upPos == xSumCount[y] || xWidth[y][upPos + 1] >= xWidthDown[downPos + 1][yy-1]) {
                incDownPos = 1;
              }
              if(downPos == countDown[yy-1] || xWidth[y][upPos + 1] <= xWidthDown[downPos + 1][yy-1]) {
                incUpPos = 1;
              }
              downPos = Math.min(countDown[yy-1], downPos + incDownPos);
              upPos = Math.min(xSumCount[y], upPos + incUpPos);
            }
          }
//        }
        int[] tmp1; int[][] tmp2;
        tmp1 = countDown; countDown = countUp; countUp = tmp1;
        tmp2 = roseCountDown; roseCountDown = roseCountUp; roseCountUp = tmp2;
        tmp2 = xWidthDown; xWidthDown = xWidthUp; xWidthUp = tmp2;
        /*
        for(int yy=1; yy<=(w-y+1); yy++) {
          System.out.println("y = " + y + ", yWidth = " + yy);
          for(int i=1; i<=countDown[yy]; i++) {
            System.out.println("\tcount = " + roseCountDown[i][yy] + ", xWidth = " + xWidthDown[i][yy]+ " ");
          }
          System.out.println();
        }
        */
      }
    }
  }
  
  private static int getFirst(String str) {
    int idx = str.indexOf(' ');
    return Integer.parseInt(str.substring(0, idx));
  }
  
  private static int getSecond(String str) {
    int idx = str.indexOf(' ');
    return Integer.parseInt(str.substring(idx + 1));
  }
}
正しい答えは出るものの、いくつかの入力値で制限時間オーバーします。

どうやって高速化するのだろう?
まだ、オーダー落とせるのか??
満点解答をみてしまったが、オーダーは同じだった。
どうも、定数項が違うらしい…

無駄なことやりすぎか?
http://private.fbox.info/ioi/pre1/gar.html

/*
TASK: GAR
LANG: CPP
NAME: Imo Plus

2006/04/12 初版製作

★かけた時間
約6時間
★方針
準備して処理する。オーダーを3乗に抑える。
★難易度
オーダー3乗にする方法だけが問題。
★難点
四辺のどこにもバラがあるのだけ確認する必要。
*/
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

typedef struct rect { int len; int left; int top; int right; int bottom; } box;
int** map;

// boxの重なりを確認する関数
int box_over(const box& a, const box& b) {
  return 0 < (a.top - b.bottom - 1) * (b.top - a.bottom - 1)
    && 0 < (a.left - b.right - 1) * (b.left - a.right - 1);
}

// boxの比較関数(昇順ソート用)
int box_cmp(const box& a, const box& b) {
  return b.len > a.len;
}

// (x1, y1)-(x2, y2)の範囲のバラの個数を計算する
int rose(int x1, int y1, int x2, int y2) {
  // 範囲内のバラの個数を返す
  return map[x2][y2] - (y1 == 0 ? 0 : map[x2][y1 - 1]) -
   (x1 == 0 ? 0 : map[x1 - 1][y2]) +
   ((x1 == 0 || y1 == 0) ? 0 : map[x1 - 1][y1 - 1]);
}

int main(void) {
  int i, j, x, y;
  int l, w, n, k;
  int top, right, left, bottom;
  int min;
  box rect;
  vector<box> rects;

  // 読み込み
  scanf("%d%d%d%d", &l, &w, &n, &k);
  // マップの初期化[O(N^2)]
  for (i = 0, map = new int*[w]; i < w; i++)
   for (j = 0, map[i] = new int[l]; j < l; j++) map[i][j] = 0;
  // バラ数量の読み込み[O(N)]
  for (i = 0; i < n; i++) scanf("%d%d", &y, &x), map[x - 1][y - 1]++;
  // バラのマップを生成する[O(N^2)]
  for (i = 0; i < w; i++) for (j = 0; j < l; j++)
   if (i != 0) map[i][j] += map[i - 1][j];
  for (i = 0; i < w; i++) for (j = 0; j < l; j++)
   if (j != 0) map[i][j] += map[i][j - 1];
  // 計算[O(N^3)]
  for (top = 0; top < l; top++) { rect.top = top;
    for (bottom = top + 1; bottom < l; bottom++) { rect.bottom = bottom;
      for (left = 0, right = 1; left < w && right < w; left++) {
        for (; right < w && rose(left, top, right, bottom) < k; right++);
        // 目的の物を発見したら
        if (right < w && rose(left, top, right, bottom) == k) {
          rect.len = (right - left + bottom - top) * 2 + 4;
          rect.left = left; rect.right = right;
          // 四辺全てあるか確認(無駄な追加を除去する)
          if (rose(left, top, right, top + 1) != 0 &&
            rose(left, bottom - 1, right, bottom) != 0 &&
            rose(left, top, left + 1, bottom) != 0 &&
            rose(right - 1, top, right, bottom) != 0)
            rects.push_back(rect);
        }
      }
    }
  }
  // ソート[O(NlogN)]
  sort(rects.begin(), rects.end(), box_cmp);
  // 目的の情報を取得[O(N〜N^2)]
  for (min = i = 0; i < rects.size(); i++) {
    for (j = i + 1; j < rects.size(); j++) {
      if (min != 0 && min <= rects[i].len + rects[j].len) break;
      if (!box_over(rects[i], rects[j])) min = rects[i].len + rects[j].len;
    }
  }
  // 出力
  if (min == 0) printf("NO\n"); else printf("%d\n", min);

  return 0;
}
/*
自分の初版ソースも張ってみる。初版なのでめっさ無駄が多そう。
*/
#include <stdio.h>
#define INF 999999
main(){
 int l,w;
 int li,wi;
 int n,k;
 int i,j;
 int px,py;
 int honsu;
 int mini;
 int honsu_l[251][251];
 int honsu_w[251][251];
 int right[251],left[251],top[251],bottom[251];
 scanf("%d %d",&l,&w);
 scanf("%d %d",&n,&k);
 for(i=0;i<=l;i++)for(j=0;j<=w;j++){
  honsu_l[i][j]=0;
  honsu_w[i][j]=0;
 }
 for(i=0;i<=l;i++){
  top[i]=INF;bottom[i]=INF;
 }
 for(i=0;i<=w;i++){
  right[i]=INF;left[i]=INF;
 }
 for(i=0;i<n;i++){
  scanf("%d %d",&li,&wi);
  for(j=li;j<=l;j++)honsu_l[j][wi]++;
  for(j=wi;j<=w;j++)honsu_w[li][j]++;
 }
 for(i=1;i<=l;i++){
  for(j=1;j<=w;j++){
   px=i;py=w;
   honsu=honsu_w[i][w]-honsu_w[i][j-1];
   while(1){
    if(honsu==k){//k-hon wo fukumu
     int shu=(px-i+1)+(py-j+1);
     if(shu<top[i])top[i]=shu;
     if(shu<bottom[px])bottom[px]=shu;
     if(shu<left[j])left[j]=shu;
     if(shu<right[py])right[py]=shu;
    }
    if(honsu<=k){
     if(px==l)break;
     px++;
     honsu+=(honsu_w[px][py]-honsu_w[px][j-1]);
    }else{
     if(py==j)break;
     honsu-=(honsu_l[px][py]-honsu_l[i-1][py]);
     py--;
    }
   }
  }
 }
 mini=INF;
 //yoko ni wakareru
 for(i=1;i<=l;i++){
  for(j=i+1;j<=l;j++){
   if(bottom[i]+top[j]<mini)mini=bottom[i]+top[j];
  }
 }
 //tate ni wakareru
 for(i=1;i<=w;i++){
  for(j=i+1;j<=w;j++){
   if(right[i]+left[j]<mini)mini=right[i]+left[j];
  }
 }
 if(mini==INF)printf("NO\n");
 else printf("%d\n",2*mini);
}

ログインすると、みんなのコメントがもっと見れるよ

mixiユーザー
ログインしてコメントしよう!

情報オリンピック 更新情報

情報オリンピックのメンバーはこんなコミュニティにも参加しています

星印の数は、共通して参加しているメンバーが多いほど増えます。

人気コミュニティランキング