はじめに

AtCoder Problems の Recommendation を利用して、過去の問題を解いています。
AtCoder さん、AtCoder Problems さん、ありがとうございます。

今回のお題

AtCoder Beginner Contest 113 C - ID
Difficulty: 877

今回のテーマ、リファレンス

Ruby

以前に解きました、Ruby で解く AtCoder Judge System Update Test Contest 202004 B を少し難しくした様な問題です。

ruby.rb

n, m = gets.split.map(&:to_i)
p = []
m.times do |i|
  y = gets.split.map(&:to_i)
  p[i] = [i, y, ""]
end
p.sort! {|a, b| (a[1][0]<=>b[1][0]).nonzero? || (a[1][1]<=>b[1][1])}
pref = 0
cnt = 1
m.times do |i|
  if pref == p[i][1][0]
    cnt += 1
  else
    cnt = 1
    pref = p[i][1][0]
  end
  p[i][2] = p[i][1][0].to_s.rjust(6, "0").concat(cnt.to_s.rjust(6, "0"))
end
p.sort! {|a, b| a[0]<=>b[0]}
m.times do |i|
  puts p[i][2]
end

array.rb

  p[i] = [i, y, ""]
  # => [[0, [1, 32], ""], [1, [2, 63], ""], [2, [1, 12], ""]]
  p.sort! {|a, b| (a[1][0]<=>b[1][0]).nonzero? || (a[1][1]<=>b[1][1])}
  # => [[2, [1, 12], ""], [0, [1, 32], ""], [1, [2, 63], ""]]
  p[i][2] = p[i][1][0].to_s.rjust(6, "0").concat(cnt.to_s.rjust(6, "0"))
  # => [[2, [1, 12], "000001000001"], [0, [1, 32], "000001000002"], [1, [2, 63], "000002000001"]]

配列 p の中が頭に浮かぶようであれば、このレベルの問題は卒業でしょう。

Ruby (Hash版)

RubyHash.rb

n, m = gets.split.map(&:to_i)
p = []
h = Hash.new(0);
m.times do |i|
  y = gets.split.map(&:to_i)
  p[i] = [i, y, ""]
  h[y[0]] +=1
end
p.sort! {|a, b| b[1][1]<=>a[1][1]}
m.times do |i|
  p[i][2] = p[i][1][0].to_s.rjust(6, "0").concat(h[p[i][1][0]].to_s.rjust(6, "0"))
  h[p[i][1][0]] -= 1
end
p.sort! {|a, b| a[0]<=>b[0]}
m.times do |i|
  puts p[i][2]
end

カウント変数の代わりにハッシュを使用して解いています。
コード長が短くなった事と、ソートの条件が一つになっていることが特徴で、若干速くなっています。
~~Java 版がTLEなので追加しました。~~

Perl

perl.pl

chomp (my ($n, $m) = split / /, <STDIN>);
my @p;
for my $i (0..$m-1) {
  chomp (my @in = split / /, <STDIN>);
  $p[$i] = [$i, @in];
}
@p = sort {$$a[1]<=>$$b[1] || $$a[2]<=>$$b[2]} @p;
my ($pref, $cnt) = (0, 0);
for my $i (0..$m-1) {
  if ($pref == $p[$i][1]) {
    $cnt++;
  } else {
    $pref = $p[$i][1];
    $cnt = 1;
  }
  $p[$i][3] = sprintf("%06s", $p[$i][1]) . sprintf("%06s", $cnt);
}
@p = sort {$$a[0]<=>$$b[0]} @p;
print $$_[3], "\n" for @p;

こちらも、前回記事の応用で複数条件のソートになります。

array.pl

[0, 1, 32], [1, 2, 63], [2, 1, 12]

但し、Ruby とは配列の中の構造が異なって、フラットになっています。

Java

java.java

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

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.next());
        int m = Integer.parseInt(sc.next());
        Map<Integer, Integer> h = new HashMap<>();
        List<City> city = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            int Pref = Integer.parseInt(sc.next());
            int Year = Integer.parseInt(sc.next());
            city.add(new City(i, Pref, Year));
            if (h.containsKey(Pref)) {
                h.put(Pref, h.get(Pref) + 1);
            } else {
                h.put(Pref, 1);
            }
        }
        sc.close();
        city.sort((o1, o2) -> Integer.compare(o2.Year, o1.Year));
        for (City c : city) {
            c.Num = h.get(c.Pref);
            h.put(c.Pref, h.get(c.Pref) - 1);
        }
        city.sort((o1, o2) -> Integer.compare(o1.ID, o2.ID));
        PrintWriter pw = new PrintWriter(System.out);
        for (City c : city) {
            pw.printf("%06d%06d\n", c.Pref, c.Num);
        }
        pw.flush();
    }

    static class City {
        int ID;
        int Pref;
        int Year;
        int Num;

        City(int ID, int Pref, int Year) {
            this.ID = ID;
            this.Pref = Pref;
            this.Year = Year;
            this.Num = 0;
        }
    }
}

Java らしく~~構造体~~クラスを利用していますが、複数条件のソートの実装が大変になりますので、ハッシュを使用しています。

flush.java

import java.io.PrintWriter;

PrintWriterを使用しないとTLEになります。

	Ruby	Ruby(Hash)	Perl	Java
コード長	450 Byte	372 Byte	470 Byte	1444 Byte
実行時間	943 ms	880 ms	1079 ms	1615 ms
メモリ	27376 KB	33900 KB	45168 KB	107864 KB

まとめ

ABC 113 C を解いた
Ruby に詳しくなった
Perl に詳しくなった
Java に詳しくなった

参照したサイト
instance method String#rjust

Ruby と Perl と Java で解く AtCoder ABC 113 C リファレンス