エイシング プログラミング コンテスト 2020 に参加しました (AtCoder)
お久しぶりとなります。
エイシング プログラミング コンテスト 2020 に参加しました。
久しぶりのコンテストだったので、感覚を忘れていて、リハビリ感覚です。
ちなみに、前回の記事はこちらです。(だいぶ前となってしまいますが・・・)
developer-bpeldi2oerkd8.hatenablog.com
準備
ほとんどできていないです。
これから少しずつでも復帰できたらなと思います。
経過
前回からしばらく空いていたので、とにかく感覚を取り戻すのに精一杯でした。
A・B問題をさくっと解き、C問題に移りました。
C問題はぱっと見わからず、式変形を試みたりしましたが、
x^x+y^y+z^z+x*y+y*z+z*x >= 1となる関係から、
x=1, y=1と考えてもz=100くらいだと思ったので、全探索で行きました。
余裕をもってx, y, z <= 200で3重ループを回すと問題なく通りました。
(ここまで40分ほど)
import java.io.PrintWriter; import java.util.Arrays; import java.util.Scanner; public class Main { //java11 public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int[] count = new int[N+1]; Arrays.fill(count, 0); for(int x=1; x<=200; x++) { for(int y=1; y<=200; y++) { for(int z=1; z<=200; z++) { int n = x*x+y*y+z*z+x*y+y*z+z*x; if(n <=N) { count[n]++; } } } } PrintWriter pw = new PrintWriter(System.out); for(int i=1; i<=N; i++) { pw.println(count[i]); } pw.flush(); } }
D問題は再帰と進数の変換を用いて実装しましたが、N=2*10^5と大きいので、
途中計算の記憶をMapで実装しました。
しかし、サンプルは通したのですが、ほとんどREとなってしまいました。
原因については、調べます。
import java.io.PrintWriter; import java.util.HashMap; import java.util.Map; import java.util.Scanner; public class Main { //java11 // static int[] fn; static Map<Integer, Integer> fn; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); String X = sc.next(); // fn = new int[(int)Math.pow(2, N)]; // fn = new int[10000000]; fn = new HashMap<>(); // Arrays.fill(fn, -1); PrintWriter pw = new PrintWriter(System.out); for(int i=0; i<N; i++) { StringBuilder sb = new StringBuilder(X); //bit反転 if(X.charAt(i) == '0') { sb.setCharAt(i, '1'); }else { sb.setCharAt(i, '0'); } int Xi = Integer.parseInt(sb.toString(), 2); pw.println(fn(Xi)); } pw.flush(); } public static int fn(int n) { if(fn.get(n) != null) { return fn.get(n); } if(n == 0) { // fn[n] = 0; fn.put(n, 0); return fn.get(n); } if(popcount(n) == 0) { fn.put(n, fn(0) + 1); }else { fn.put(n, fn(n % popcount(n)) + 1); } return fn.get(n); } public static int popcount(int n) { return Integer.bitCount(n); } }
結果
久しぶりにしてはという感じですが、やはり問題を解かないとレベルは上がっていきませんね。
他のことでも忙しいのですが、なんとか時間を作って頑張りたいと思います。
というわけで、エイシング プログラミング コンテスト 2020の結果でした。
次回も参加したいと思います。