[topic] 情報オリンピック2007年度国内本選問題2
Posted feedbacks - Java
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 | import java.io.BufferedReader;
import java.io.InputStreamReader;
public class P2 {
public static void main(String[] args) throws Exception {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
String s1 = in.readLine();
String s2 = in.readLine();
int[][] len = new int[s1.length()][s2.length()];
int max = 0;
for (int i = 0; i < s1.length(); i++) {
char c1 = s1.charAt(i);
for (int j = 0; j < s2.length(); j++) {
if (c1 == s2.charAt(j)) {
int prev;
if (i > 0 && j > 0)
prev = len[i - 1][j - 1];
else
prev = 0;
len[i][j] = prev + 1;
max = Math.max(max, len[i][j]);
}
}
}
System.out.println(max);
}
}
|
2次元配列をやめてみたけど、実行時間は変わらず…
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 | import java.io.BufferedReader;
import java.io.InputStreamReader;
public class P2 {
public static void main(String[] args) throws Exception {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
String s1 = in.readLine();
String s2 = in.readLine();
int[] prev = new int[s2.length()];
int max = 0;
for (int i = 0; i < s1.length(); i++) {
char c1 = s1.charAt(i);
int[] next = new int[s2.length()];
for (int j = 0; j < s2.length(); j++) {
if (c1 == s2.charAt(j)) {
if (j > 0)
next[j] = prev[j - 1] + 1;
else
next[j] = 1;
max = Math.max(max, next[j]);
}
}
prev = next;
}
System.out.println(max);
}
}
|
yukoba #5778() Rating0/0=0.00
中高生向けの情報オリンピック国内本選2007年度問題2です。
「問題ごとに、プログラムの実行時間（や使用メモリ量）に制限が設定されています。」にご注意ください。本問では、制限時間1秒、メモリ制限64MBとなっています。
出題時はサンプルデータのみが公開され、採点は、採点データによる、自動採点にて行われます。
実際のコンテストでは、予選通過者48名が対象となっていて、100点満点中38点以上とった、16名が本選通過です。
[ reply ]