[topic] 情報オリンピック2007年度国内本選問題3
Posted feedbacks - Java
しらみつぶしだと O(N^4) です。20％の得点がもらえます。
3本までをしらみつぶしでやり、最後2分探索すると
O(N^3 log N) で50％の得点がもらえます。
4本＝2本＋2本であることに着目すると、2本までをしらみつぶしでやり、
最後2分探索すると O(N^2 log N) になり、満点となります。
【擬似コード】
データを読み込む。データに0を追加
N^2 の組み合わせを作る
それをソートする
for x <- N^2 の組み合わせで M 以下
2分探索で、M-x 以下で最大の物を探し、xとの和をとる。
その最大値が答え
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 | import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
public class P3 {
public static void main(String[] args) throws Exception {
// データの読み込み。データに０を追加
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
String[] ary = in.readLine().split(" ");
int N = Integer.parseInt(ary[0]);
int M = Integer.parseInt(ary[1]);
N++;
int[] data = new int[N];
for (int i = 1; i < N; i++) {
data[i] = Integer.parseInt(in.readLine());
}
// N^2 の組み合わせを作る
int[] comb = new int[N * N];
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
comb[i * N + j] = data[i] + data[j];
}
}
// それをソートする
Arrays.sort(comb);
// for x <- N^2 の組み合わせで M 以下
int max = 0;
for (int i = 0; i < comb.length; i++) {
int x = comb[i];
if (x > M)
break;
// 2分探索で、M-x以下で最大の物を探し、xとの和をとる。
int bs = Arrays.binarySearch(comb, M - x);
if (bs < 0) {
bs = -(bs + 1);
} else if (bs != comb.length) {
max = M;
break;
}
if (bs > 0) {
max = Math.max(max, x + comb[bs - 1]);
}
}
System.out.println(max);
}
}
|
yukoba #5779() Rating0/0=0.00
中高生向けの情報オリンピック国内本選2007年度問題1です。
「問題ごとに、プログラムの実行時間（や使用メモリ量）に制限が設定されています。」にご注意ください。本問では、制限時間1秒、メモリ制限64MBとなっています。
出題時はサンプルデータのみが公開され、採点は、採点データによる、自動採点にて行われます。
実際のコンテストでは、予選通過者48名が対象となっていて、100点満点中38点以上とった、16名が本選通過です。
[ reply ]