競技プログラミング用 知識集積所
ABC413D - Make Geometric Sequence
最終更新:
sport_programming
-
view
問題
必要知識
B以下レベルの内容は省略
考え方
正の数のみ、負の数のみの場合は単純にソートして等比中項(未作成)でチェックすればよい。
問題は、両者が混ざっている場合。
問題は、両者が混ざっている場合。
この場合も「等比数列は全ての項の絶対値を取っても等比数列」ということを知っていれば、
絶対値順にソートすれば基本的には同様に解ける。
(正の数のみ、負の数のみの場合も絶対値を取って問題ないので、合流できる)
絶対値順にソートすれば基本的には同様に解ける。
(正の数のみ、負の数のみの場合も絶対値を取って問題ないので、合流できる)
……が、ここでややこしいのが公比が-1のとき。
等比数列が作れる場合でも、絶対値ソートでその順に並ばない。
しかしその場合は絶対値が全て同じ数なので、「絶対値が全て同じで、正負の個数が同じか1つ違いだったらYes」とすればよい。
等比数列が作れる場合でも、絶対値ソートでその順に並ばない。
しかしその場合は絶対値が全て同じ数なので、「絶対値が全て同じで、正負の個数が同じか1つ違いだったらYes」とすればよい。
解答例
注意点
公比-1の判定に公比1を巻き込まないように注意。
公比-1の判定の実装がまずいと、公比1の場合が巻き込まれてWAになる。
それを除外するか、別のif分岐で先に処理してしまうこと。
それを除外するか、別のif分岐で先に処理してしまうこと。