hihoCoder 1039文字最も詳細な問題解決レポートを削除
7095 ワード
タイトルソース:文字消去
問題解決の考え方:
1、指定された文字列の任意の位置に'A'、'B'、'C'の任意の文字を挿入し、挿入後の文字が消去された後で最も短い文字列長を計算する.
2、文字消去後の最短長さを計算する時、知能的に一度計算して、個人は何ももっと良い方法を考え出せなかった.
3、1文字ずつ挿入した後、2ステップ目の計算を経て最も短い文字列長min、最後に元の文字列の長さ-min+1を記録する.
具体的なアルゴリズム(java版、直接AC可能)
問題解決の考え方:
1、指定された文字列の任意の位置に'A'、'B'、'C'の任意の文字を挿入し、挿入後の文字が消去された後で最も短い文字列長を計算する.
2、文字消去後の最短長さを計算する時、知能的に一度計算して、個人は何ももっと良い方法を考え出せなかった.
3、1文字ずつ挿入した後、2ステップ目の計算を経て最も短い文字列長min、最後に元の文字列の長さ-min+1を記録する.
具体的なアルゴリズム(java版、直接AC可能)
1 import java.util.Scanner;
2
3 public class Main {
4
5 public static int handle(StringBuffer buffer) {
6 int count = 0;
7 while (true) {
8 StringBuffer temp = new StringBuffer();
9 int i = 0, j = 1;
10 for (; j < buffer.length(); j++) {
11 if (buffer.charAt(i) != buffer.charAt(j)) {
12 temp.append(buffer.charAt(i));
13 } else {
14 while (j < buffer.length()
15 && buffer.charAt(i) == buffer.charAt(j))
16 j++;
17 }
18 i = j;
19 }
20 if (j == buffer.length()) {
21 temp.append(buffer.charAt(i));
22 }
23 if (temp.length() == buffer.length()) {
24 count = temp.length();
25 break;
26 }
27 buffer = temp;
28 }
29 return count;
30 }
31
32 public static void main(String[] args) {
33 Scanner scanner = new Scanner(System.in);
34 int n = scanner.nextInt();
35 for (int i = 0; i < n; i++) {
36 StringBuffer buffer = new StringBuffer(scanner.next());
37 int min = buffer.length();
38 for (int j = 0; j < buffer.length(); j++) {
39 for (char ch = 'A'; ch <= 'C'; ch++) {
40 StringBuffer temp = new StringBuffer(buffer);
41 temp = temp.insert(j, ch);
42 int count = handle(temp);
43 min = min > count ? count : min;
44 }
45 }
46 System.out.println(buffer.length() + 1 - min);
47 }
48 }
49 }