[JAVA] ABC --023 --A & B & C

AtCoder ABC 023 A&B&C AtCoder - 023

A problem

	private void solveA() {
		int x = nextInt();

		int res = 0;
		while (x != 0) {
			res += x % 10;
			x /= 10;
		}

		out.println(res);
	}

B problem

――Since the order of the combination of 'a',' c'and'b' is not taken into consideration, it is actually a ** lie solution **. .. .. A fix will be coming soon.

--Looking at the sample --The start starts with 'b' and is always +2 characters, so it will always be an odd number. --False for even numbers --The center is 'b', and the left and right are one of the following - 'a' xxx 'c' - 'c' xxx 'a' - 'b' xxx 'b' ――Look at the left and right based on the middle 'b'

	private void solveB() {
		int numN = nextInt();
		String s = next();

		if ((numN & 1) == 0) {
			out.println(-1);
			return;
		}
		int max = numN / 2;
		int res = 0;
		for (int i = 0; i < max; i++) {
			char down = s.charAt((numN - 1) - (max + 1) - i);
			char up = s.charAt((max + 1) + i);
			if ((down == 'a' && up == 'c') || (down == 'c' && up == 'a') || (down == 'b' && up == 'b')) {
				res = i + 1;
			} else {
				out.println(-1);
				return;
			}
		}

		out.println(res);
	}

C problem

AtCoder Beginner Contest 023 Explanation P.12 ~

--Basically, if you read the explanation

-I will write only a supplement about [Fine adjustment \ Investigate where the candy was placed]

If the sum is equal to K

--When k = 3 -At the position of $ (col no, row no) = (2,2) , you can get 3 candies without any problem. - (Col count, row count) = (2,1) $, so the total is 3 -At the position of $ (col no, row no) = (3,2) , only two candies can be taken. - (Col count, row count) = (2,1) $, so there should be 3 in the calculation. .. ..

If the place where you put the candy is $ col count + row count = K $, you are counting the places that should not be counted.

If the sum is equal to K + 1

--When k = 3 -At the position of $ (col no, row no) = (3,3) $, you can get 3 candies without any problem. --However, $ (col count, row count) = (2,2) $, so the total is 4

--If the place where you put the candy is $ col count + row count = K + 1 $, the candy is counted twice. ―― +1 because you have counted the candy you put twice

	private void solveC() {
		int r = nextInt();
		int c = nextInt();
		int k = nextInt();
		int n = nextInt();
		int[] rI = new int[n];
		int[] cI = new int[n];
		int[] rP = new int[r + 1];
		int[] cP = new int[c + 1];
		for (int i = 0; i < n; i++) {
			int tmpR = nextInt() - 1;
			int tmpC = nextInt() - 1;
			rI[i] = tmpR;
			cI[i] = tmpC;
			//Number of candies for each line of r
			rP[tmpR]++;
			//Number of candies in each column of c
			cP[tmpC]++;
		}

		/*
		 *Aggregate the number of candies for each row
		 *If this number is for each row
		 * [1, 2, 2, 0]
		 *Count as follows
		 * 0=1
		 * 1=1
		 * 2=2
		 * 3=0
		 *rPCount size is N+1 is because there are no more candies
		 */
		int[] rPCount = new int[n + 1];
		for (int i = 0; i < r; i++) {
			rPCount[rP[i]]++;
		}
		//Process each column in the same way as row
		int[] cPCount = new int[n + 1];
		for (int i = 0; i < c; i++) {
			cPCount[cP[i]]++;
		}

		long res = 0;
		/*
		 *Roughly calculate the combination
		 *For input example 1,
		 *When the number of candies in row is 0, the number of candies in col must be 3.
		 *for that reason,[Number of lines where r candy is 0]×[The number of lines where the candy of c is 3]Calculate
		 *Similarly, when the number of row candies is 1, the number of col candies is two, so
		 *  [Number of lines where r candy is 1]×[The number of lines where the candy of c is 2]Calculate
		 *This gives a rough combination
		 */
		for (int i = 0; i <= k; i++) {
			res += rPCount[i] * cPCount[k - i];
		}

		/*
		 *Tweak
		 *Investigate where the candy was placed
		 */
		for (int i = 0; i < n; i++) {
			long sum = rP[rI[i]] + cP[cI[i]];
			if (sum == k) {
				/*
				 *The fact that the sum is equal to K counts the objects that should not be counted in the rough combination calculation.
				 *Therefore, this position is excluded from the count
				 */
				res--;
			} else if (sum == k + 1) {
				/*
				 *The total is K+1 is out of the scope of counting at the time of rough combination calculation
				 *Therefore, this position counts
				 */
				res++;
			}
		}
		out.println(res);
	}

C problem: TLE

--Is memory low? It seems, but the speed is not enough. .. ..

	private void solveC3() {
		int r = nextInt();
		int c = nextInt();
		int k = nextInt();
		int n = nextInt();
		//		int[][] masu = new int[r][c];
		Map<Integer, Set<Integer>> wk = new HashMap<Integer, Set<Integer>>();
		int[] rP = new int[r];
		int[] cP = new int[c];
		for (int i = 0; i < n; i++) {
			int tmpR = nextInt() - 1;
			int tmpC = nextInt() - 1;
			//			masu[tmpR][tmpC] = 1;
			Set<Integer> tmpSet = new HashSet<Integer>();
			tmpSet.add(tmpC);
			wk.merge(tmpR, tmpSet, (oldV, newV) -> {
				oldV.addAll(newV);
				return oldV;
			});
			rP[tmpR]++;
			cP[tmpC]++;
		}

		long res = 0;
		Set<Integer> defSet = new HashSet<Integer>();
		for (int i = 0; i < rP.length; i++) {
			for (int j = 0; j < cP.length; j++) {
				int val = wk.getOrDefault(i, defSet).contains(j) ? 1 : 0;
				//				int val = wk.getOrDefault(i, new HashSet<Integer>()).contains(j) ? 1 : 0;
				if (rP[i] + cP[j] - val == k) {
					res++;
				}
			}
		}

		out.println(res);
	}

C problem: MLE

--The array is too large and there is not enough memory. .. ..

	/**
	 * MLE
	 */
	private void solveC2() {
		int r = nextInt();
		int c = nextInt();
		int k = nextInt();
		int n = nextInt();
		int[][] masu = new int[r][c];
		int[] rP = new int[r];
		int[] cP = new int[c];
		for (int i = 0; i < n; i++) {
			int tmpR = nextInt();
			int tmpC = nextInt();
			masu[tmpR - 1][tmpC - 1] = 1;
			rP[tmpR - 1]++;
			cP[tmpC - 1]++;
		}

		long res = 0;
		for (int i = 0; i < rP.length; i++) {
			for (int j = 0; j < cP.length; j++) {
				if (rP[i] + cP[j] - masu[i][j] == k) {
					res++;
				}
			}
		}

		out.println(res);
	}