【C#】AtCoderで多次元配列をソートしたかった時にとった手法

AtCoder Beginner Contest 131 D問題を解いたとき、アルゴリズム自体は簡単だったのですが実装でかなり手こずったのでその時のメモです。

D問題の概要

• N 個の仕事がある
• i番目のしごとはA_i時間かかり、B_iまでに完了する必要がある
• 与えられた入力に対して、すべての仕事がちゃんと期限までに完了できれば”Yes”、できなければ”No”を出力する

解法

まず、Bをキーとして昇順にソートします。つまり、期限が早いものから順に並べます。

各仕事のAの値を足していき、足したAに対応する期限Bを超えていないかチェックして、超えていなければ次の仕事をチェックします。最後までチェックしてBを超えなければ条件を満たすことができるので”Yes”を出力します。

input
2 4
1 8
4 9
1 9
3 12

↓ ( Sort & Check)

2 4   (2 <= 4) : OK
1 8   (1 + 2 <= 8) : OK
1 9   (1 + 2 + 1 <= 9) : OK
4 9  (1 + 2 + 1 + 4 <= 9) : OK
3 12 (1 + 2 + 1 + 4  + 3 <= 12) : OK

C＃での実装

最初、このA、Bの情報を多次元配列に格納してソートしようとしました。ただ、多次元配列におけるソートを行う標準ライブラリがなかったので、他に方法がないか調べました。ジャグ配列を使用すればArray.Sortが使用できるそうなので、そちらに方針を変更しました。(別にソートを実装してもよいですが、競プロだとスピードが求められるのでできるだけ標準ライブラリで実装する方針としています。)

実装

github.com

long[][] AB = new long[N][];
for (int i = 0; i < N; i++)
{
    input = Console.ReadLine().Split();
    AB[i] = new long[] { int.Parse(input[1]), int.Parse(input[0]) };
}
Array.Sort(AB, StructuralComparisons.StructuralComparer);

ここで、Array.Sort(AB, StructuralComparisons.StructuralComparer);という記述をしていますが、まだちゃんと調べられてないのですが、挙動としてはジャグ配列の1つ目の要素をキーとして昇順にソートされます。そのため、今回はBをキーにしたかったのでAB[i] = new long[] { int.Parse(input[1]), int.Parse(input[0]) };でBを先に格納しています。(BはGithubのコードを読めばわかります)

ちなみに、このジャグ配列をArray.Sortでソートする場合は、要素となる各配列の長さがすべて同じじゃなきゃできません。

感想

多次元のソートも覚えておいたほうが良いと思うので、どっかに処理を残しておくか。