DouKaku?beta

[topic] 情報オリンピック2007年度世界大会「帆」

中高生向けの情報オリンピックの世界大会2007年度の第1日目「帆」です。コンテストは2日間にて行われます。クロアチアにて開催されました。

「問題ごとに、プログラムの実行時間（や使用メモリ量）に制限が設定されています。」にご注意ください。本問では、制限時間1秒、メモリ制限64MBとなっています。

入出力は標準入出力にて行います。

採点は、テストデータにおいて正しい結果が返ってくるかで採点されます。出題時はテストデータの一部のみが公開されており、全てのデータは出題時には公開されていません。

post comment

Posted feedbacks - Scala

間違ったコードです。こんなインチキアルゴリズムでも、半分の部分点がもらえることにビックリ。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
object Sails2 extends Application {
  val N = readInt
  // 高さ,　旗の数
  val mast:Array[Array[int]] = List.tabulate(N, i => readLine.split(" ").toList.map(Integer.parseInt(_)).toArray).toArray
  var maxHeight = 0
  mast.foreach(l => maxHeight = Math.max(maxHeight, l(0)))

  val count = new Array[int](maxHeight + 1)
  var flags = 0
  mast.foreach(a => {
    count(a(0)) += 1
    flags += a(1)
  })
  for(i <- (1 to maxHeight - 1).reverse) {
    count(i) += count(i + 1)
  }
  var left = flags
  var sum = 0l
  for(i <- (1 to maxHeight).reverse) {
    val min = Math.min(count(i), left / i)
    left -= min
    sum += (min * (min - 1) / 2)
  }
  println(sum)
}

擬似コードは以下の通りです。
h == zoneMax は else の一部ですが、混ぜてしまうと、概念的に混乱してしまうので、意図的に分離しています。

---------------------

マストの高さでソート
低いマストから
  NES : 高さ(1～) -> 累積帆数
    これは管理しない。概念上のみ。
  step : 高さ -> ひとつ上の高さからの累積帆数の増分 = NES(h) - NES(h + 1)
  stepHeight: step(h) != 0 となる h の TreeSet
    step を更新するときに、ひとつ上を見て、add, remove を判断する
    zoneMin = 同じNESが連続する下限の高さ
    zoneMax = 同じNESが連続する上限の高さ
  h = 今回の高さ - 今回の帆数
  h == 0
    step(マストの高さ)++
  h == マストの高さ
    // ありえない（帆を必ずつける）
  h == zoneMin
    step(zoneMin - 1)--   // zoneMin >= 2 のみ
    step(マスト高さ)++
  h == zoneMax
    // 222111000
    // 222211111
    step(zoneMin - 1)--   // zoneMin >= 2 のみ
    step(zoneMin)++
    zoneMax != マスト高さ
      step(zoneMax)--
      step(マスト高さ)++
  else
    w = zonMax - h + 1    // w >= 1
    step(zoneMin - 1)--   // zoneMin >= 2 のみ
    step(zoneMin + w - 1)++
    zoneMax != マスト高さ
      step(zoneMax)--
      step(マスト高さ)++

--------------------- 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
import scala.collection.jcl.TreeSet

object Sails extends Application {
  // データの読み込み
  val N = readInt
  // マストの(height, flags) のソート済み配列
  val masts = List.tabulate(N, i => {
    val ary = readLine.split(" ").map(Integer.parseInt(_))
    (ary(0), ary(1))
  }).sort((a,b) => a < b).toArray
  var maxHeight = masts(masts.length - 1)._1 
  
  val step = new Array[int](maxHeight + 2)
  val stepHeight = new TreeSet[int]()
  //for(mast <- masts) {
  for(i <- 0 until (masts.length)) {
    val mast = masts(i)     
    val mastHeight = mast._1
    val h = mastHeight - mast._2 + 1
    def getZoneMin(h:int):int = {
      val h2 = stepHeight.underlying.ceiling(h)
      val h3 = if(h2 == null) {
      if(stepHeight.underlying.size == 0) return 1
        stepHeight.underlying.last
      } else {
        stepHeight.underlying.lower(h2)
      }
      if(h3 == null) 1 else h3.asInstanceOf[int] + 1
    }
    def getZoneMax(h:int):int = {
      val h2 = stepHeight.underlying.ceiling(h)
      if(h2 == null) mastHeight else h2.asInstanceOf[int]
    }
    val zoneMin = getZoneMin(h)
    val zoneMax = getZoneMax(h)
    //println("i = " + i + ", h = " + h + ", zoneMin = " + zoneMin + ", zoneMax = " + zoneMax)
    def addStep(h:int, v:int) {
      if(h <= 0) return
      step(h) += v
      adjustStepHeight(h)
    }
    def adjustStepHeight(h:int) {
      if(step(h) != 0)
        stepHeight.underlying.add(h)
      if(h >= 2 && step(h - 1) != 0)
        stepHeight.underlying.add(h - 1)
      if(step(h) == 0)
        stepHeight.underlying.remove(h)
      if(h >= 2 && step(h - 1) == 0)
        stepHeight.underlying.remove(h - 1)
    }
    if(h == 1) {
      addStep(mastHeight, 1)
    } else if(h == zoneMin) {
      addStep(zoneMin - 1, -1)
      addStep(mastHeight, 1)
    } else if(h == zoneMax) {
       addStep(zoneMin - 1, -1)
       addStep(zoneMin, 1)
       if(zoneMax != mastHeight) {
         addStep(zoneMax, -1)
         addStep(mastHeight, 1)
       }
    } else {
      val w = zoneMax - h + 1
      addStep(zoneMin - 1, -1)
      addStep(zoneMin + w - 1, 1)
      if(zoneMax != mastHeight) {
        addStep(zoneMax, -1)
        addStep(mastHeight, 1)
      }
    }
    //println("i = " + i + ", step = " + step.toList + ", stepHeight = " + stepHeight)
  }
  //println(step.toList)
  
  var sum = 0l
  var flagCount = 0
  for(i <- (1 to maxHeight).reverse) {
    def sumNE(n:long) = n * (n - 1) / 2
    flagCount += step(i)
    sum += sumNE(flagCount)
  }
  println(sum)
}

Index

Feed

Other

Link

Pathtraq

loading...
Creative Commons License このサイトの内容は、 クリエイティブ・コモンズ・ライセンスの下でライセンスされています。 [詳細]