2014-儀式-解説
- 正解
- 図をわかりやすく描き直すと，次のようになります。
- 対話形式の問題では，作成した行事予定がこの図に当てはまる順序になっていれば正解です。
- たとえば「Choir Singing(聖歌隊合唱), Boring Speeches(退屈な挨拶) , Lottery(抽選会), Drum Roffle(太鼓連打), Musical Intemezzo(間奏曲演奏), Fanfare(ファンファーレ), Fireworks(花火), Thank you(謝辞)」は正解の1つです。
- 他にも以下が正解です。（最初の「Choir Singing」と最後の「Thank you」は省略しています。）
- 「Drum Roffle」 - 「Boring Speeches」 - 「Lottery」 - 「Musical Intermezzo」 - 「Fanfare」 - 「Fireworks」
- 「Drum Roffle」 - 「Boring Speeches」 - 「Musical Intermezzo」 - 「Fanfare」 - 「Fireworks」 - 「Lottery」
- 「Drum Roffle」 - 「Boring Speeches」 - 「Musical Intermezzo」 - 「Fanfare」 - 「Lottery」 - 「Fireworks」
- 「Drum Roffle」 - 「Boring Speeches」 - 「Musical Intermezzo」 - 「Lottery」 - 「Fanfare」 - 「Fireworks」
- 「Boring Speeches」 - 「Drum Roffle」 - 「Lottery」 - 「Musical Intermezzo」 - 「Fanfare」 - 「Fireworks」
- 「Boring Speeches」 - 「Drum Roffle」 - 「Musical Intermezzo」 - 「Fanfare」 - 「Fireworks」 - 「Lottery」
- 「Boring Speeches」 - 「Drum Roffle」 - 「Musical Intermezzo」 - 「Fanfare」 - 「Lottery」 - 「Fireworks」
- 「Boring Speeches」 - 「Drum Roffle」 - 「Musical Intermezzo」 - 「Lottery」 - 「Fanfare」 - 「Fireworks」
- 非対話形式の問題では，図の規則に合っていない選択肢は "Drum, Musical, Fanfare, Boring, Lottery, Fireworks" です。"Boring" が "Musical" の後に置かれてしまっています。
- 図をわかりやすく描き直すと，次のようになります。
- 解説
- この問題では，対象を「ノード（頂点）」と「エッジ（辺）」で表すグラフ表現を扱っています。
- この問題で，儀式の行事は順序を示す矢印で結ばれた有向グラフとして表現されています。
- コンピュータでは，グラフ構造を利用することで複雑なデータを表現したり、鉄道の経路探索のような複雑な問題を扱ったりしています。
- この問題の図を上の図のように並び替えることはトポロジカルソートと呼ばれるもので，エッジを出している（矢印の元）ノードが，そのエッジが入る（矢印の先）ノードよりも前に置くように並び替えます。これにより，この問題のように前に行われていなければいけない行事があるときのスケジューリングを考えることができます。
- 出題国: この問題はフランスで作成されました。
注があるものを除き, このサイトの内容物は
