Editorial for JOI '05 Final Round P1 - Questionnaire


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

生徒数 n は無関係で,アンケートの数 m の大きさの配列を用意すればよい.入力ファイルを読みながら,カウントしていく.ソートは,アンケートの集計をそのままソートするのではなく,その番号(インデックス)が出力に必要なので,インデックスを保存する配列を別に用意して,間接的にソートする.回答数が同じ項目は,アンケートの番号順なので,安定ソートを用いるか,比較の条件に入れてソートすることが重要である.m \le 100 なので,クイックソート (quicksort) など使わなくても十分である.

安定ソート (stable sort) とは,「同じ値をもつデータのソート前の順序が,ソート後も変わらない」ようなソート・アルゴリズムの総称である.例えばこの問題の場合には,アンケートの番号順に回答数を集計した配列を用意しておき,安定ソートによりソートすると,回答数が同じ項目はアンケートの番号順で並ぶようになる.

安定ソートの例としては,アルゴリズムが単純で実装が容易な挿入ソート (insertion sort) がある.挿入ソートの基本的な考え方は,すでに並んでいるデータ a[0], \dots, a[i-1] に対して,a[i] を左から順に比較していき,挿入場所(例えば、a[j] の直後に挿入すべきだったとする)がわかったら,その後ろの部分列 a[j+1], a[j+2], \dots, a[i-1] をずらして,空いた場所に a[i] を挿入する,というものである.


Comments

There are no comments at the moment.