1日で2つの記事。
いっぱい学んで偉いぞ自分。
というわけで、本番中は解けなかった、CodeFestivalあさぷろMiddleの問題Bについて書きます。
さて、この問題は、(各人の好む枕の一番小さい値(=本文中のxi)を"下限"、一番大きい値(=本文中のyi)を"上限"と書きます)
1.各参加者を、下限が低い順にならべる
2.枕を、高さの低い順にならべる
3.枕を低い順に見ていって、下限がその枕高以下の人の、上限を覚えていく。そして、その枕を下限的に使える人の中で、上限的にも使える人の内、上限が最も低い人にその枕を割り当てる。
というアルゴリズムで解けそうです。
これの実行には、1.で、
人の上限と下限をセットで覚えて、下限の小さい順にソートする
という操作が必要です。これは今までの僕には出来ませんでした。
しかし今回!ついに出来るようになりました。というわけで、やり方を説明していきます(参考にしたページはコチラ)。
まず、新しくpersonというクラス(型)を作りました。内容はこんな感じ。
class person{ int minHeight; int maxHeight; }
どシンプルですね。person型は、整数を2つ持ちます。それは好みの枕の下限と上限を表します。
そしてperson型の配列を生成します。それは
person[] persons = new person[n];
で出来ます。
そして、人の情報を読み込んでいくのは、次のようにします。少し面倒ですが、毎回"new"を使って、新しいpersonのインスタンスを生成しなければなりません。
for(int i = 0; i < n; i++){ person newperson = new person(); //ここが面倒ですね newperson.minHeight = sc.nextInt(); newperson.maxHeight = sc.nextInt(); persons[i] = newperson; }
そしてそして、このpersonを並び変えるときに使う、比較関数を作る必要があります。
その実態がコチラ。
class newComp implements Comparator{ public int compare(Object o1, Object o2){ person p1 = new person(); person p2 = new person(); p1 = (person)o1; p2 = (person)o2; if(p1.minHeight < p2.minHeight){ return -1; }else if(p1.minHeight > p2.minHeight){ return 1; } return 0; } }
Comparatorというクラスをimplementします。
その中にcompareという関数を書きます。
注意ですが、このcompare関数の引数はObject型のもの2つです。ここの引数をperson型にしていて、ずっとつまっていました。ややこしい。
そしてこのcompare関数で、負の値を返した場合はo1 < o2、正の場合はo1 > o2を意味します。
自然順序を入れるというやり方もあるそうなのですが、今回はやっていません。そのうちやります。そのうちだよ、そのうち。
(追記:自然順序の方もやってみました→Javaで自分の作ったクラスに順序を入れる方法(Comparable編))
このようにnewCompクラスと定義するとこのcompare関数に従ってperson型の配列をソートするという操作はこう書けます。
Arrays.sort(persons, new newComp());
ここにもnewが必要です。ここに一番詰まりました。んもう。
これでついに、自分が作った型の配列をソートすることができました。
いぇいいぇい。進歩です。
あとは、PriorityQueue(以前学びました)を使ってやっていくだけです。余裕!
というわけで、今回の説明は以上です。
最後に、この問題の解答コードを書いておきます。解くアルゴリズムはこの記事内の頭で説明したものです。
import java.util.*; class person{ int minHeight; int maxHeight; } class newComp implements Comparator{ public int compare(Object o1, Object o2){ person p1 = new person(); person p2 = new person(); p1 = (person)o1; p2 = (person)o2; if(p1.minHeight < p2.minHeight){ return -1; }else if(p1.minHeight > p2.minHeight){ return 1; } return 0; } } public class Main { public static void main(String[] args){ Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int m = sc.nextInt(); person[] persons = new person[n]; for(int i = 0; i < n; i++){ person newperson = new person(); newperson.minHeight = sc.nextInt(); newperson.maxHeight = sc.nextInt(); persons[i] = newperson; } Arrays.sort(persons, new newComp()); int[] makukras = new int[m]; for(int i = 0; i < m; i++){ makukras[i] = sc.nextInt(); } Arrays.sort(makukras); int count = 0; int lookingIndex = 0; PriorityQueue<Integer> priQue = new PriorityQueue<Integer>(); for(int i = 0; i < m; i++){ //その枕を(下限だけ見て)使えそうな人を、どんどんPriorityQueueに入れていく。 //どこまでの人を見たかも覚えとく(このチェックをクリアしてQueueに入った人達は、これ以降の枕についても下限的には使えるハズであるから、再考しなくてよい)。 while(lookingIndex < n && makukras[i] >= persons[lookingIndex].minHeight){ priQue.add(persons[lookingIndex].maxHeight); lookingIndex++; } //キューが空なら、この枕を使える人はいない if(priQue.isEmpty()){ continue; } //下限的にクリアした人の中で、上限が一番小さい人を見ていく。 //この枕を上限的にも使える人に出会うまでみていく while(!priQue.isEmpty() && makukras[i] > priQue.peek()){ priQue.poll(); } //キューが空なっちゃったなら、この枕を使える人はいない if(priQue.isEmpty()){ continue; }else{ count++; priQue.poll(); } } System.out.println(count); } }