AtCoder Beginner Contest 089

A - Grouping 2

import java.util.*;
import static java.lang.System.*;
 
public class Main {
	static Scanner sc = new Scanner(System.in);
	public static void main(String[] args) {
		int n = sc.nextInt();
		out.println(n/3);
	}
}

3で割って終わり。こういった極端に簡単な問題を素早く解く訓練をしていないので、多少もたついてしまった。

B - Hina Arare

import java.util.*;
import static java.lang.System.*;
 
public class Main {
	static Scanner sc = new Scanner(System.in);
	public static void main(String[] args) {
		boolean P = false;
		boolean W = false;
		boolean G = false;
		boolean Y = false;
		int n = sc.nextInt();
		String s;
		for (int i=0; i<n; i++) {
			s = sc.next();
			if (s.equals("P")) {P=true;}
			else if (s.equals("W")) {W=true;}
			else if (s.equals("G")) {G=true;}
			else {Y=true;}
		}
		int count = 0;
		if (P==true) {count++;}
		if (W==true) {count++;}
		if (G==true) {count++;}
		if (Y==true) {count++;}
		out.println(count==4?"Four":"Three");
	}
}

3種類か4種類かの違いは、黄色が入っているかいないかである。よって、Yが一つでもあれば4種類、一つもなければ3種類ということになる。冷静に考えてからコードを組み立てればいいものを、下手に速く解こうとしたのでコードが冗長になってしまった。

C - March

import java.util.*;
import static java.lang.System.*;
 
public class Main {
	static Scanner sc = new Scanner(System.in);
	public static void main(String[] args) {
		long[] ar = new long[5];
		int n = sc.nextInt();
		char c;
		for (int i=0; i<n; i++) {
			c = sc.next().charAt(0);
			if (c=='M') {ar[0]++;}
			else if (c=='A') {ar[1]++;}
			else if (c=='R') {ar[2]++;}
			else if (c=='C') {ar[3]++;}
			else if (c=='H' ) {ar[4]++;}
		}
		
		long total = 0;
		total += ar[2]*ar[3]*ar[4];
		total += ar[1]*ar[3]*ar[4];
		total += ar[1]*ar[2]*ar[4];
		total += ar[1]*ar[2]*ar[3];
		total += ar[0]*ar[3]*ar[4];
		total += ar[0]*ar[2]*ar[4];
		total += ar[0]*ar[2]*ar[3];
		total += ar[0]*ar[1]*ar[4];
		total += ar[0]*ar[1]*ar[3];
		total += ar[0]*ar[1]*ar[2];
		out.println(total);
	}
}

コンビネーションの公式すら危ういほど高校数学を忘却してしまっているので、解法に辿り着くのに時間がかかりすぎてしまった。5C3は10通り、よってそれらを全て列挙すればよい。スマートな解法を思いつけなかったので腕力を振るった。

D - Practical Skill Test

熟考の果てに我流の解法に辿り着いた僕は全完の夢を見たが、それはTLEという形で打ち砕かれ、結果としてはいつも通りのABC3完に終わった。制約が緩かったら通ったのだろうが、さすがにD問題となると腕力によるごまかしは効かないようだ。

解説には「Dで割った余りを用いた累積和」とあるが、「普通は d[i]=d[i-1]+n とするところを d[i]=d[i-D]+n とした累積和」「D個間隔の累積和」と言ったほうが分かりやすいと思う。

まとめ

結果はTLEに終わってしまったが、D問題の解法に自力で辿りつけたのは嬉しかった。また、前回の反省記事でも書いた通り、四年の歳月が僕の頭から数学の知識をすっかり奪い去ってしまったようなので、せめて確率と期待値と組み合わせくらいは来週のABCまでに復習しておきたいと思った。