ABC#19 C問題「高橋くんと魔法の箱」
コメント
非常に悔しかった問題。最初問題文見て関数のブラックボックスの話かなって思った。(てかそうかな?)
ポイントは2つ。
- xと2xを箱にいれたら出てくる整数が同じ、ということは入力した数字を奇数になるまで2で割り続けてあげればどんな数字も奇数になり、グループ分けが可能。
- あとは、違う種類の奇数をカウントすればいい。
一つは気づいてちゃんとできたが、もう一つの違う種類の奇数のカウント方法がO(2^n)になり撃沈…。
ただ、解説を見てHashSetの使い方を学ぶことができたからよかったかな。
コード
途中点のコードのみ。
完全解答のコードはAtCoderの社長さんがあげているのでそちらを参照に。
import java.util.Scanner; //20点分のみクリア //→実行時間O(n^2)だから public class Main { void run() { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[] a = new int[n]; // 全ての数を奇数に for (int i = 0; i < a.length; i++) { a[i] = sc.nextInt(); while (a[i] % 2 == 0) { a[i] /= 2; } } // 複数あるものは一つだけ残しあとは0を代入 for (int i = 0; i < a.length; i++) { int x = a[i]; for (int j = i + 1; j < a.length; j++) { if (x == a[j]) { a[j] = 0; } } } //0をflagとして残りをカウント int count = 0; for (int i = 0; i < a.length; i++) { if (a[i] > 0) { count++; } } System.out.println(count); sc.close(); } public static void main(String[] args) { new Main().run(); } }