Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2010-02-14Member SRM461(DIV2)

結果


問題結果ポイントその他
第一問(250pt)Passed System Test242.77今まで一番簡単じゃないか、これ。
第二問(550pt)Failed System Test0.00すんなり解けたけど英語イミフ
第三問(1000pt)Opened0.00

Rating: +97(985 > 1082)

とりあえず4桁まで持ち直せた。room内3位、div2全体で150位でした!

SRM461 div2 第一問(250点)

| SRM461 div2 第一問(250点) - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク - SRM461 div2 第一問(250点) - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=10749&rd=14181


public class TrappingRabbit { 
  public int findMinimumTime(int[] trapX, int[] trapY) { 
    int trapNum = trapX.length; 
    int min = -1; 
    for (int i = 0 ; i < trapNum ; i++) { 
      int sec = (trapX[i] - 1) + (trapY[i] - 1); 
      if (min == -1 || min > sec) {
        min = sec;
      }
    }
    return min; 
  }
}

Challengeで一人撃墜できた。


SRM461 div2 第二問(550点)

| SRM461 div2 第二問(550点) - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク - SRM461 div2 第二問(550点) - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=10731&rd=14181

長方形を赤と青のディスクを交互に使って埋めるとき、最小何個使えば埋められるか、と言う問題。


英語がよく分からず、問題の意味を理解するのに時間がかかった。

とりあえずディスクを昇順に並び替え、大きい方から交互に使って行く方針。

赤から使い始める場合と青から使い始める場合とを試して、

結果のいい方をとればいいのではないかと。

submitしたコードはこちら。

import java.util.List; 

public class ColoringRectangle { 
  public int chooseDisks(int width, int height, int[] red, int[] blue) { 
    int usedDisksRed = 0, usedDisksBlue = 0; 
    java.util.Arrays.sort(red); 
    java.util.Arrays.sort(blue); 

    int redNum = red.length; 
    int blueNum = blue.length; 
    int num = Math.max(redNum, blueNum); 
    boolean ev = true; 
    double r; 
    double dist = 0; 
    double height24 = (double) height * height / 4; 
    for (int i = 1 ; i <= num ;) { 
      try { 
        if (ev) { 
          r = (double) red[redNum - i] / 2; 
        } else { 
          r = (double) blue[blueNum - i] / 2; 
        } 
      } catch (Exception e) { 
        break; 
      } 
      dist += Math.sqrt(r * r - height24) * 2; 
      usedDisksRed++; 
      if (dist >= width) { 
        break; 
      } 
      ev = !ev; 
      if (ev) { 
        i++; 
      } 
    } 
    if (dist < width) { 
      usedDisksRed = -1; 
    } 

    dist = 0; 
    ev = true; 
    for (int i = 1 ; i <= num ;) { 
      try { 
        if (ev) { 
          r = (double) blue[blueNum - i] / 2; 
        } else { 
          r = (double) red[redNum - i] / 2; 
        } 
      } catch (Exception e) { 
        break; 
      } 
      dist += (double) Math.sqrt(r * r - height24) * 2; 
      usedDisksBlue++; 
      if (dist >= width) { 
        break; 
      } 
      ev = !ev; 
      if (ev) { 
        i++; 
      } 
    } 
    if (dist < width) { 
      usedDisksBlue = -1; 
    } 

    if (usedDisksRed == -1 && usedDisksBlue == -1) { 
      return -1; 
    } else if (usedDisksRed == -1) { 
      return usedDisksBlue; 
    } else if (usedDisksBlue == -1) { 
      return usedDisksRed; 
    } else { 
      return Math.min(usedDisksBlue, usedDisksRed); 
    } 
  } 
}

汚い・・・(笑)

サンプルのケースが一応通ったので焦りつつ提出。

しかしSystestで、ひとつだけ通らないテストケースが出た。

width = 10,
height = 5,
red = {10, 10},
blue = {4, 3}

これで失敗。うちのプログラムが出した答えは -1 、つまり埋まらず。

正しくは4個全部使えば埋められるらしい。

正しくは-1、ですが間違って4が出力されていました。

平方根の計算(Math.sqrt)の部分で、円の直径が長方形の縦の長さより小さい場合を

考慮していなかったのが原因のようです。しかしよくChallengeで落とされなかったな。

SRM461 div2 第三問(1000点)

| SRM461 div2 第三問(1000点) - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク - SRM461 div2 第三問(1000点) - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=10747&rd=14181

ゲーセンハイスコアのネームエントリー風に文字を入力するとき、

最小でいくつキー入力が必要かという問題。

残り20分ごろになってOpenはしたが、解くことはできなかった。

tomeruntomerun2010/02/14 16:45550ですが、
> うちのプログラムが出した答えは -1 、つまり埋まらず。正しくは4個全部使えば埋められるらしい。

逆、ではないでしょうか。
円の直径<height のとき、Math.sqrt(r * r - height24) の引数が負になってdistがNaNになってしまうので、以降distとwidthの比較が全部falseになるのではないかと。

hama_DUhama_DU2010/02/14 21:14tomerun様
コメント・ご指摘ありがとうございます。

>逆、ではないでしょうか。
先ほど確認したところ、見間違いで-1の方が正しいようです。

>円の直径<height のとき・・・
そうですね!その場合を忘れてました!
あとでソースコードを書き直してみます!