はい。
https://atcoder.jp/contests/abc120
ooo- 918(-10) でした。
A - Favorite Sound
a,b,c=map(int,input().split())
print(min(b//a,c))
#include<bits/stdc++.h>
using namespace std;
#define sc3(a,b,c) scanf("%d %d %d",&a,&b,&c)
int main(){
int a,b,c;
sc3(a,b,c);
printf("%d\n",min(b/a,c));
return 0;
}
難しいです。。最初a//bして計算あわなくてあたふたしました。
B - K-th Common Divisor
a,b,k=map(int,input().split())
ans=[]
for i in range(1,101):
if (a%i==0 and b%i==0): ans.append(i)
print(ans[-k])
#include<bits/stdc++.h>
using namespace std;
#define sc3(a,b,c) scanf("%d %d %d",&a,&b,&c)
int main(){
int a,b,k,ans;
sc3(a,b,k);
ans=max(a,b);
for (int i=ans;ans>0;i--) {
ans=i;
if (a%i==0 && b%i==0) k--;
if(k==0) break;
}
printf("%d\n",ans);
return 0;
}
改行ミスで無駄にRE。これ1から100までやってからK番目探してますけど、100から1までやるようにすればK番目出た時点で解を確定できるかもしれない。
C - Unification
n=input()
ans=0
chk=""
for i in n:
if chk=="" or chk[-1]==i:
chk+=i
else:
chk=chk[:-1]
ans+=2
print(ans)
#include<bits/stdc++.h>
using namespace std;
int main(){
int n=0,m=0;
char s[100005];
scanf("%s",s);
for (long i=0;i<strlen(s);i++) {
n+=s[i]=='0';
m+=s[i]=='1';
}
printf("%d\n",min(n,m)*2);
return 0;
}
隣同士が違う部分を排除して+2を続けていくと解になるはず、と思ってました。0か1は必ず0か1と接しています、最後の1つでなければ。01の多いほうは少ないほうを全て消去します。最終形で01混在は必ずあり得ません。なのでシミュしなくても01の少ないほうの2倍が解になります。
D - Decayed Bridges
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;++i)
#define sc2(a,b) scanf("%d %d",&a,&b)
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)]; }
};
long long ans[100005];
int main(){
long long n,m;
scanf("%lld %lld",&n,&m);
vector <pair<int,int>> w(m);
UnionFind uf(n);
for (int i=0;i<m;i++) {
int a,b;
sc2(a,b);
w[i].first=a-1;
w[i].second=b-1;
}
ans[m-1]=n*(n-1)/2;
for(int i=m-1;i>0;i--) {
ans[i-1]=ans[i];
if (uf.find(w[i].first,w[i].second)==false) {
ans[i-1]-=(long long)uf.size(w[i].first)*uf.size(w[i].second);
uf.unite(w[i].first,w[i].second);
}
}
rep(i,m) printf("%lld\n",ans[i]);
return 0;
}
繋がっている頂点同士から辺を削除してという操作は多分現実的ではありません。なので最終では全てバラバラになっている状態から辺を1つずつ追加する流れで処理を考えます。頂点や辺の管理はUnionFindを使います。最終で全てバラバラの状態で移動できない不便さは頂点N個の総当たりなので N*(N-1)/2
になります。辺で繋いでいくと違うグループ同士が結合するときには不便さがそれぞれのグループの頂点数の積の分だけ解消されます。なので結合前の不便さから頂点数の積を引きます。