AtCoder振り返り：162(A~D)
2020/4/12(日) に参加したAtCoder162の結果を振り返ります。
成績
前回よりレーティングが-5でした。
レーティングが落ちたの初めてです。
原因としては以下2点
- 回答に時間が掛かった。
昨日は障害が起きており問題がすぐに回答してもらえなかったというのがありました。とはいえ単純にコーディングが遅かったというものあります。
- 回答をミスした。
提出するクラス名が「Main」でなくてはいけないのですが
誤って別のクラス名で提出してました。この問題結構やりがちです。
あと見直したらA問正解してませんでした。。。（提出ミス。。。）
後地味に今回からAtCoderの対応言語が変わってました。
後でまとめておこう。
パフォーマンスも今までで最低を取得しているので、かなりショックです。
次回参加するときは前日に勉強しておくようにします。。。
問題
問1
問Aは3桁の値いずれかに"7"が含まれているかをチェックする処理です。
単純に以下の通り各桁の文字チェックすればOKです。
■回答コード
import java.util.Scanner; public class Main162_011 { public static void main(String[] args) { // TODO 自動生成されたメソッド・スタブ Scanner sc = new Scanner(System.in); String N = sc.next(); char seven = '7'; if(N.charAt(0) == seven || N.charAt(1) == seven || N.charAt(2) == seven) { System.out.println("Yes"); } else { System.out.println("No"); } } }
問2
最大値10^6まであるFizzBuzz問題です。
通常のFizzBuzzと違うのは3でも5でも割り切れない数値の総和を求めるという処理です。
こちらも特段難しくはなかったです。総和の変数はlong型にするのを忘れずに
■回答コード
import java.util.Scanner; public class Main { public static void main(String[] args) { // TODO 自動生成されたメソッド・スタブ Scanner sc = new Scanner(System.in); int N = sc.nextInt(); long sum = 0; for(int i = 1; i <= N; i++) { if(i % 3 != 0 && i % 5 != 0) { sum = sum + i; } } System.out.println(sum); } }
問3
一瞬シグマが見えた瞬間「終わったー」と思いましたが、ただの階乗でした。
階乗が３つ(a, b, c)ありますが、ユークリッドの互除法と3重ループを組み合わせることで求めることができました。
■回答コード
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 sum = 0; for(int i = 1; i <= N; i++) { for(int j = 1; j <= N; j++) { for (int k = 1; k <= N; k++) { sum = sum + gcd(i, j, k); } } } System.out.println(sum); } public static final int gcd(final int... param) { final int len = param.length; int g = getCommonDivisor(param[0], param[1]); //gcd(a, b) は以前作ったもの for (int i = 1; i < len - 1; i++) { g = getCommonDivisor(g, param[i + 1]); //gcd(a, b) は以前作ったもの } return g; } private static int getCommonDivisor(int x, int y) { int biggerNum = Math.max(x, y); int smallerNum = Math.min(x, y); // 大きい方から小さい方を割った余を求める int surplus = biggerNum % smallerNum; // 割り切れていれば、それを返す if (surplus == 0) { return smallerNum; } // 割り切れなければ再帰的に自信を呼び出す surplus = getCommonDivisor(smallerNum, surplus); return surplus; } }
問4
"R", "G", "B"という文字列のみが渡され、
上記3つの組み合わせが成り立つ件数が何件あるかを求めます。
制約として以下の条件が存在します。<<制約>>
- 1 <= i < j < k < Nであること
- Si ≠ Sj かつ Si ≠ Sk かつ Sj ≠ Skであること
- J - i ≠ k -j であること
これを馬鹿正直に組んだロジックは以下の通りです。
しかし、3重ループとなるためO(n^3)となります。単純に遅すぎてしまいLTEでした。
■誤回答(一部の問題でTLE)
import java.util.Scanner; public class Main { public static void main(String[] args) { // TODO 自動生成されたメソッド・スタブ Scanner sc = new Scanner(System.in); int N = sc.nextInt(); String S = sc.next(); int[] rgbs = new int[N]; int sum = 0; for(int i = 0; i < N; i++) { char c = S.charAt(i); if(c == 'R') { rgbs[i] = 1; //R continue; } if(c == 'G') { rgbs[i] = 2; //G continue; } if(c == 'B') { rgbs[i] = 4; //B } } for(int i = 0; i < N; i++) { for(int j = i+1; j < N; j++) { if(rgbs[i] == rgbs[j]) { continue; } int x = rgbs[i] + rgbs[j]; int y = 7 - x; for(int k = j+1; k < N; k++) { //条件2 if(j - i == k - j) { continue; } if(rgbs[k] == y) { sum++; } } } } System.out.println(sum); } }
ではどうするのか？ですがこれは2重ループで処理ができます。
RGBのうち、
R(int i) とG(int k)の回数だけ繰り返します。
B(int j)ですが、bの総数を事前に記録しておき基本的に総和量を加算する（※例外に該当するデータ量を都度除く）ことで計算量が減ります。
import java.util.ArrayList; import java.util.HashSet; import java.util.List; import java.util.Scanner; import java.util.Set; public class Main162_04 { public static void main(String[] args) { try (Scanner scn = new Scanner(System.in)) { final int N = scn.nextInt(); final char[] S = scn.next().toCharArray(); Set<Double> bs = new HashSet<>(4000); for (int b = 0; b < N; b++) { if (S[b] != 'B') continue; bs.add((double) b); } List<Integer> gs = new ArrayList<>(4000); for (int g = 0; g < N; g++) { if (S[g] != 'G') continue; gs.add(g); } long sum = 0; for (int r = 0; r < N; r++) { if (S[r] != 'R') continue; for (int g = 0; g < gs.size(); g++) { double max = Math.max(r, gs.get(g)); double min = Math.min(r, gs.get(g)); sum += bs.size() - (bs.contains(max - (max - min) * 2) ? 1 : 0) //bnx - (bs.contains(max - (max - min) / 2) ? 1 : 0)//nbx - (bs.contains(max + (max - min)) ? 1 : 0)//nxb ; } } System.out.println(sum); } } }
