競プロ・数学を頑張りたい(願望)

競技プログラミングの問題を解いたときや数学に関してのメモにしようと思っています。競プロはAOJを、数学は数検準1を目標で。

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();
	}

}