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.
Submitting an official solution before solving the problem yourself is a bannable offence.
生徒数 は無関係で,アンケートの数
の大きさの配列を用意すればよい.入力ファイルを読みながら,カウントしていく.ソートは,アンケートの集計をそのままソートするのではなく,その番号(インデックス)が出力に必要なので,インデックスを保存する配列を別に用意して,間接的にソートする.回答数が同じ項目は,アンケートの番号順なので,安定ソートを用いるか,比較の条件に入れてソートすることが重要である.
なので,クイックソート (quicksort) など使わなくても十分である.
安定ソート (stable sort) とは,「同じ値をもつデータのソート前の順序が,ソート後も変わらない」ようなソート・アルゴリズムの総称である.例えばこの問題の場合には,アンケートの番号順に回答数を集計した配列を用意しておき,安定ソートによりソートすると,回答数が同じ項目はアンケートの番号順で並ぶようになる.
安定ソートの例としては,アルゴリズムが単純で実装が容易な挿入ソート (insertion sort) がある.挿入ソートの基本的な考え方は,すでに並んでいるデータ に対して,
を左から順に比較していき,挿入場所(例えば、
の直後に挿入すべきだったとする)がわかったら,その後ろの部分列
をずらして,空いた場所に
を挿入する,というものである.
Comments