前回はこちらから。

さあ、今回はABC113Cを解いていこうかな。C問題だから、前回よりも難しいけど頑張ろう。

ABC113Cの問題

問題文
Atcoder国には N 個の県があり、これらの県には合計で M 個の市が属しています。
市 i が誕生したのは Yi 年であり、県 Pi に属しています。
ただし、同じ年に誕生した市が複数存在することはないとします。
それぞれの市に 12 桁の認識番号を割り振ることとなりました。
市 i が 県 Pi に属する市の中で x 番目に誕生した市のとき、市 i の認識番号の上 6 桁は Pi、下 6 桁は x となります。
ただし、Pi や x が 6 桁に満たない場合は 6 桁になるまで 0 を左に追加するものとします。
全ての市の認識番号を求めてください。
ただし、市が 1 つも属さない県がある場合に注意してください。

制約
- 1≤N≤10^5
- 1≤M≤10^5
- 1≤Pi≤N
- 1≤Yi≤10^9
- Yi は全て異なる
- 入力は全て整数

今回の問題は、保持しなくちゃいけない情報が多くて大変そうだ。

アルゴリズム

やっぱり、B問題よりも考えなきゃいけないことが多くて、手順が複雑になるなぁ..

1. すべての市の情報を取得
2. 県の番号でソート
3. 同一の県の番号を持つ場合は誕生年でソート
4. 各市ごとの出力内容(例: 000001000002)の生成
5. 市の番号順に生成した出力内容を出力

こんな感じの流れかなぁ？
まぁこれで実装してみよう。

ということで、実装を始めたのだけど、情報を保持するデータ構造に少し悩む。最初はmapでうまく出来ないかなぁなんて思ったけど、情報が保持しづらそう..
結局、競プロで初の構造体を定義することに。

一つの市について保持すべき情報は、

- 市の番号 : 解答時の出力順用
- 属する県の番号 : 属する県の特定用
- 市の誕生年 : 誕生順の特定用

ってことで、以下のような構造体を定義してみることに。

type City struct {
   n int // 市の番号
   p int // 県の番号
   y int // 市の誕生年
}

次は、構造体にソート時に必要な Less() メソッドの定義をしなければ。手順2,3を実現する必要があるので、以下のような感じに。

func (l Citys) Less(i, j int) bool {
   if l[i].p == l[j].p {
       return l[i].y < l[j].y // 県の番号が互いに同一の場合、誕生年で比較
   }
   return l[i].p < l[j].p // 県の番号が互いに異なる場合は、県の番号で比較
}

やっぱり、速度重視の競技プログラミングでソートするためだけに3つもメソッド定義しなくちゃならないのはネックだなぁ...
最近のGo言語なら簡単にソートできるんだけども、AtCoderで扱えるGo言語のバージョンが古くて、昔の方法しか使えない...

なんて文句言っていてもしょうがないので、次へ進もう。と言っても、ソートした後は、出力内容を生成して表示すれば終わりだ。

出力内容の生成は、直前の市と属する県が同じなら下6桁の方の番号を上げて、県が違ったら上6桁の番号を上げて、下6桁を1に戻す。 
こんな感じに実装してみたけど、もう少しいい方法がありそうかなぁ。

sort.Sort(citys)
ans := make([]string, m)

last := citys[0].p
n := 0
for _, c := range citys {
   if c.p == last {
      n++
   } else {
      n = 1
      last = c.p
   }
   ans[c.n] = fmt.Sprintf("%06d%06d", c.p, n)
}

後は、出力のコードを追加して完成だね！

解答

最終的には、こんな感じのコードになりました。

package main

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

type City struct {
   n int
   p int
   y int
}

type Citys []City

func (l Citys) Len() int {
   return len(l)
}

func (l Citys) Less(i, j int) bool {
   if l[i].p == l[j].p {
       return l[i].y < l[j].y
   }
   return l[i].p < l[j].p
}

func (l Citys) Swap(i, j int) {
   l[i], l[j] = l[j], l[i]
}

func main() {
   sc := bufio.NewScanner(os.Stdin)
   sc.Split(bufio.ScanWords)
   sc.Scan()
   sc.Text()
   sc.Scan()
   m, _ := strconv.Atoi(sc.Text())

   citys := make(Citys, m)
   for i := 0; i < m; i++ {
       sc.Scan()
       p, _ := strconv.Atoi(sc.Text())
       sc.Scan()
       y, _ := strconv.Atoi(sc.Text())
       citys[i] = City{i, p, y}
   }

   sort.Sort(citys)   
   ans := make([]string, m)

   last := citys[0].p
   n := 0
   for _, c := range citys {
       if c.p == last {
           n++
       } else {
           n = 1
           last = c.p
       }
       ans[c.n] = fmt.Sprintf("%06d%06d", c.p, n)
   }

   for _, a := range ans {
       fmt.Println(a)
   }
}

なんとかC問題クリア。B問題より大幅に時間がかかってしまった。
けれど、自分で考えて問題解けると嬉しいね。

次はABC114Bを解いていこうと思う。
さぁ次回も頑張ろう。