Codeforces Round #698 (Div. 2) 1478C - Nezzar and Symmetric Array
問題
を、個の相異なる整数からなり、任意のに対してとなる要素が存在する配列とする。
配列から生成した配列が与えられる。
ここで、である。
元の配列は存在するだろうか。
解法
Editorial of Codeforces Round #698 (Div.1, Div.2) - Codeforces
Editorialを軸に説明を進める。
前提
つまり、に相異なる個の整数が2つずつ含まれていない場合、答えはNO。
この事実から、一般性を失わず、
かつ、任意のに対して
かつ、任意のに対して
と仮定する。
式変形
前提より、において、
差分をとると、
つまり、がで割り切れない場合、答えはNO。
確認
ならば、より、において。
また、においてからが求まるので、
つまり、が0以下であるかの倍数ではない場合、答えはNO。
コード(Rust)
Submission #109130082 - Codeforces
感想
Editorialを読んでも理解できなかったため、記事を書いてみた。
少しは苦手意識を克服できた気がする。