問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう!
※この問題は、2021年1月に開催されたP共通テスト(バンタンテックフォードアカデミー中高プログラミング共通テスト)で出題された問題です。
データを分類する手法の一つに、k 近傍法というものがあります。
これは、クラスを予測したいデータに最も距離が近い k 個のデータのクラスを調べ、それらによる多数決をとり一番多いクラスをそのデータのクラスの予測値とする考え方です。
なお、データのクラス (ラベル) とは、そのデータの属するカテゴリを指し示すものです。例えば、画像に写っている動物が犬なのか猫なのかを判別する際には、「犬」「猫」がクラスとなります。
本問では、2 次元座標を持つデータの分類について考えることにします。
各データは 2 次元座標 (x_i, y_i) とクラス (c_i) を持っています。
クラスがわかっているいくつかのデータがある状態で、クラス不明のデータのクラスを予測することを考えます。
今 6 個のデータがあり、そのうち 5 個のデータのクラスがわかっているとしましょう。
残りの 1 つのデータのクラスを k 近傍法で分類すると、下図のようになります。
? がクラス不明のデータです。
・k = 1 のときは クラス 1 が 1 つなので、? のクラスは 1 と分類されます。
・k = 3 のときは クラス 1 が 1 つ、クラス 2 が 2 つなので、多数決をとって ? のクラスは 2 と分類されます。
・k = 5 のときは クラス 1 が 3 つ、クラス 2 が 2 つなので、多数決をとって ? のクラスは 1 と分類されます。
k 近傍法による分類がどういったものなのかわかったところで、実装してみましょう。
n 個の 2 次元データとそのクラス、そしてクラス不明の 2 次元データが 1 つ与えられます。そして、q 個の k が与えられるので、各 k について k 近傍法による分類をおこなってください。
なお、k 近傍法による分類は分類結果が一意に定まらない場合がありますが、その場合は以下のようにして分類してください。
n
x_1 y_1 c_1
x_2 y_2 c_2
...
x_n y_n c_n
x_0 y_0
q
k_1
k_2
...
k_q
q 行出力してください。i 行目 (1 ≦ i ≦ q) には、k_i 近傍法による分類をおこなったときのデータ (x_0, y_0) のクラスの予測値を出力してください。
また、末尾に改行を入れ、余計な文字、空行を含んではいけません。
すべてのテストケースにおいて、以下の条件をみたします。
・ 入力はすべて整数
・ 5 ≦ n ≦ 100,000
・ -10,000 ≦ x_i, y_i ≦ 10,000 (0 ≦ i ≦ n)
・ i ≠ j ならば (x_i, y_i) ≠ (x_j, y_j)
・ 1 ≦ c_i ≦ 10^9 (1 ≦ i ≦ n)
・ 1 ≦ q ≦ 100,000
・ 1 ≦ k_i ≦ n (1 ≦ i ≦ q)
5
2 0 5
1 1 10
2 -2 100
-1 0 5
0 1 10
0 0
3
1
5
3
5
5
10