Ruby と Perl と Java と Python で解く AtCoder ABC 131 D 配列のソート

はじめに

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

今回のお題

AtCoder Beginner Contest 131 D - Megalomania
Difficulty: 594

今回のテーマ、配列のソート

Ruby

配列のソートですので、実装も簡単だと思います。初Pythonなので軽めの問題を選択しました。

ruby.rb

n = gets.to_i
a = Array.new(n){gets.split.map(&:to_i)}
a.sort_by!{|x| x[1]}
ans = 0
n.times do |i|
  ans += a[i][0]
  if ans > a[i][1]
    puts "No"
    exit
  end
end
puts "Yes"

sort.rb

a.sort_by!{|x| x[1]}

複数条件でソートしていますが学習のためで、解法としては一つだけソートで行けます。
追記
頂いたコメントより一部修正しました。

Python

初めて Python で解きますので、ほぼ写経です。

python.py

n = int(input())
a = list(list(map(int, input().split())) for _ in range(n))
a.sort(key=lambda x: x[1])
ans = 0
for i in range(0, n):
    ans += a[i][0]
    if ans > a[i][1]:
        print("No")
        exit()
print("Yes")

VSCode の拡張機能が効いていますので、コーディングは楽です。

range.py

for i in range(0, n):
for i in range(0, n - 1):

for のところで i で回すようにしましたが、n - 1 と書いてWAをもらいました。

次回は、複数条件のソートに挑戦しようと思います。

Perl

perl.pl

chomp (my $n = <STDIN>);
my @a;
for my $i (0..$n-1) {
  my @in = split / /, <STDIN>;
  ($a[$i][0], $a[$i][1]) = @in;
}
@a = sort {$$a[1]<=>$$b[1] || $$b[0]<=>$$a[0]} @a;

my $ans = 0;
for my $i (0..$n-1) {
  $ans += $a[$i][0];
  if ($ans>$a[$i][1]) {
    print "No\n";
    exit;
  }
}
print "Yes\n";

sort.pl

@a = sort {$$a[1]<=>$$b[1] || $$b[0]<=>$$a[0]} @a;

Perl は複数条件のソートです。

Java

java.java

import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.next());
        List<Work> work = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            int time = Integer.parseInt(sc.next());
            int limit = Integer.parseInt(sc.next());
            work.add(new Work(time, limit));
        }
        sc.close();
        work.sort(Comparator.comparingInt(x -> x.limit));
        int ans = 0;
        for (int i = 0; i < n; i++) {
            ans += work.get(i).time;
            if (ans > work.get(i).limit) {
                System.out.println("No");
                return;
            }
        }
        System.out.println("Yes");
    }

    static class Work {
        int time;
        int limit;

        Work(int time, int limit) {
            this.time = time;
            this.limit = limit;
        }
    }
}

sort.java

        work.sort(Comparator.comparingInt(x -> x.limit));

Java は単数条件のソートです。

追記
コメントで教えてもらいましたので、ソートの比較部分を java8 で導入された Comparator を使用するコードに変更しました。安全かつ若干速くなりました。

	Ruby	Python	Perl	Java
コード長	189 Byte	231 Byte	315 Byte	972 Byte
実行時間	484 ms	995 ms	1237 ms	883 ms
メモリ	22520 KB	53728 KB	66788 KB	72900 KB

まとめ

• ABC 131 D を解いた
• Ruby に詳しくなった
• Python に詳しくなった
• Perl に詳しくなった
• Java に詳しくなった