【30分40分】実装してみる・問題を解いてみる
コードを書いてみる→行き詰まる→先人のコードを見て感動する→理解したつもりになる→コードを書いてみる→・・・を繰り返した
class SegTree: #根のインデックスは1
def __init__(self,init_list,segfunc,default): #defaultは初期値
#葉の長さ
n=len(init_list)
#葉の最左のインデックス
self.num=1<<(n-1).bit_length()
self.segfunc=segfunc
self.default=default
#セグ木は全体を配列として管理
#ノードの数は(2*葉の長さ)に収まる
self.tree=[default]*2*self.num
#葉に値を挿入
for i in range(n):
self.tree[self.num+i]=init_list[i]
#葉以外を関数に従って更新
for i in range(self.num-1,0,-1):
self.tree[i]=self.segfunc(self.tree[2*i],self.tree[2*i+1])
#対象のリストは0-indexed, segtreeは1-indexedであることに注意
#対象のリストのk番目をxに更新
def update(self,k,x):
#kがtree上のインデックスを表すように葉の最左のインデックスを加算
k+=self.num
#まずは該当の場所に値を挿入
self.tree[k]=x
#根に行き着くまで親も更新
#k>>1で親のインデックスを表せる 頭いい
#e.g.)110(6)>>1 : 011(3) 111(7)>>1 : 011(3)
#k^1で兄弟を表せる 頭いい
while k>1:
self.tree[k>>1]=self.segfunc(self.tree[k],self.tree[k^1])
k>>=1
#[l,r)区間で対象の値を返す
#lを含み,rを含まない
def query(self,l,r):
res=self.default
#l,rがtree上のインデックスを表すように葉の最左のインデックスを加算
l+=self.num
r+=self.num
while l<r:
#lが弟だった場合,兄は参照してはならないので
#弟のみ参照して,lに1を加算.兄を参照してはならない=親を参照してはならない
if(l&1):
res=self.segfunc(res,self.tree[l])
l+=1
#rが弟だった場合,兄のみ参照しなくてはならない(rは開区間なため)
if(r&1):
res=self.segfunc(res,self.tree[r-1])
#親に上がる
l>>=1
r>>=1
return res
from math import gcd
n=int(input())
a=list(map(int,input().split()))
seg=SegTree(a,gcd,0)
ans=0
for i in range(n):
ans=max(ans,gcd(seg.query(0,i),seg.query(i+1,n)))
print(ans)
総括
忘れた頃にもう一回解けることが大事だって、chokudaiさんが言ってた。数週間後にまた帰ってくる。
1時間で終わらなくてごめんなさい。
