概要

信号が \(N\) 個の中継器を順番に通過するとき、各中継器で強度が一定の割合で減衰していく様子をシミュレーションし、最終的な信号強度を求める問題です。

考察

問題の理解

信号の強度 \(C\) が中継器 \(i\) を通過すると、新しい強度は \(\lfloor C \times A_i / 100 \rfloor\) になります。これは「\(A_i\) パーセントの効率で伝送される」ことを意味します。

具体例で確認

例えば、\(M = 1000\)、\(N = 3\)、\(A = [50, 80, 90]\) の場合： 1. 最初の強度: \(C = 1000\) 2. 中継器1通過後: \(C = \lfloor 1000 \times 50 / 100 \rfloor = 500\) 3. 中継器2通過後: \(C = \lfloor 500 \times 80 / 100 \rfloor = 400\) 4. 中継器3通過後: \(C = \lfloor 400 \times 90 / 100 \rfloor = 360\)

なぜ単純なシミュレーションで大丈夫か

この問題では、各中継器を1つずつ順番に処理する必要があります。

• 中継器は最大 \(10^5\) 個
• 各中継器での計算は \(O(1)\)（掛け算と割り算のみ）

よって、全体で \(O(N)\) の計算量となり、十分高速です。

注意点：床関数の扱い

問題文の \(\lfloor C \times A_i / 100 \rfloor\) は「切り捨て除算」を意味します。Python の // 演算子は整数同士の除算で切り捨てを行うため、C * a // 100 と書けば正しく計算できます。

アルゴリズム

1. 信号の強度 \(C\) を初期値 \(M\) で初期化する
2. 各中継器 \(i = 1, 2, \ldots, N\) について順番に以下を行う：
   • \(C \leftarrow \lfloor C \times A_i / 100 \rfloor\)
3. 最終的な \(C\) の値を出力する

C = M
for each a in A:
    C = floor(C * a / 100)
output C

計算量

• 時間計算量: \(O(N)\)
  • \(N\) 個の中継器それぞれに対して \(O(1)\) の計算を行う
• 空間計算量: \(O(N)\)
  • 配列 \(A\) を保存するために \(O(N)\) の空間が必要
  • （ストリーム処理にすれば \(O(1)\) にもできる）

実装のポイント

• 整数演算の使用: Python では // を使うことで整数の切り捨て除算ができます。/ を使うと浮動小数点数になり、精度の問題が生じる可能性があるため避けましょう。

• 大きな数の扱い: \(M\) は最大 \(10^{18}\) ですが、Python は任意精度整数をサポートしているため、オーバーフローの心配はありません。C++ などを使う場合は注意が必要です。

• 掛け算を先にする: C * a // 100 の順序で計算することで、精度を保ちながら正しい結果が得られます。もし先に a // 100 を計算すると、\(a < 100\) のとき 0 になってしまいます。

  ソースコード

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

C = M
for a in A:
    C = C * a // 100

print(C)

---

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