geam1113’s diary

主にAtcoderのコンテストの備忘録を書きます。AtCoder緑と水色を行ったり来たりしています。

ARC125 参加記録

ARC 式変形

コンテスト中AC:A

A - Dial Up

$a$ に1しかないのに $T$ に1がある場合、-1です。0の場合も同様です。以下、そうでない時を考えます。

$a$ を円環とみなしたとき、 $a_1$ と異なる数のうち最も近い位置と、 $a_1$ との距離を $d$ とします。

$b$ への追加操作は明らかに $M$ 回必要であるため、以下ではシフト操作のみを考えます。

$T$ の先頭から調べ、初めて $a_1$ と異なる数が現れたとき、 $d$ 回のシフト操作が必要です。

その後は、 $a$ を1回シフトすれば異なる数にすることができ、これが最適なので、 $T$ の $T_i$ と $T_{i+1}$ が異なる毎にシフト操作が1回必要になります。

これで最小の操作回数を求めることができました。

B - Squares

解けなかったため、解説見ました。

条件の２つ目は、整数 $z$ を用いて、 $x^2-y=z^2$ と表現でき、移項と因数分解で、 $(x+z)(x-z)=y$ となります。

$x-z=p,\ q=x-z$ おくと、連立方程式の解を求めるのと同じように $p,q$ の組みに対し、 $x,z$ の組みが一意に定まります。よって、 $p,q$ の組みを数える問題に帰着できます。

$x,y$ の条件から $p,q$ の満たす条件を求めます。

$y=pq \Longleftrightarrow 1≦pq≦N$

$x,y,z$ が整数 $\Longleftrightarrow p,q$ が整数

$x=\frac{p+q}{2} \Longleftrightarrow 1≦\frac{p+q}{2}≦N,\$ $\frac{p+q}{2}$ が整数

$\frac{p+q}{2}$ が整数 $\Longleftrightarrow$ $p,q$ の偶奇が等しい

また、 $1≦pq≦N$ より、正正、負負があり得ますが、 $1≦\frac{p+q}{2}≦N$ より、負負の組み合わせはあり得ません。よって、 $p,q$ は正整数です。

$p,q$ は正整数なので、 $x＞z$ となり、 $x+z≧x-z$ であるから、 $p≧q$ が成り立ちます。

ここで、 $1≦pq≦N,\ p≧q$ なので、 $1≦q≦\sqrt{N}$ が成り立ちます。これにより、 $q$ の全探索が可能なことがわかりました。

$q$ を定めれば、 $p$ の範囲は $q≦p≦\lfloor{N/q} \rfloor$ であり、このうち $q$ と偶奇が等しいものを数え上げれば良いです。条件を満たす $p$ は $O(1)$ で計算できます。

提出コード：https://atcoder.jp/contests/arc125/submissions/25356430