AtCoder振り返り：165(A~D)

2020年5月2日に開催されたAtCoderを復習します。

結果

遺憾ですが、2問しか解けませんでした。
3問目は何言っているのかよく分からなくて飛ばしてしまいました。
4問目はTLEです。それ以降は問題も見ていません。

最近は安定して3完取れていたのでこの結果には非常に悔しいです。
5/3(日) もAtCoderが実施されるのでそちらでは3完以上取りたいです。

成績

以下の通り微増といったところです。
下がらなくてよかったですがやはり2完は痛い

個別の成績は以下です。
パフォーマンス370だと茶色ですらないですね。精進しなくては

問題

問1 We Love Golf

引数Kの倍数が、引数AからBの範囲内に収まるかをチェックする処理です。
私は馬鹿正直に積み上げて計算してしまいましたが、
解説の通り B / K × K が、A以上であった場合OKとするであればもっと簡単に求められます。

回答コード

import java.util.Scanner;
 
public class Main {
	public static void main(String[] args) {
		try (Scanner scn = new Scanner(System.in)) {
			int K = scn.nextInt();
			int A = scn.nextInt();
			int B = scn.nextInt();
 
			int tmp = K;
			while(tmp < A) {
				tmp = tmp + K;
			}
			if(A <= tmp && tmp <= B) {
				System.out.println("OK");
			} else {
				System.out.println("NG");
			}
		}
	}
}

問2 1%

初期値100という銀行残高に、年利１％がつくと目的の金額 Xには何年で到達するかを求める問題です。
単純に目標金額を上回るまで銀行残高/100を足し続ければOKです。
今回の場合、double形で計算したため小数点を考慮する必要があります。
※long型だったなら勝手に小数点切り捨ててくれるのでMath.floorもいらなかったですね。

回答コード

import java.util.Scanner;
 
public class Main {
	public static void main(String[] args) {
		try (Scanner scn = new Scanner(System.in)) {
			double zandaka = 100;
			double rishi = 0.01d;
			long X = scn.nextLong();
 
			int year = 0;
			while(zandaka < X) {
				double fukuri = Math.floor(zandaka*rishi);
				zandaka = zandaka + fukuri;
				year++;
			}
 
			System.out.println(year);
		}
	}
}

問3 Many Requirements

この問題を最初見た時、何言っているのかわからなかったのですが
Abi - Aai = ci を満たすデータという点ですが、つまり
A(biの要素) - A(aiの要素 = ciということになるので
bi, aiはC言語でいうところのポインタになります。

Aという要素が{1, 3, 4}だった場合、
渡される引数一つずつを処理すると以下の通りとなります。
3 4 3
1 3 3 100 //Aの要素3番目(4) - Aの要素1番目(1) = ci(3) のため、条件を満たす。
1 2 2 10 //Aの要素2番目(3) - Aの要素1番目(1) = ci(2) のため、条件を満たす。
2 3 2 10 //Aの要素3番目(4) - Aの要素2番目(3) = ci(2) のため、条件を満たさない。

ということで、あとは全探索を行っていけばいいのですがここで詰まりました。。。

まずは私の誤回答コードですが、以下アルゴリズムの場合
1, 3, 4のようパターンは検出できますが
2, 2, 4などは検索できません。

import java.util.Scanner;
 
public class Main {
	public static void main(String[] args) {
		try (Scanner scn = new Scanner(System.in)) {
			int N = scn.nextInt();
			int M = scn.nextInt();
			int Q = scn.nextInt();
 
			int[] a = new int[Q];
			int[] b = new int[Q];
			int[] c = new int[Q];
			int[] d = new int[Q];
			int[] x = new int[N];
 
			for(int i = 0; i < Q; i++) {
				a[i] = scn.nextInt();
				b[i] = scn.nextInt();
				c[i] = scn.nextInt();
				d[i] = scn.nextInt();
			}
 
			//初期化
			for(int i = 0; i < N; i++) {
				x[i] = M;
			}
			int sum = 0;
			int result = 0;
			//N × M回処理する
			//1 <= A1 <= A2 <= A3...<= AN <=M の条件を守る
			//
			for(int i = 0; i < N; i++) {
				//初期化
//				for(int j = 0; j < N; j++) {
//					x[j] = M;
//				}
				for(int j = 0; j < M-1; j++) {
					x[i] = x[i] - 1;
//					x = check(x, i);
					//計算処理
					for(int k = 0; k < Q; k++) {
						if(x[b[k]-1] - x[a[k]-1] == c[k]) {
							sum = sum + d[k];
						}
					}
					if(result < sum) {
						result = sum;
					}
					sum = 0;
 
				}
			}
			System.out.println(result);
		}
	}
 
	public static int[] check(int[] num, int i) {
		if(i == 0) return num;
		if(num[i-1] > num[i]) {
			num[i-1] = num[i-1] - 1;
			check(num, i - 1);
		}
		return num;
	}
}

再起処理を利用して、Aの要素を順番に以下のように順番に計算していけばいいです。
私は再起処理がまだ完全に理解しきれていない節があるのでどんどん練習しなくては、、、

1, 1, 1
1, 1, 2
1, 2, 2
1, 2, 3
1, 3, 3
1, 3, 4
1, 4, 4
2, 2, 2
...

解答コード

import java.util.Scanner;

public class Main165_03re {
	public static int[] ans;
	public static int max = 0;
	public static int n;
	public static int m;
	public static int[][] qs;
    public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		m = sc.nextInt();
		int qn = sc.nextInt();
		ans = new int[n];
		qs = new int[qn][4];
		for(int i=0; i<qn; i++){
			qs[i][0] = sc.nextInt();
			qs[i][1] = sc.nextInt();
			qs[i][2] = sc.nextInt();
			qs[i][3] = sc.nextInt();
		}
		saiki(1, 1);
		System.out.println(max);
	}

	public static void saiki(int now, int keta){
		for(int i=now; i<=m; i++){
			ans[keta-1] = i;
			if(keta == n) {
				int tmp = 0;
				for(int[] q: qs){
					if(ans[q[1]-1] - ans[q[0]-1] == q[2]){
						tmp += q[3];
					}
				}
				max = Math.max(max, tmp);
				continue;
			}
			saiki(i, keta+1);
		}
	}
}

問4 Floor Function

最後の問題ですが、引数A B N が渡されるので
floor(Ax / B) - A * floor(x / B)の最大値を整数として出力します。
なお、N以下と決められていますが馬鹿正直にN回繰り返して計算するとN = 10^12なので1兆回計算することとなり当然TLEとなります。

私の誤回答コード

import java.util.Scanner;
 
public class Main {
	public static void main(String[] args) {
		try (Scanner scn = new Scanner(System.in)) {
			long A = scn.nextLong();
			long B = scn.nextLong();
			long N = scn.nextLong();
 
			long max = 0;
			for(int x = 1; x <= N; x++) {
				long ax = A * x / B;
				long ab = A * (x/B);
				long tmp = ax - ab;
 
				if(max < tmp) {
					max = tmp;
				}
			}
			System.out.println(max);
		}
	}
}

他の方の解説を見て分かったのですが、
今回の問題は floor(Ax / B) は、A(5) の数だけ増分し、B(7)で周期します。
つまり x = 0, 1, 2, ... B -1 までなので計算量が B -1 回数となります。
ただこれだと B = 10^12場合またTLEになります。

しかし、0からB-1はどの位置をとっても単調増加（常に右上がりになる）なので、
基本的にはB-1のパターンを計算すればよいが、x <= Nの条件も考慮する必要があるため
NまたはB-1の最小になる値を利用すれば求まる。

解答コード

import java.util.Scanner;
 
public class Main {
	public static void main(String[] args) {
		try (Scanner scn = new Scanner(System.in)) {
			long A = scn.nextLong();
			long B = scn.nextLong();
			long N = scn.nextLong();
 
			N = Math.min(B-1, N);
 
			System.out.println((long)(Math.floor(A*N/B) - A * (Math.floor(N/B))));
		}
	}
}

解説
https://img.atcoder.jp/abc165/editorial.pdf