A問題 Christmas Presen
条件分岐
a,b=map(int,input().split()) if a>b: print("Bat") else: print("Glove")
B問題 Christmas Trees
ｌとｒが負の整数か、それとも正の整数かで３つに場合分けして、いい感じに割り算をします。
条件分岐の内容としては、ｌとｒがどちらも負の整数の場合、片方が負の整数でもう片方が正の整数の場合、２つとも正の整数の場合の３つに場合分けします。
a,m,l,r=map(int,input().split()) l-=a r-=a if l<=0 and 0<=r: hako=1 else: hako=0 if l>=0 and r>=0: print(r//m-(l-1)//m+hako) elif l<0 and r>=0: print(r//m+abs(l)//m+hako) else: print(abs(l)//m-(abs(r)-1)//m+hako)
C問題 Socks 2
まず、この問題は、持っている靴下の合計が偶数か奇数かで場合分けします。
もし偶数の場合は全ての靴下を使うことになり、愚直に靴下の色をソートして、前から２つずつをペアにしていけばよいです。
もし奇数の場合は少し面倒なことになります。基本的には偶数のときと同じように、ソートして前から２つずつをペアにしていく…ということをすればいいのですが、奇数の場合は一枚あまることになります。その余る一枚を決めるのが少々めんどくさいところです。
ぼくは、前と後ろから累積和をとり、いい感じにやりました。こうすることで、その靴下を使わないなら奇妙さの総和はいくつになるか…が一回の計算で求まります。
全ての靴下に対してこの計算をすれば答えが出ます。
n,k=map(int,input().split()) a=set(list(map(int,input().split()))) hako=(2*n-k)//2 rotti=[] for i in range(n): if i+1 in a: rotti.append(i+1) else: hako-=1 if len(rotti)%2==0: ans=0 for i in range(len(rotti)//2): ans+=abs(rotti[i*2]-rotti[i*2+1]) print(ans) exit() a=[0] b=[0] for i in range(len(rotti)//2): a.append(a[i]+abs(rotti[i*2]-rotti[i*2+1])) for i in range(len(rotti)//2): b.append(b[i]+abs(rotti[len(rotti)-1-i*2]-rotti[len(rotti)-1-i*2-1])) ans=1000000000 for i in range(len(a)): ans=min(a[i]+b[len(b)-1-i],ans) print(ans)
D問題 Reindeer and Sleigh
与えられた配列Rを累積和にします。
そして、クエリが与えられるたびに二分探索で何匹目まで運べるかを求めます。
import bisect n,q=map(int,input().split()) amount=sorted(list(map(int,input().split()))) rotti=[0] for i in range(len(amount)): rotti.append(rotti[i]+amount[i]) for i in range(q): a=int(input()) hako=bisect.bisect(rotti,a) if hako==len(rotti): print(len(rotti)-1) elif rotti[hako]==a: print(hako) else: print(hako-1)
E問題 Christmas Color Grid 1
制約をみる限り、全てのマスに対して”＃”をおいたときにグリッドの緑の連結成分数がいくつになるかを求めても実行時間は大丈夫そうなので全探索します。
h,w=map(int,input().split()) rotti=[[]*1 for i in range(h)] for i in range(h): rotti[i]=list(input()) rotti2=[[-1]*w for i in range(h)] done=[[0]*w for i in range(h)] count=0 for i in range(h): for ipp in range(w): if done[i][ipp]==1 or rotti[i][ipp]==".": continue done[i][ipp]=1 stack=[[i,ipp]] iti=0 count+=1 while len(stack)>iti: a=stack[iti][0] b=stack[iti][1] rotti2[a][b]=count #ue if a-1>=0 and done[a-1][b]==0 and rotti[a-1][b]=="#": stack.append([a-1,b]) done[a-1][b]=1 #migi if b+1<w and done[a][b+1]==0 and rotti[a][b+1]=="#": stack.append([a,b+1]) done[a][b+1]=1 #sita if a+1<h and done[a+1][b]==0 and rotti[a+1][b]=="#": stack.append([a+1,b]) done[a+1][b]=1 #hidari if b-1>=0 and rotti[a][b-1]=="#" and done[a][b-1]==0: stack.append([a,b-1]) done[a][b-1]=1 iti+=1 q=0 p=0 for i in range(h): for ipp in range(w): if rotti[i][ipp]=="#": continue q+=1 hako=[] #ue if i-1>=0 and rotti[i-1][ipp]=="#": hako.append(rotti2[i-1][ipp]) #migi if ipp+1<w and rotti[i][ipp+1]=="#": hako.append(rotti2[i][ipp+1]) #sita if i+1<h and rotti[i+1][ipp]=="#": hako.append(rotti2[i+1][ipp]) #hidari if ipp-1>=0 and rotti[i][ipp-1]=="#": hako.append(rotti2[i][ipp-1]) hako=set(hako) if len(hako)==1: p+=count elif len(hako)==0: p+=count+1 elif len(hako)==2: p+=count-1 elif len(hako)==3: p+=count-2 elif len(hako)==4: p+=count-3 def kouyaku(a,b): while a>0 and b>0: if a<b: b=b%a elif a==b: return a else: a=a%b return max(a,b) def koubai(a,b): return a*b//kouyaku(a,b) count=kouyaku(p,q) p=p//count q=q//count for i in range(1000000): p+=998244353 if p%q==0: print((p//q)%998244353) break
