Atcoderアルゴリズム勉強会第1回（シミュレーション・全探索）

はじめに

こんにちは

現在京都に住んでいる修士2年の大学院生です．自己紹介だけの記事はかけないとのことで、ここで自己紹介について書こうと思ったものの、長くなりそうなのでやはり短めにいきたいと思います．

S台で浪人するも第1志望に落ち、関西圏公立大学に入学しましたが、仮面浪人して今の大学の学部に入りなおした多浪大学生です．

さて、今回はatcoderで高橋さんが行った講義、最強のアルゴリズム勉強会の第1回について取り組んでいきたいと思います．スライドにのっている問題を中心に解いていきます．

全探索なので難しい問題はないはずです（多分）

スライドはこちらになります．[https://www.slideshare.net/chokudai/wap-atcoder1]

全探索問題

天下一プログラマーコンテスト2012 予選B A問題　孫子算経

これは特にコメントないです．恐らく全探索の導入的な問題です．

スライドでは簡単にforループが列挙できる条件として、「分岐の回数が少なく、回数が決まっている」「ループごとに、選択肢が有限個で決まっている」とのことです．

a,b,c=map(int,input().split())

for i in range(1,128) :
    if i%3==a and i%5==b and i%7==c :
        print(i)

ARC001 A問題　センター採点

1,2,3,4の選択肢の個数を数えました．なんかこんな感じのコード昨日のABC200のC問題でも書いた気がする．

どんどん次の問題にいきましょう．

n=int(input())
c=list(input())
count=[0]*4

for i in c :
    count[int(i)-1]+=1

print(max(count),min(count))    

ARC004 A問題　2点間距離の最大値

特に意識したことはないですが、根号は最後に付けました．

この種類の問題は難しくなってくると誤差が生じてきて厄介ですよね

n=int(input())
x=[]
for i in range(n) :
    x.append(list(map(int,input().split())))

ans=0
for i in range(n-1) :
    for j in range(i+1,n) :
        distance=(x[j][0]-x[i][0])**2+(x[j][1]-x[i][1])**2
        ans=max(ans,distance)

print(ans**0.5)

ARC018 B問題　格子点と整数

for文３つ書いて愚直に計算しました．個人的にはfor文3個以上になるのは好きではないので他に良い解法があれば知りたいですね．

３つの組み合わせを出してくれるようなitertoolあったような気がするけど，リスト内の要素の組み合わせはどうするんだっけ．

n=int(input())
x=[]
for i in range(n) :
    x.append(list(map(int,input().split())))
count=0

for i in range(n-2) :
    for j in range(i+1,n-1) :
        for k in range(j+1,n) :
            ans=abs((x[j][0]-x[i][0])*(x[k][1]-x[i][1])-(x[k][0]-x[i][0])*(x[j][1]-x[i][1]))
            if ans%2==0 and ans!=0:
                count+=1
print(count)          

ABC004 D問題　マーブル

これはこの中では一番面倒な問題でした．

中央に位置する緑色の配置を決めてから、左に位置する赤色、そして右に位置する青色の配置を決めました．結論（最後の配置）から遡る問題でした．

各マーブルの移動関数については、マーブル全体が初期中央位置よりも左側にある場合、右側にある場合、そして初期中央位置が含まれている場合の3通り考えられますが、1つの関数にまとめることができました．

例）緑のマーブル7個が座標-8から-2に配置された場合の移動回数

(0-(-8))\times(0-(-8)+1)\div2-(-2-0)\times(-2-0+1)\div2=35\\

左辺については、
（マーブル8個の座標-8から-1までの移動総回数）ー（マーブル1個の座標-1までの移動総回数）
となっている．

これはマーブル全体が初期中央よりも左側に位置する場合の計算である．右側の時も同様に計算すれば求まる．

この式を一般化する．
（マーブル移動後の左端）＝l、（マーブル移動後の右端）＝r、（初期中央位置）＝cとおくと

(-1)^{c<l}(c-l)\times(c-l+1)\div2+(-1)^{r<c}(r-c)\times(r-c+1)\div2=ans\\

となる．

ここでc<lおよびr<cがでてくるが、これは各々の不等式を満たすと1となり、満たさない場合は-1となる．これによって、3通りの場合すべてを1つの関数で表すことができる．

これはこの問題で初知りでした、、、不等式満たさないと0になると思ってました

後は、for文で緑左端の位置を回していき、赤の右端、青の左端の位置を決めていくだけでした．

r,g,b=map(int,input().split())
ans=10**10

#----各マーブルの移動回数の関数----#
#----l=left,r=right,center=c,r<cが成り立てば1,不成立なら-1----#
def cost(l,r,c) :
    return (-1)**(r<c)*(r-c)*(r-c+1)//2+(-1)**(c<l)*(c-l)*(c-l+1)//2


#----緑色のマーブルの左端の位置から決めていく----#
for l in range(-500,201) :
    rR=min(l-1,-100+r//2)   #min(緑色マーブル左端からひとつ左，赤色マーブル右端)
    lB=max(l+g,100-b//2)    #max(緑色マーブル右端からひとつ右，青色マーブル左端)
    ans=min(ans,cost(rR-r+1,rR,-100)+cost(l,l+g-1,0)+cost(lB,lB+b-1,100))

print(ans)

最後に

最後の問題だけは結構難しかったです．関数を作るところが悩みました．

こんな感じでアルゴリズムについてスライド配布してくださるのでatcoderには感謝しかありません．

次は，第2回アルゴリズムのスライドを扱っていきたいと思います．なんの範囲かは忘れてしまいましたが、恐らくまた全探索だったような気がする．