DISCO_2016_qual/

README

DISCO presents ディスカバリーチャンネル プログラミングコンテスト2016 予選 過去問感想

Last Change: 2020-05-24 00:33:42.

A問題（@2020-05-24）

文字列処理ともとれるかもだが、自分はスライスの操作でやった。

B問題（@2020-04-18）

嘘解法から抜け出せなかった。。 面白さと部屋番号の小さい順に安定ソートして、前から見たときに部屋番号が反転していたら次の周回に回す必要がある、 と考えた。

この解法だと面白さが順列の場合でないと正解できない。

同じ面白さが複数あったり間が抜けていたりすると（※抜けている場合の反例は見つけていないが）、 シミュレーションをする必要がある。 今回は、面白さの値の範囲が狭いため、バケットソートが適用でき、バケット構造から O(n) でシミュレーションができる。

最後に見学する部屋が最初の部屋の場合は、コーナーケースになるため、更に注意が必要。

嘘解法チェックサンプルの一例

in:
6
1 3 5 1 1 3

out:
2

↑が 3 になるとアウト。