コンテスト中AC:A
A - Dial Up
に1しかないのに
に1がある場合、-1です。0の場合も同様です。以下、そうでない時を考えます。
を円環とみなしたとき、
と異なる数のうち最も近い位置と、
との距離を
とします。
への追加操作は明らかに
回必要であるため、以下ではシフト操作のみを考えます。
の先頭から調べ、初めて
と異なる数が現れたとき、
回のシフト操作が必要です。
その後は、を1回シフトすれば異なる数にすることができ、これが最適なので、
の
と
が異なる毎にシフト操作が1回必要になります。
これで最小の操作回数を求めることができました。
B - Squares
解けなかったため、解説見ました。
条件の2つ目は、整数を用いて、
と表現でき、移項と因数分解で、
となります。
おくと、連立方程式の解を求めるのと同じように
の組みに対し、
の組みが一意に定まります。よって、
の組みを数える問題に帰着できます。
の条件から
の満たす条件を求めます。
が整数
が整数
が整数
が整数
の偶奇が等しい
また、より、正正、負負があり得ますが、
より、負負の組み合わせはあり得ません。よって、
は正整数です。
は正整数なので、
となり、
であるから、
が成り立ちます。
ここで、 なので、
が成り立ちます。これにより、
の全探索が可能なことがわかりました。
を定めれば、
の範囲は
であり、このうち
と偶奇が等しいものを数え上げれば良いです。条件を満たす
は
で計算できます。
提出コード:https://atcoder.jp/contests/arc125/submissions/25356430