結果
問題 | No.252 "良問"(良問とは言っていない (2) |
ユーザー |
|
提出日時 | 2015-07-27 15:28:49 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 573 ms / 2,000 ms |
コード長 | 2,645 bytes |
コンパイル時間 | 3,848 ms |
コンパイル使用メモリ | 78,680 KB |
実行使用メモリ | 75,396 KB |
最終ジャッジ日時 | 2024-07-16 04:08:46 |
合計ジャッジ時間 | 7,022 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 7 |
ソースコード
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStream;import java.io.InputStreamReader;import java.util.Arrays;import java.util.Iterator;public class Main_yukicoder252 {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int t = sc.nextInt();for (int i = 0; i < t; i++) {char[] s = sc.next().toCharArray();int n = s.length;int[] g = new int[n];for (int j = 0; j + 3 < n; j++) {g[j] = ham(s, j, "good");if (j > 0) {g[j] = Math.min(g[j - 1], g[j]);}}int[] p = new int[n];int[] p0 = new int[n];for (int j = 0; j + 6 < n; j++) {p[j] = ham(s, j, "problem");if (j > 0) {if (p[j] == 0) {p0[j] = p0[j - 1] + 1;} else {p0[j] = p0[j - 1];}} else {if (p[j] == 0) {p0[j] = 1;} else {p0[j] = 0;}}}for (int j = n - 7; j >= 0; j--) {if (j < n - 7) {p[j] = Math.min(p[j + 1], p[j]);}}int min = Integer.MAX_VALUE;for (int j = 4; j + 6 < n; j++) {min = Math.min(min, g[j - 4] + p[j] + (j >= 10 ? p0[j - 10] : 0));}System.out.println(min);}sc.close();}private static int ham(char[] s, int j, String string) {char[] tmp = string.toCharArray();int ret = 0;for (int i = 0; i < tmp.length; i++) {if (s[j + i] != tmp[i]) {ret++;}}return ret;}@SuppressWarnings("unused")private static class Scanner {BufferedReader br;Iterator<String> it;Scanner (InputStream in) {br = new BufferedReader(new InputStreamReader(in));}String next() throws RuntimeException {try {if (it == null || !it.hasNext()) {it = Arrays.asList(br.readLine().split(" ")).iterator();}return it.next();} catch (IOException e) {throw new IllegalStateException();}}int nextInt() throws RuntimeException {return Integer.parseInt(next());}long nextLong() throws RuntimeException {return Long.parseLong(next());}float nextFloat() throws RuntimeException {return Float.parseFloat(next());}double nextDouble() throws RuntimeException {return Double.parseDouble(next());}void close() {try {br.close();} catch (IOException e) {// throw new IllegalStateException();}}}}