新人SEの学習記録

14年度入社SEの学習記録用に始めたブログです。もう新人じゃないかも…

参加記録:AtCoder Regular Contest

[参加記録] AtCoder Regular Contest 028

結果

  • A問題とB問題の部分点で140点
  • A問題:小石を取るゲーム
    • ぱっと見で思いついた解答が以下
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);

		int n = scan.nextInt();
		int a = scan.nextInt();
		int b = scan.nextInt();
		String str;
		
		while (true) {
			n -= a;
			if (n <= 0) {
				str = "Ant";
				break;
			}
			
			n -= b;
			if (n <= 0) {
				str = "Bug";
				break;
			}
		}
		
		System.out.println(str);
		
		scan.close();
	}
}
    • 似たようなことをwhile文中で2回やっているのが微妙
    • 解説を聞くと、aとbを配列に入れ、2の剰余でインデックス指定するとすっきり書けるらしい
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);

		int n = scan.nextInt();
		int a = scan.nextInt();
		int b = scan.nextInt();
		int[] num = {a, b};
		int k = 0;
		
		while (n > 0) {
			n -= num[k];
			k = (k + 1) % 2;
		}

		String[] ret = {"Ant", "Bug"};
		System.out.println(ret[1-k]);
		
		scan.close();
	}

}
    • k = (k + 1) % N で0〜N-1の間でインクリメントできるのを覚えておく
  • B問題:あるコンテストの順位と年齢をもとに、i位以上でk番目に若い人を探す
    • まずは愚直に毎回ソート>k番目の人を出力
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;
 
public class Main {
 
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		List<Integer> list = new ArrayList<Integer>();
		
		int n = scan.nextInt();
		int k = scan.nextInt();
		List<Integer> x = new ArrayList<Integer>();
		
		
		for (int i = 0; i < n; ++i) {
			x.add(scan.nextInt());
		}
 
		for (int i = 0; i < k - 1; ++i) {
			list.add(x.get(i));
		}
		
		for (int i = k; i <= n; ++i) {
			list.add(x.get(i-1));
			Collections.sort(list);
			System.out.println(x.indexOf(list.get(k-1))+1);
		}
		
		scan.close();
	}
 
}
    • 当然TLEだったので計算量を減らす工夫を考える
    • k番目に若い人より年齢の高い人はリストから消してみるなどしたが、結局ソートが必要になりTLEになってしまう
    • 解説によるとヒープ(Priority Queue)を使うと良いらしい
      • Comparableを実装したクラスを追加すると、その順序で並ぶ
      • 追加はoffer、先頭要素の取り出し(参照&削除)はpoll、先頭要素の参照はpeak
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;

public class Main {
	
	static class Contestant implements Comparable<Contestant>{

		private int rank;
		private int old;
		
		public Contestant(int r, int o) {
			rank = r;
			old = o;
		}

		@Override
		public int compareTo(Contestant o) {
			return o.old - old;
		}
	}

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		
		int n = scan.nextInt();
		int k = scan.nextInt();
		int[] x = new int[n];
		Queue<Contestant> queue = new PriorityQueue<Main.Contestant>();
		
		for (int i = 0; i < n; ++i) {
			x[i] = scan.nextInt();
		}

		for (int i = 0; i < k; ++i) {
			queue.offer(new Contestant(i + 1, x[i]));
		}

			System.out.println(queue.peek().rank);
		
		for (int i = k; i < n; ++i) {
			queue.offer(new Contestant(i + 1, x[i]));
			queue.poll();
			System.out.println(queue.peek().rank);
		}
		scan.close();
	}
}
      • Priority Queueには常にk個の要素が入っている
      • Contestantは年齢の降順で並ぶようにcompareToを規定
      • 一番最初を除き、キューに追加>先頭(一番年齢の高い人)を削除>先頭(k番目に若い人)を表示、という処理を行う
      • キューに追加したのが若い人なら、今までk番目に若かった人がキューから追い出され、今までk-1番目に若かった人が先頭となり、その人の順位が出力される
      • キューに追加したのが一番年齢の高い人なら、追加時に先頭に配置されるのでその人がキューから追い出される