問題3 解説

 製品別の合計を求めることは容易にできる. 問題のポイントは,この製品名の順序を考慮することにある. 通常,文字列の順序は「辞書式順序」を用いることが多い. まず,この辞書式順序について説明しよう.その名前が示すように,辞書式順序とは 英語の辞書のような順序に文字列を並べる順序である. 例えば,ad は abc の後ろに並べられる(abc<ad と書くことにする).
 厳密には辞書式順序は次のように定義する.2つの文字列 X, Y が

  X = x1 x2 ... xm,   Y = y1 y2 ... yn    (xi と yj は 1 文字)

であるとき, x1 = y1, ..., xi-1 = xi-1, xi<yi となる i が存在するならば,X < Y と定める. ここで,xi<yi はあらかじめ決められている「文字の間の順序」である.xi または yi の部分に文字がないときは,そこには最小の文字があると考える. 英字の場合,文字の間の順序はアルファベット順である.

 では,この問題で与えられている順序はどのようなものかというと,数の順序のような順序である.例えば,ad と abc をそれぞれ 16 進数により表された数と考えると,[ad]16 = [173]10,[abc]16 = [2748]10 なので,ad<abc である(ここで,[○○○]p は,○○○が p 進数であることを表す). 数は桁数が小さいものが小さく,同じ桁数では上位の桁から比べて最初に異なる数の順になる.これを文字列の比較に使った挿入ソート を用いると,合計を求めながら並べることが容易になる. 挿入ソート (insertion sort) とは,すでにソートされているデータがあるとき,ソート済みのデータを左から順に 1 つずつ次に挿入するべきデータと比べることにより,挿入する位置を見つけて,そこへ挿入する,ということを繰り返すソート法のことである.