AtCoder振り返り：161(A~D)
AtCoder Beginner 161に参加しました。
結果など振り返っていきます。
成績
AtCoderはA~Cまでの3完でした。
前回4完までできていたので、今回は3完は悔しいですが安定はしてきているのでこのままいけば茶コーダーまでは行けそうですかね。
パフォーマンスは470でしたので茶色相当ですね。
しかし3完したのに順位低くないか…？コロナの影響で参加者増えているのかな？
問題
問1
箱A, B, Cを引数と渡されて、以下の手順で処理した結果を返す問題です。
例えば引数が
A = 1, B = 2, C = 3の場合、
①A = 2, B = 1とする。
②A = 3, C = 2とする。
結果、3, 1, 2が返却されるという問題ですが、正直わざわざ入れ替えのロジックを組む必要はありません。
結果は不変なので出力順をC, A, Bと出力すればいいだけです。
回答コード
import java.util.Scanner; public class Main { public static void main(String[] args) { // TODO 自動生成されたメソッド・スタブ Scanner sc = new Scanner(System.in); int X = sc.nextInt(); int Y = sc.nextInt(); int Z = sc.nextInt(); System.out.println(Z); System.out.println(X); System.out.println(Y); } }
問2
N種類の商品に対して人気商品M個を取得する問題です。
人気商品 >= 1/4Mの条件を満たすものとしてるのですが、
この問題は1つでも条件を満たさないデータがあれば"No"を返します。
したがって一つ一つ条件を満たすかチェックする必要はなく
ランク上位からM個目のデータが条件を満たすかチェックすればよいです。
回答コード
もっと簡単にできたと思うのですが、今回はクイックソートを追加しました。
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[] A = new int[N]; int minMax = 0; int sum = 0; for(int i = 0; i < N; i++) { A[i] = sc.nextInt(); sum = sum + A[i]; } quick_sort(A, 0, N-1); double s = A[N-M]; double dsum = sum; if(s >= (dsum / (4 * M))) { System.out.println("Yes"); } else { System.out.println("No"); } } static void quick_sort(int[] d, int left, int right) { if (left>=right) { return; } int p = d[(left+right)/2]; int l = left, r = right, tmp; while(l<=r) { while(d[l] < p) { l++; } while(d[r] > p) { r--; } if (l<=r) { tmp = d[l]; d[l] = d[r]; d[r] = tmp; l++; r--; } } quick_sort(d, left, r); // ピボットより左側をクイックソート quick_sort(d, l, right); // ピボットより右側をクイックソート } }
問3
atcoder.jp
初期値Nに対して整数Kの絶対値差で最小の値を求める問題です。
整数は10^18のためlong型で処理する必要があります。
また、単純にループ処理するとTLEになってしまうとおもうので意味はないです。
ただ結局ループすることはなくN / Kのあまりが基準となりますので殆ど計算量はありません。
余りを求めた後 「あまり」 または 「あまりとKの差」どちらか小さい値を採用すれば求められます。
回答コード
import java.util.Scanner; public class Main { public static void main(String[] args) { // TODO 自動生成されたメソッド・スタブ Scanner sc = new Scanner(System.in); long N = sc.nextLong(); long K = sc.nextLong(); long result = N; //あまり求める if(result > K) { result = result % K; } //差分求める long tmp = result; if(tmp < K) { tmp = K - tmp; } else { tmp = tmp - K; } if(result > tmp) { result = tmp; } if(result > N) { result = N; } System.out.println(Math.abs(result)); } }
問4
ルンルン数を求める問題です。
1234 1 334 など隣り合った数値が±1に収まる数をルンルン数としています。
私はこれが分からずTLEとなってしまいました。
解説では以下の通りです。
この問題は、Queue というデータ構造を用いることで効率的に解くことができます。まず、空の
Queue を 1 つ用意し、1, 2, ..., 9 を順に Enqueue します。それから、以下の操作を K 回行います。
• Queue に対して Dequeue を行う。取り出した要素を x とする。
• x mod 10 ̸= 0 なら、 10x + (x mod 10) − 1 を Enqueue する。
• 10x + (x mod 10) を Enqueue する。
• x mod 10 ̸= 9 なら、 10x + (x mod 10) + 1 を Enqueue する。
K 回目の操作において取り出した数が、 K 番目の Lunlun Number となっています。
そして、上記アルゴリズムをプログラムに落とし込むと以下の通りとなります。
解答コード
import java.util.ArrayDeque; import java.util.Deque; import java.util.Scanner; public class Main161_04_renew { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int k = sc.nextInt(); sc.close(); Deque<Long> num = new ArrayDeque<>(); for (int i = 1; i <= 9; i++) { num.add((long) i); } long x = 0; for (int i = 1; i <= k; i++) { x = num.poll(); for (int j = -1; j <= 1; j++) { long d = x % 10 + j; if (d < 0 || d > 9) { continue; } num.add(x * 10 + d); } } System.out.println(x); } }
