AtCoder Beginner Contest 098
※今回のコンテストには出場できず、全ての問題は終わった後に解きました。
A - Add Sub Mul
out.println( max(a+b,a-b,a*b) );
B - Cut and Count
import static java.lang.System.*; import java.util.*; public class Main { //初期フィールド・メソッド--------------------------------------------- static Scanner sc = new Scanner(System.in); static int min(int... ar) {Arrays.sort(ar); return ar[0];} static int max(int... ar) {Arrays.sort(ar); return ar[ar.length-1];} //------------------------------------------------------------ //フィールド追加場所----------------------------------------------- static String s; //------------------------------------------------------------ //mainメソッド--------------------------------------------------- public static void main(String[] args) { int n = sc.nextInt(); s = sc.next(); int max = Integer.MIN_VALUE; for (int i=1; i<n; i++) max = Math.max(max,cut(i)); out.println(max); } //------------------------------------------------------------ //メソッド追加場所------------------------------------------------ static int cut(int n) { boolean[] x = new boolean[26]; boolean[] y = new boolean[26]; String a = s.substring(0,n); String b = s.substring(n,s.length()); for (int i=0; i<a.length(); i++) x[a.charAt(i)-97] = true; for (int i=0; i<b.length(); i++) y[b.charAt(i)-97] = true; int num = 0; for (int i=0; i<26; i++) { if (x[i] && y[i]) num++; } return num; } //------------------------------------------------------------ }
B問題にしてはちょっと難しいかも。
文字列長は最大でも100なので、全探索可能です。
切断した後の左右の文字列のうち、左側にある文字種を格納する配列xと、右側にある文字種を格納する配列yを用意し、あとは実際に全ての箇所を切断しながら、両配列に共通する文字種を数えていけばよいです。
問題を解くにあたり、
①substringを使った文字列の部分抽出のやりかた
②英小文字のchar値から97を引くことで、0~25までの数字に変換する
これらのテクニックを使えるようにしておくと便利です。
C - Attention
import static java.lang.System.*; import java.util.*; public class Main { //初期フィールド・メソッド--------------------------------------------- static Scanner sc = new Scanner(System.in); static int min(int... ar) {Arrays.sort(ar); return ar[0];} static int max(int... ar) {Arrays.sort(ar); return ar[ar.length-1];} //------------------------------------------------------------ //フィールド追加場所----------------------------------------------- //------------------------------------------------------------ //mainメソッド--------------------------------------------------- public static void main(String[] args) { int n = sc.nextInt(); String s = sc.next(); int[] eNum = new int[n]; int[] wNum = new int[n]; for (int i=1; i<n; i++) { if (s.charAt(i-1)=='W') wNum[i]++; wNum[i] += wNum[i-1]; } for (int i=n-2; i>=0; i--) { if (s.charAt(i+1)=='E') eNum[i]++; eNum[i] += eNum[i+1]; } int min = Integer.MAX_VALUE; for (int i=0; i<n; i++) { min = Math.min(min,wNum[i]+eNum[i]); } out.println(min); } //------------------------------------------------------------ //メソッド追加場所------------------------------------------------ //------------------------------------------------------------ }
累積和の問題です。
配列wNum:i番目の人を選んだとき、その人より左側にいるWの数の累積和
配列eNum:i番目の人を選んだとき、その人より右側にいるEの数の累積和
というふうに累積和をとって、二つの配列を順に探索し、wNum[i]+eNum[i]の最小値を出力すればよいです。
追記:もしかするとB問題も、累積和使えば全探索しなくても解けるのかな?
D - Xor Sum 2
またこんど
まとめ
今回のコンテストは深刻な寝不足により参加できませんでした。
解説を見ることなく、またWAを出すことなくA,B,C問題を完答できたのでよかったです。次回までに生活リズムを整えておきたい……。