概要

\(N\) 種類のお菓子をそれぞれ \(M\) 人に均等に配るとき、各種類について1人あたりの個数（商）と余りを求める問題です。基本的な割り算（除算と剰余）を行えば解けます。

考察

問題文をよく読むと、各種類のお菓子の個数 \(A_i\) を友人の人数 \(M\) で割ったときの 商 \(Q_i\) と 余り \(R_i\) を求めよ、ということが分かります。

• 商 \(Q_i = \lfloor A_i / M \rfloor\)：1人あたりに配れるお菓子の個数
• 余り \(R_i = A_i \mod M\)：配りきれずに余るお菓子の個数

例えば、\(A_i = 10\)、\(M = 3\) の場合を考えます。10個のお菓子を3人に配ると、1人あたり \(\lfloor 10 / 3 \rfloor = 3\) 個配れて、\(10 \mod 3 = 1\) 個余ります。実際、\(10 = 3 \times 3 + 1\) が成り立っています。

この問題では特別なアルゴリズムは不要で、素朴に各 \(A_i\) について割り算をすれば十分です。\(N\) が最大 \(2 \times 10^5\) ですが、各要素に対して \(O(1)\) の演算しか行わないため、時間的にも問題ありません。

アルゴリズム

1. \(N\) と \(M\) を読み込む。
2. 配列 \(A\) を読み込む。
3. 各 \(A_i\) に対して、\(Q_i = A_i \div M\)（整数除算）、\(R_i = A_i \mod M\)（剰余）を計算する。
4. 各 \(i\) について \(Q_i\) と \(R_i\) を1行ずつ出力する。

計算量

• 時間計算量: \(O(N)\) — 各お菓子について1回ずつ割り算と剰余を計算するだけです。
• 空間計算量: \(O(N)\) — 入力の配列と出力用の文字列リストを保持します。

実装のポイント

• 出力の高速化: Python では print を \(N\) 回呼び出すと遅くなることがあります。そこで、出力をリストに溜めておき、最後に '\n'.join(out) で一括出力しています。\(N\) が最大 \(2 \times 10^5\) のため、この工夫は実行時間の短縮に有効です。

• 入力の高速化: sys.stdin.readline を使うことで、標準の input() より高速に入力を読み取っています。

• Python では // 演算子が整数の切り捨て除算、% 演算子が剰余を返します。\(A_i \geq 0\) かつ \(M \geq 1\) なので、負の数に関する除算の挙動を気にする必要はありません。

  ソースコード

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
A = list(map(int, input().split()))

out = []
for a in A:
    out.append(f"{a // M} {a % M}")
print('\n'.join(out))

この解説は claude4.6opus-thinking によって生成されました。