問題文

$N$ 個の整数 $A = \{ a_1, a_2, \dots, a_N \}$ が与えられます。 これらの整数を $M$ 個の実数 $B = \{ b_1, b_2, \dots, b_M \}$ に「丸め」たいと考えています。

ここで「丸める」とは、各 $a_i$ を $B$ の中で最も近い $b_j$ $(1 \leq j \leq M)$ に置き換える操作を指します。 ここで「最も近い」とは、 $|a_i - b_j|$ が最小となる $b_j$ のことを意味します。 もし複数の $b_j$ が最も近い場合は、その中から任意の一つを選んで丸めます。

各 $a_i$ を丸めた結果として生じる数値の差の絶対値 $|a_i - b_j|$ を「丸め誤差」と定義します。

あなたの目的は、丸め誤差の総和を最小にするような $B$ の値を選ぶことです。また、そのときの総誤差も求めてください。

制約

• $1 \leq N \leq 200$
• $1 \leq M \leq N$
• $0 \leq a_i \leq 10^5$ $(1 \leq i \leq N$)
• 入力される値はすべて整数である。

入力

入力は以下の形式で与えられます。

出力

以下の形式で出力してください。

• 1 行目に、丸め先の数値を空白区切りで $M$ 個出力してください（順不同で構いません）。
• 2 行目に、最小化された総誤差を出力してください。

サンプル

5 2
1
2
3
4
5

2 4
3

この場合、それぞれの数値は次のように「丸める」ことで総誤差を最小化できます。

1 → 2 (丸め誤差: 1)

2 → 2 (丸め誤差: 0)

3 → 2 または 4 (丸め誤差: 1) この場合、いずれに丸めても誤差は変化しません。

4 → 4 (丸め誤差: 0)

5 → 4 (丸め誤差: 1)

よって総誤差は3となります。

2 2
3
3

3 100000
0

3 2
3
2
4

2 3
1

なお、与えられる数値データはソートされているとは限りません。

問題の背景 ～QLoRAの4-bit NormalFloat Quantizationとは？～

お初にお目にかかります。KCSのAI班です。 今回の三田祭ではChatGPTを用いた音声対話botを展示できるはずです。ぜひ御覧ください。

さて、昨今ではChatGPTを筆頭に「大規模言語モデル(LLM)」が世界を席巻しています。皆さんも一度は使ったことはあるでしょう。その進歩や脅威はもはや説明するまでもありません。 ですが、そういった大掛かりなAIは大掛かりなマシンで動作するものです。サーバールームにびっしりと立ち並ぶコンピューターに数十万円はくだらないようなメモリ。私たちが普段使うPCなんかでは到底太刀打ちない――

――という常識が、今や覆ろうとしています。それが昨年提案された手法「QLoRA」です。

QLoRAでは量子化を行います。この量子化とはいわば軽量化だと思ってもらって構いません。今までは何百GBものメモリが必要だったモデルが48GBメモリに収まるという驚異的なパワーを持ちます。 そこには大きく3つの手法が用いられます。

1. 4-bit NormalFloat (NF4)
2. 量子化定数の再量子化によるメモリフットプリントの平均削減を実現する「ダブル量子化 (double quantization) 」
3. メモリスパイクを管理する「ページ化オプティマイザ (paged optimziers) 」

今回の問題はこの4-bit NormalFloatに注目した問題となっています。

NormalFloat (NFₖ)データ型は、ニューラルネットワークの重みなどを効率的に量子化（デジタル化）するための方法です。 量子化とは、連続的な値を有限のビン（区間）に分けて、各ビンに代表値を割り当てることです。 kビットの場合 $2^k$ 個の量子化レベル（代表値）を持ちます。

こう言うと難しそうですね。でもやっていることは単純で、この問題を $M=2^k$ にしただけです。

さらにQLoRAではもっと単純で、なんと数値が正規分布に従うことがわかっています。よって正規化の後に [-1.0, -0.6961928009986877, -0.5250730514526367,-0.39491748809814453, -0.28444138169288635, -0.18477343022823334,-0.09105003625154495, 0.0, 0.07958029955625534, 0.16093020141124725,0.24611230194568634, 0.33791524171829224, 0.44070982933044434,0.5626170039176941, 0.7229568362236023, 1.0]（QLoRA: Efficient Finetuning of Quantized LLMsのAppendex Eより引用） のいずれかに丸めることで、量子化を高速に済ませつつ誤差を少なくすることができることがわかっています。 このようにして大規模言語モデルのパラメータを軽量化することができます。

現在は様々なライブラリが整い、こうした量子化されたモデルをお手元のPCで動かすことができます。ぜひ皆さんも大規模言語モデルをローカル環境で動かしてみてはいかがでしょうか？