ARC 101-200/ARC198B - Rivalry - 競技プログラミング用 知識集積所

---

問題

ARC198B

必要知識

簡単な内容は省略

• 必要十分条件（未作成）

考え方

クエリ数が多いので、x,y,zの値からスパッと判断しなければならない。
そのためには、条件を満たす必要十分条件（未作成）を考えなければならない。

まず、0について。
0は、両サイドに0未満の数が0個という条件だが、そもそも0未満の数などどこにも存在しない。
よって、どんな位置にどんな位置関係で存在しても条件を満たす。

次に、2について。
2は、両サイドに2未満の数が2個という条件なので、隣に2がなければそれでいい。

最後に、1について。
1は、両サイドに1未満の数が1個という条件なので、どちらか片側のみが0ということになる。
よって、どこかの0の隣（0に挟まれない）という位置にしか置けない。

ということは、0が存在しない場合、1も存在できず、すると2も存在できず、入力条件に反する。
したがって、0は少なくとも1つあるので、円環を0で区切って考えることにする。

条件より、0と0の間は「00」「0110」「020」「01210」「0120」「0210」のどれかの形でしかありえない。
0は両区間にまたがることも考えると、

• 1は0の2倍までしか存在できない
• 2は0と同じ数までしか存在できない
• 2が存在しない場合、1は偶数個でなければ入れられない

というのが必要条件である。

逆にこれら3つの条件を満たす場合、

• とりあえず0を全部円環に並べる
• 2を全部異なる区間に1つずつ分けて0と0の間に入れる
• 1を、まずは2がある区間を1つ残すように2個セットで入れていく
• 最後に1つ1だけ1が残った場合は、それを2がある区間に入れる

で条件を満たす数列が構成できる。
したがって、前述の3つの条件で必要十分条件（未作成）となっているので、これを用いて高速で判定していけばいい。

解答例

解答例

注意点

別解