AtCoder ABC125 解説

カイルダイアリー（テキトー）

AtCoder Beginer Constestの解説&反省です。
使用言語はpython。

#A - Biscuit Generator

特に難しくなくt+0.5以内の時間で何個作れますかという話。

![125 A.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/369642/ea24cb86-357b-7c42-e860-cbd92bf65c7c.png)


##ACコード

```python

a,b,t=map(int,input().split())
t+=0.5
print(int(t//a*b))

```

#B - Resale

一瞬やや複雑な問題に見えて全探索かとうろたえたが、ただ単にVi-Ciが正であるものを加算すればよい。numpyを使って簡単に書ける。
すべて不要なコーナーケースに備えてsum()やmax()の中身に[0]を仕込むことがせいぜいポイントか。

![125 B.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/369642/107918ad-64de-bc17-e512-3d999976f30e.png)

##ACコード

```python

from numpy import*
n=int(input())
*a,=map(int,input().split())
*b,=map(int,input().split())
c=array(a)-array(b)
print(sum([0]+list(c[c>0])))

```

#C - GCD on Blackboard
今回の最大の鬼門である。
まず、前提知識として配列[a,b,c]のgcdはgcd(gcd(a,b),c)であることを知っておいてほしい、頻出である。

下二つは正しい解法ではないので読みたくない人は飛ばすように。

#TLE&嘘解法
最初に考えたのはすべての数に対して約数列挙を行い、約数の集計をとって、ある約数の個数がn-1以上で最大のものを採用する方法。おそらくTLEになるだろうなと思っていて、投げたら案の定半分くらいTLEであった。
![125 C1.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/369642/8c24e87c-ff17-8939-c8f9-d9d06ecd4cf5.png)

##TLEコード

```python

from collections import*
def dv(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
 
    # divisors.sort()
    return Counter(divisors)
 
n,*a=map(int,open(0).read().split())
ans=Counter()
for i in range(n):
    ans+=dv(a[i])
l=[]
for k,v in ans.items():
    if v==n-1 or v==n:
        l.append(k)
print(max(l))

```
次に思いつく愚直解はある数を配列から消して変化後の配列全体でgcdをとる方法である。しかし、この方法ももちろんO(N^2)であり通らない。そこで思いついたのは、おそらく書き換えるべき数が入っているであろう1/4を欠落させてgcdをとれば最大の数が出てくるのでは？と考え次のコードで通した。（通ってしまった、これは嘘解法である。理由は後述する。）indexがずれると困るので、nが小さいときにTLEコードを使った。



![125 C2.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/369642/f735a1de-40bb-cf18-d0df-91f266d52978.png)


![125 C3.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/369642/3050254a-b164-2b68-1abf-3984caf25e67.png)


##嘘解法ACコード
```python

from collections import*
from functools import*
from fractions import*
def dv(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
 
    # divisors.sort()
    return Counter(divisors)

n,*a=map(int,open(0).read().split())
if n<1000:
    ans=Counter()
    for i in range(n):
        ans+=dv(a[i])
    l=[]
    for k,v in ans.items():
        if v==n-1 or v==n:
            l.append(k)
    print(max(l))
else:
    print(max(reduce(gcd,a[n//4:]),reduce(gcd,a[:n//4]+a[n//2:]),reduce(gcd,a[:n//2]+a[3*n//4:]),reduce(gcd,a[:3*n//4])))

```
なぜこれが嘘解法なのかというと、画像の通りである。
![125 C4.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/369642/39b38520-b296-87bc-2dae-e977b43de061.png)
言葉で言うならば、消す数の近くに最大公約数を決定する数があるとアウトである。~~まあ通せりゃいいんだ、通せば。へへ～んだ。~~

#きちんとした解法

まずはTLE解の派生のような解法である。前提知識がないならばこれが一番わかりやすいはずだ。

 x = 7 6 8
任意の二つの値を選んで約数を列挙する。
7,6を選び約数の和集合は{1,2,3,6,7}
これらの約数でxのすべての値を割りn-1個以上を割り切れた約数の中で最大の約数が解である。
これもnumpyを使って簡単に書ける。


##ACコード
```python

from numpy import*

def dv(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    return divisors

n,*a=map(int,open(0).read().split())
a=array(a)
l=[]
for i in set(dv(a[0])+dv(a[1])):
    if sum(a%i==0)>=n-1:
        l.append(i)
print(max(l))

```
#きちんとした解法２
解説によると想定解は累積gcdである。
本質的にはTLE解の方で書いた、配列から値を一つ消し、一つ消した全通りの配列のgcdをO(N)で出すということをやっている。
どこが累積なのかというと配列を右から見た途中のgcd配列と左から見た途中のgcd配列を保存しておき、間を一つ飛ばしで両者のgcdをとりそれの最大値が解ということである。

例えば配列[a,b,c,d]の累積gcdはgcd(0,gcd(b,c,d))、gcd(a,gcd(c,d))、gcd(gcd(a,b),d)、gcd(gcd(a,b,c),0)の最大値ということである。図も併せてぜひ理解してほしい。
（図の非自明なカッコつきの0は配列始まりの端に相方がいないからである、ちなみにpythonのfractionsのgcd(0,3)の出力は3である。）

![125 C5.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/369642/b6e2d500-0e11-869e-9fcc-80fb1b1718e2.png)

同色で囲んだ組をgcdして最大値を求める。

![125 C5-2.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/369642/a768da4b-5225-5a45-826c-21fd54f45d73.png)





##ACコード(想定解)
```python

from fractions import*
n,*a=map(int,open(0).read().split())
p=gcd(a[0],a[1])
l=[a[0],p]
c=list(reversed(a))
q=gcd(c[0],c[1])
r=[q]
for i in range(1,n-1):
    p=gcd(p,a[i+1])
    l.append(p)
    q=gcd(q,c[i+1])
    r.append(q)

r=r[::-1]+[a[-1]]
r=r[1:]+[0]
l=[0]+l

print(max(gcd(s,t)for s,t in zip(r,l)))
```
##accumulateに第二引数があることに気づいた(5/3)追記
```python

from itertools import*
from fractions import*
n,*a=map(int,open(0).read().split())
b=list(accumulate([0]+a,gcd))
c=list(accumulate([0]+a[::-1],gcd))
print(max(gcd(s,t)for s,t in zip(b,c[::-1][1:])))

```
#D - Flipping Signs

おそらくCよりも簡単だったのではないだろうか。
本質を言うと最初に配列にある-の数で答えが決まってしまう。
発想としてはABC120 C - Unificationに近いので是非参照されたし。

もし-の個数が奇数ならば、一つだけ-を+にするのが不可能なので配列のすべての値の絶対値の総和-最小値*2
偶数ならば、絶対値の総和が解である。
またまたこれもnumpyを使うと簡単に書ける。
##ACコード
```python

from numpy import*
n,*a=map(int,open(0).read().split())
a=array(a)
if len(a[a<0])%2==0:
    print(sum(abs(a)))
else:
    a=sorted(abs(a))
    print(sum(a[1:])-a[0])

```

これにて終了、初全完でおそらく人生最後の全完回となるだろう。（ならないように頑張るけど）