Java初心者の競技プログラミング日記

Dvorak配列でjavaを書いてます

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問題を完答できたのでよかったです。次回までに生活リズムを整えておきたい……。