Javaの練習のためにABC#003を解いてみました

今回もいつもどおりABC(Atcoder Beginner Contest)を解いてみました。

javaなどほとんど忘れていた状態だったのですが、毎日書いているとやはり書けるようになってきますね。
それでもまだまだ初心者レベルからは脱出できていませんが。。。

今回はABC#003を解いてみました。

これでbeginner contestの方は全て解き終わったことになります。

初めはビギナーコンテストなのだからどうせ簡単な問題だろう、とたかをくくっていました。

しかし、実際はコンテスト一回につき一問はかなり解き応えのある問題があるので、やりごたえがあります。

リアルタイムで参加したABC#004の4問目は未だに解けていませんし(笑)

宣伝のようになってしまいますが、競技プログラミングを初めてみたい方、プログラミング初心者の方には本当にお勧めです。

では問題の方に移っていきたいと思います。

まず1問目

A: AtCoder社の給料 - AtCoder Beginner Contest #003 | AtCoder

これは簡単な問題なのでパス。以下コード

import java.util.Scanner;
 
public class Main {
 
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int ans=0;
		for(int i=1; i<=n; i++){
			ans+=10000*i;
		}
		System.out.println(ans/n);
	}
 
}

2問目

B: AtCoderトランプ - AtCoder Beginner Contest #003 | AtCoder

こちらは2問目にしては少し苦戦しました。

私は、一文字ずつ読み取って、それを比べていく方式を取りました。

知らなかったことをメモ

・文字列の長さを求める

int length = s.length();

・文字列の任意の場所の文字を取り出す(今回は先頭の文字を取り出した)

char s1 = s.charAt(i);

i番目の文字を取り出します

以下コード

import java.util.Scanner;

public class Main {	//トランプ
 
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String s = sc.next();
		String t = sc.next();
		char s1;
		char t1;
		boolean flag = true;
		int len = s.length();
		
		for(int i=0; i<len; i++){
			s1 = s.charAt(i);
			t1 = t.charAt(i);
			//System.out.println(s1+","+t1);
			if(s1==t1)continue;
			else if(s1!=t1){
				if(s1=='@'){
					if(t1=='a'|t1=='t'|t1=='c'|t1=='o'|t1=='d'|t1=='e'|t1=='r'|t1=='@'){
						continue;
					}else{
						flag=false;break;
					}
				}else if(t1=='@'){
					if(s1=='a'|s1=='t'|s1=='c'|s1=='o'|s1=='d'|s1=='e'|s1=='r'|s1=='@'){
						continue;
					}else{
						flag=false;break;
					}
				}else{
					flag=false;break;
				}
			}
		}
		if(flag)System.out.println("You can win");
		else System.out.println("You will lose");
	}
 
}

3問目

C: AtCoderプログラミング講座 - AtCoder Beginner Contest #003 | AtCoder

これは一見難しいかと思いきや、アルゴリズムを考えればとても簡単な問題でした。

間違っても全探索なんかで解いてはいけないですね。

N個のレートの中から大きい順にK個を選んで(これはソートで実現)、選んだものをレートの小さい順に計算処理します。

以下コード

import java.util.Scanner;
import java.util.Arrays;
 
public class Main {
 
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int k = sc.nextInt();
		double[] r = new double[n];
		double ans = 0;
		
		for(int i=0; i<n; i++){
			r[i] = sc.nextInt();
		}
		Arrays.sort(r);
		for(int i=n-k; i<n; i++){
			ans = (ans+r[i])/2;
		}
		System.out.println(ans);
		
		sc.close();
	}
 
}

4問目

D: AtCoder社の冬 - AtCoder Beginner Contest #003 | AtCoder

毎回一番難しい4問目ですが、今回は100点満点ではなく101満点でした。

100点の解法はアルゴリズム自体は易しく少し考えれば分かるのですが、問題は実装方法でした。

何かというとこの問題

145180660592914517790287604376765671109248284280228061640640
↑のようなとても大きな桁の数値を扱うのです。

初めはdouble型を用いて書きました。double型は非常に大きな数、小さな数を扱えます。

しかし、その代償に、誤差が生じてしまいます。double型では大きな数や小さな数は指数表記で表すため、数値が丸められてしまいます。そのため正しい答えを出力することはできませんでした。

そこで次はBigDicemal型という型を使って演算を行いました。これを使うことで、intやlongなどで扱えないような大きな数でも誤差なく計算することができ、正しい答えを出力することができました。
詳しくは別の記事でまとめたいと思います。

アルゴリズム説明

①R×Cの長方形の中にあるX×Yの長方形が何通りあるかを求める

②D,Lの置き方が何通りあるのか求める
今回はD+L＝X×Yの場合なのでXYの中に空白は生まれない。よってD(またはL)の置き方が何通りあるのかを求めれば、それが求める組み合わせ数になる。
この組み合わせ数はX×Y個からD(またはL)を選ぶ場合の数なので、(xy)C(d)で求めることができる。

③①と②を掛けあわせたものが全てのパターンとなるのでそれを100000007で割った余りを求める。

こんなかんじです。

以下ソース

import java.util.Scanner;
import java.math.BigDecimal;
 
public class Main {
 
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int r = sc.nextInt();
		int c = sc.nextInt();
		int x = sc.nextInt();
		int y = sc.nextInt();
		int d = sc.nextInt();
		int l = sc.nextInt();
		
		int p1 = (c-y+1)*(r-x+1);
		BigDecimal p2;
		BigDecimal p1b = new BigDecimal(Integer.toString(p1));
		BigDecimal up = new BigDecimal(Integer.toString(x*y));
		BigDecimal d_d = new BigDecimal(Integer.toString(d));
		BigDecimal l_d = new BigDecimal(Integer.toString(l));
		BigDecimal upans = new BigDecimal("1");
		BigDecimal downans = new BigDecimal("1");
		BigDecimal one = new BigDecimal("1");
		BigDecimal wari = new BigDecimal("1000000007");
		
		if(d<=l){
			for(int i=d; i>=1; i--){
				//upans *= up;
				upans = upans.multiply(up);
				//downans *= i;
				downans = downans.multiply(d_d);
				//up--;
				up = up.subtract(one);
				//d_d--;
				d_d = d_d.subtract(one);
			}
			p2 = upans.divide(downans,0,BigDecimal.ROUND_HALF_UP);
		}else{
			for(int i=l; i>=1; i--){
				//upans *= up;
				upans = upans.multiply(up);
				//downans *= i;
				downans = downans.multiply(l_d);
				//up--;
				up = up.subtract(one);
				//l_d--;
				l_d = l_d.subtract(one);
			}
			p2 = upans.divide(downans,3,BigDecimal.ROUND_HALF_UP);
		}
		BigDecimal p1p2 = p1b.multiply(p2);
		BigDecimal div = p1p2.divide(wari,0,BigDecimal.ROUND_DOWN);
		BigDecimal mul = div.multiply(wari);
		int ans = p1p2.subtract(mul).intValue();
		
		System.out.println(ans);
		
		sc.close();
	}
 
}

今回はかなり長い記事になってしまいました。
ではこの辺で。