AtCoder Beginner Contest 177
はい。
AtCoder Beginner Contest 177
ooox-- 860(-16) D問題はコンテスト時間中は立ち回りミスでした。。。
A - Don't be late
PyPy3
d,t,s=map(int,input().split()) print("Yes" if d<=t*s else "No")
ぴったりは間に合う扱いになるはずでしょうし特に何も工夫せず。
B - Substring
PyPy3
s=input() t=input() x=len(t) ans=chk=x for i in range(len(s)-len(t)+1): chk=x for j in range(x): chk-=s[i+j]==t[j] ans=min(ans,chk) print(ans)
先頭から全部確認しました。ループが重くないか若干不安でしたが制約が優しく問題ありませんでした。
C - Sum of product of pairs
PyPy3
mod=1000000007 n=int(input()) a=[int(i) for i in input().split()] t=[0]*(n+1) for i in range(n): t[i]=t[i-1]+a[i] ans=chk=0 for i in range(n-1): x=-1*(i+1) ans+=a[x]*t[x-2] ans%=mod print(ans)
1x2 + 1x3 + 2x3を当初は全部その通りに計算してTLE。 1x(2+3) + 2x3 のような感じにしてなんとかAC。
D - Friends
#include<bits/stdc++.h> using namespace std; struct UnionFind { vector<int> data; UnionFind(int size) : data(size, -1) {} bool unite(int x, int y) { x=root(x), y=root(y); if (x!=y) { if (data[y]<data[x]) { swap(x, y); } data[x]+=data[y], data[y]=x; } return x!=y; } bool find(int x, int y) { return root(x)==root(y); } int root(int x) { return data[x]<0 ? x : data[x]=root(data[x]); } int size(int x) { return -data[root(x)]; } }; int main(){ int n,m,ans=1; scanf("%d %d",&n,&m); UnionFind uf(n); for (int i=0;i<m;i++) { int a,b; scanf("%d %d",&a,&b); uf.unite(a-1,b-1); } //printf("%d\n",); for(int i=0;i<n;i++) { ans=max(ans,uf.size(i)); } printf("%d\n",ans); return 0; }
友達情報をUnionFindで結合してグループ作成。グループで最も人数の多いものが解になるはずです。それぞれ別グループから一人ずつ出していくのが最小で作成する方法です、多分。
E問題以降はいつか。