じょん・どうのブログ

趣味と勉強したことを吐き出すブログです。主に競プロ、Unity、トレカをやってます！

ABC162解きました。（Java使用、ネタバレ注意！）

AtCoder プログラミング 数学 競技プログラミング

　どうも、じょんです。今回はABC162に参加してきたので、C問題とD問題を紹介。今回はまだ新参者のぼくにとっては、Cがむずかったので、紹介をば。

 

コンテストページのリンク

https://atcoder.jp/contests/abc162/tasks

 

　C問題は次の通り。

∑a=1K∑b=1K∑c=1Kgcd(a,b,c) を求めてください。

ただし、gcd(a,b,c) は a,b,c の最大公約数を表します。

 ちょっと分かりづらい！思ったので、今回は入力例もコピペしときます。

 

入力例 1 Copy

Copy
2

出力例 1 Copy

Copy
9

gcd(1,1,1)+gcd(1,1,2)+gcd(1,2,1)+gcd(1,2,2) +gcd(2,1,1)+gcd(2,1,2)+gcd(2,2,1)+gcd(2,2,2) =1+1+1+1+1+1+1+2=9

となるため、答えは 9 です。

 では、この問題を解く上でどうするかなんですが、僕は何も思いつかなかったので、とりあえず指示通りに組むことに。組んだコードは以下の通り（拙いコードですみません）。

  1. import java.util.*;
  2. import java.util.ArrayDeque;
  3. import java.util.Queue;
  4. import java.math.RoundingMode;
  5. import java.math.BigDecimal;
  6.  
  7.  
  8. public class Main{
  9. public static void main(String[] args){
  10. Scanner sc = new Scanner(System.in);
  11. long k = sc.nextLong();
  12. long sum = 0;
  13. for(int i = 1; i <= k; i++) {
  14. for(int j = i; j <= k; j++) {
  15. for(int n = j; n <= k; n++) {
  16. if(i==j&&j==n) {
  17. sum+=solve(i,j,n);
  18. }
  19. else if(i!=j&&j!=n&&n!=i) {
  20. sum+=solve(i,j,n)*6;
  21. }
  22. else{
  23. sum+=solve(i,j,n)*3;
  24. }
  25. }
  26. }
  27. }
  28. System.out.println(sum);
  29. }
  30. private static long solve(long i, long j, long n) {
  31. long tmp;
  32. long a = i;
  33. long b = j;
  34. long gcd;
  35. while((tmp = b % a) != 0) {
  36. b=a;
  37. a=tmp;
  38. }
  39. gcd = a;
  40. long c;
  41. if(n<gcd) {
  42. a = n;
  43. c = gcd;
  44. }
  45. else {
  46. a = gcd;
  47. c = n;
  48. }
  49. while((tmp = c % a) != 0) {
  50. c=a;
  51. a=tmp;
  52. }
  53. return a;
  54. }
  55. }

 インデントがなくて見づらいですね（バグ発見のために使用した文字列出力を消したので、行数の番号に違和感があります）。普段、エクリプスを使っているのですが、エクリプス上では（バグ発見のために使用した文字列出力がある状態で）2秒以上かかっていたので、大丈夫かな？と思ったのですが、通りました。入力制約の最大値である、200をいれても、183msで終わりました（実行時間には誤差があります）！ちなみに、これを解くにあたって使用したアルゴリズムはユークリッドの互除法です！

 

ユークリッドの互除法の解説（スタディプラス様）

https://www.studyplus.jp/412

 

大学受験で割と慣れ親しんでいたものがアルゴリズムの一つだったことに驚きました！

　それでは、次はD問題。問題はこちら。

R, G, B のみからなる、長さ N の文字列 S があります。

以下の 2 つの条件をともに満たす組 (i, j, k) (1≤i<j<k≤N) の数を求めてください。

  • Si≠Sj かつ Si≠Sk かつ Sj≠Sk である
  • j−i≠k−j である

 　こちらも高校数学で勉強する、場合の数の問題を解く上で基本的な考え方を持っていると楽です。それは、「全部1から数え上げるよりも、全体の数から条件を満たさないものを引く方が楽である場合もある」というものです！え？そんなことかって？そうです。そんなことです。でもこの考え方、数字に強い人はいざ知らず、そうでもない人（数字に対して強くも弱くもない人も含めて）にとっては意外とスッと出てこないんです（僕だけだったらすみません）！僕も時間内にはコードが書ききれませんでした。でも、悔しかったので、コンテストが終わった翌日に自分なりに書いてみて通ったコードがこちら。

  1. import java.util.*;
  2. import java.util.ArrayDeque;
  3. import java.util.Queue;
  4. import java.math.RoundingMode;
  5. import java.math.BigDecimal;
  6.  
  7.  
  8. public class Main{
  9. public static void main(String args){
  10. Scanner sc = new Scanner(System.in);
  11. int n = sc.nextInt();
  12. String S = sc.next();
  13. char s = S.toCharArray();
  14. long ans = 0;
  15. long Rnum = 0;
  16. long Bnum = 0;
  17. long Gnum = 0;
  18. for(int i = 0; i < n; i++) {
  19. if(s[i] =='R') {
  20. Rnum++;
  21. }
  22. if(s[i] =='B') {
  23. Bnum++;
  24. }
  25. if(s[i] =='G') {
  26. Gnum++;
  27. }
  28. }
  29. ans+=Rnum*Bnum*Gnum;
  30. for(int i = 0; i < n; i++) {
  31. for(int j = i+1; j < n; j++) {
  32. int k = 2*j-i;
  33. if(k<n&&s[i]!=s[j]&&s[j]!=s[k]&&s[k]!=s[i]) {
  34. ans--;
  35. }
  36. }
  37. }
  38. System.out.println(ans);
  39. }
  40. }

 先ほどの発想があれば、コード自体はB問題やC問題と同じくらいのレベルでした。くっそ～。

 

今後はD問題を中心に練習していきます！

読んでくれてありがとうございました！