AtCoder159振り返り(A ～ E)
2020年2月から始めたAtCoderですがようやく4完までできました。
改めて今回の成績を振り返っていきます。（いい加減、Java7は卒業したいですね。。。)
成績
4完できたのでレーティングもそこそこあがりました。
パフォーマンスも755だったので、茶色上位相当くらいは行けてそうです。
今後は4完を安定させていきたいのでアルゴリズム面の勉強もソロソロ始めてみようか。。。といったところでしょうか。
問題
問1
奇数のボールN個と、偶数のボールM個があって
1つずつボールを選択したときに和が奇数となる組み合わせが何種類あるかを答える問題です。
組み合わせとしては以下2パターンしかありえません。
①奇数＋奇数
②偶数＋偶数
NとMそれぞれで組み合わせを求めればOKです。
回答コード
import java.util.Scanner; public class Main { public static void main(String[] args) { // TODO 自動生成されたメソッド・スタブ Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int M = sc.nextInt(); int cnt = 0; for(int i = 1; i < N; i++) { cnt = cnt + N - i; } for(int i = 1; i < M; i++) { cnt = cnt + M - i; } System.out.println(cnt); } }
ただ、解答を見るともっと簡単に求められますね。
問2
中央を除いた文字左側と文字右側を比較して一致していればYes
一致していない場合はNoを返す問題です。
単純に文字列操作ができるかという問題ですので大した難しさはないですね。
javaで書く場合substringの書き方が気になったくらいでしょうか。
また文字列比較なので == 演算子ではなく equalsメソッドを利用すべきです。
回答コード
import java.util.Scanner; public class Main { public static void main(String[] args) { // TODO 自動生成されたメソッド・スタブ Scanner sc = new Scanner(System.in); String s = sc.next(); String front = s.substring(0, (s.length()-1)/2); String back = s.substring((s.length()+2)/2, s.length()); if(front.equals(back)) { System.out.println("Yes"); } else { System.out.println("No"); } } }
問3
3問目は縦、横、高さの合計である整数Lから最も体積が大きい直方体を求める問題です。
私この問題みたとき単純に縦 = 横 = 高さが最も体積が大きい値になるという経験則から問題を解きました。
解答を見ると
相加相乗平均不等式？によって等号成立条件は a = b = cになるそうです。
細かいことは理解していませんでしたがひとまずちゃんと解けました。
回答コード
import java.util.Scanner; public class Main { public static void main(String[] args) { // TODO 自動生成されたメソッド・スタブ Scanner sc = new Scanner(System.in); double L = sc.nextDouble(); double S = L / 3; double W = L / 3; double H = L / 3; System.out.println(S * W * H); } }
問4
N個のボールから、k番目のボールを除いた時の同一値となる組み合わせを求める問題です。
最初毎回計算させる方法を考えたのですが、絶対にO(N^2)とかになってめちゃくちゃ時間が掛かりそうだったのでやめました。
最初に全部の組み合わせの合計を求めてから、
k番目の数値を除いた時の組み合わせ数を減算すればO(N)で求められるそうです。
（私が組んだプログラムは無駄が見られますがやっていることは同じような感じです。）
なおすべてint型にすると恐らく途中問題から桁あふれを起こしてWAとなります。
一瞬混乱しましたが、合計値をlong型にすることで無事ACとなりました。
解答も同じ感じでしたね。
回答コード
import java.util.Scanner; public class Main { public static void main(String[] args) { // TODO 自動生成されたメソッド・スタブ Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int[] nums = new int[N]; for(int i = 0; i < N; i++) { nums[i] = sc.nextInt(); } long[] cnt = new long[N]; //各番号ごとの組み合わせを計算する for(int i = 0; i < N; i++) { cnt[nums[i]-1] ++; } long result = 0; //各項目の組み合わせを計算する。 for(int i = 0; i < N; i++) { long count = 0; long num = cnt[i]; for(long j = 1; j < num; j++) { count = count + num - j; } result = result + count; } for(int i = 0; i < N; i++) { System.out.println(result - (cnt[nums[i]-1] - 1)); } } }
問5
枠内に収めてよいホワイトチョコレートの数k個に収まるように
チョコレートブロックを分割しその最小値を求める問題です。
自分にはまだ難しくて解けませんでしたが深さ優先探索を使いつつカット回数の最小値が求められるそうです。
こちらは後日時間があった時に復習します。。。
回答コード（模写）
import java.util.Arrays; import java.util.Scanner; public class Main159_05_copy { public static void main(String[] args){ Scanner sc = new Scanner(System.in); int h = sc.nextInt(); int w = sc.nextInt(); int k = sc.nextInt(); int[][] g = new int[h][w]; for(int i=0; i<h; i++) { char[] c = sc.next().toCharArray(); for(int j=0; j<w; j++) { g[i][j] = c[j]-'0'; } } int[] res = new int[1]; res[0] = 1000000; int[] a = new int[h]; dfs(a, g, h, w, k, res, 1, 0); System.out.println(res[0]); } static void dfs(int[] a, int[][]g, int h, int w, int k, int[] res, int d, int last) { if(d == h) { int[] sum = new int[last+1]; boolean reset = true; int cut = 0; for(int i=0; i<w; i++) { for(int j=0; j<h; j++) { if(g[j][i] == 1) sum[a[j]] += 1; } for(int l=0; l<=last; l++) { if(sum[l] > k) { if(reset) return; Arrays.fill(sum, 0); for(int j=0; j<h; j++) { if(g[j][i] == 1) sum[a[j]] += 1; } cut++; } } reset = false; } res[0] = Math.min(res[0], cut + last); return; } a[d] = last; dfs(a, g, h, w, k, res, d+1, last); a[d] = last + 1; dfs(a, g, h, w, k, res, d+1, last+1); } }
解答
