nu50218 blog

Parenting Partnering Returns | GCJ2020 Qual C

 kyopro  1416  3 分

Google Code Jam 2020 Qualification Roundの3問目、Parenting Partnering Returnsが易しいけど割と好きな感じだったので自分の解法の証明を書きます。Goで解きました。

問題の概要

$N (\leq 1000)$個のタスクにそれぞれ開始の時間$S_i$と終了の時間$E_i$がある。それぞれのタスクをCameronとJamieの二人に割り振りたい。ただし1人1タスクしか同時にできない。

このような割り振り方が存在するかを判定し、存在するなら1つ出力する。存在しないならIMPOSSIBLEと出力。

解法

以下をすべてのタスクを割り当てるまで繰り返す。途中で終了していなければ、得られた割り振り方を出力する。

  1. $X$をまだ割り当てていないタスクのうち開始がもっとも早いもののいずれか1つとする

  2. $X$をCameronに割り当てられるなら割り当てて1に戻る

  3. $X$をJamieに割り当てられるなら割り当てて1に戻る

  4. IMPOSSIBLEと出力して終了

ソートで$O(N \log N)$、上の処理で$O(N)$かかって全体$O(N \log N)$です。

証明

条件を満たす割り振り方が存在するか否かで場合分けをして考えます。

存在しない場合

明らかにこの解法は途中で終了していなければ正しい割り振り方を得ます。つまり、条件を満たす割り振り方が存在しない場合、この解法は途中で終了します。よって正しくIMPOSSIBLEを出力します。

存在する場合

途中で終了していなければ正しい割り振り方を得るので、存在する場合、途中で終了しないことを示します。

IMPOSSIBLEと出力するとき、$X$はCameronとJamieのどちらにも割り当てられません。すでにCameronとJamieに割り振っているタスクは開始が$X$以前であることから、ある区間が存在して、3つ以上のタスクがその区間と被っていることがわかります。このようなとき、条件を満たす割り振り方は存在しないので、背理法より示せました。

※イメージ

gcj-2020-qual-c-1.png

感想

GCJのジャッジ環境のGoのバージョンが低すぎてキレそうになりました。sort.Sliceが見つからないって言われたので多分1.8より前です。$N \leq 1000$だったので愚直バブルソートを書きました。C++を使いましょう。

ちなみにこれを書いてるときに調べたらGo1.8より前はsortパッケージが存在していなかったわけではなくて、sort.Interfaceを満たすようにこっちで書いて渡してあげるとソートしてくれるっぽいです。

参考: Go 1.8以前のバージョンでソートする

あと、draw.ioをはじめて使いました。評判通りめっちゃ使いやすかったです。

コード

  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
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103

package main

import (
 "bufio"
 "bytes"
 "fmt"
 "os"
 "strconv"
)

type Interval struct {
 Index    int
 Assignee byte
 Start    int
 End      int
}

func sort(intervals []*Interval, less func(i, j int) bool) {
 for range intervals {
  for i := 0; i < len(intervals)-1; i++ {
   if !less(i, i+1) {
    // swap
    intervals[i], intervals[i+1] = intervals[i+1], intervals[i]
   }
  }
 }
}

func solve() string {
 N := nextInt()

 intervals := make([]*Interval, N)
 for i := range intervals {
  interval := &Interval{
   Index: i,
  }
  interval.Start = nextInt()
  interval.End = nextInt()

  intervals[i] = interval
 }

 sort(intervals, func(i, j int) bool {
  return intervals[i].Start < intervals[j].Start
 })

 var (
  cLast int
  jLast int
 )

 for _, interval := range intervals {
  if cLast <= interval.Start {
   interval.Assignee = 'C'
   cLast = interval.End
   continue
  }
  if jLast <= interval.Start {
   interval.Assignee = 'J'
   jLast = interval.End
   continue
  }
  return "IMPOSSIBLE"
 }

 sort(intervals, func(i, j int) bool {
  return intervals[i].Index < intervals[j].Index
 })

 var b bytes.Buffer
 for _, interval := range intervals {
  b.WriteByte(interval.Assignee)
 }

 return b.String()
}

func main() {
 T := nextInt()
 for x := 1; x <= T; x++ {
  s := solve()
  fmt.Printf("Case #%d: %s\n", x, s)
 }
}

var (
 s = bufio.NewScanner(os.Stdin)
)

func init() {
 s.Split(bufio.ScanWords)
}

func nextInt() int {
 s.Scan()
 n, _ := strconv.Atoi(s.Text())
 return n
}

func nextString() string {
 s.Scan()
 return s.Text()
}

関連記事: