はい。
Codeforces Round #686 (Div.3)
ooox-- 1189(-2) レーティング計算優しい。
A. Special Permutation
t=int(input())
for i in range(t):
n=int(input())
l=[0]*n
for i in range(n):
l[(i+1)%n]=i+1
print(*l)
1からnまで数列でindexと一致するものが1つもないようにする。危うく単に降順にしたものを使いそうになりました。
提出前に長さが奇数の場合に真ん中がに気づいて1つずらす方針でACに。
B. Unique Bid Auction
mod=1000000007
t=int(input())
for i in range(t):
n=int(input())
ans=chk=mod
l=[int(i) for i in input().split()]
w={}
ans=chk=mod
for j,k in enumerate(l):
if k not in w:
w[k]=j
else:
w[k]=-1
for j in w:
if w[j]>-1 and chk>j:
chk=j
ans=w[j]
print(ans+1 if chk!=mod else -1)
1つしかない数で最小値を探す。数列を全部調べます。
C. Sequence Transformation
mod=10**9+7
t=int(input())
for i in range(t):
n=int(input())
l=[int(i) for i in input().split()]
d=[]
f=0
for j in l:
if f==0 or j!=d[-1]:
d.append(j)
f=1
w={}
for j in d:
if j in w: w[j]+=1
else: w[j]=1
if len(d)==1:
print(0)
elif len(w)==n:
print(1)
elif d[0]==d[-1] and w[d[0]]==2:
print(1)
else:
ans=chk=mod
for j in w:
x=w[j]-1
if d[0]!=j: x+=1
if d[-1]!=j: x+=1
ans=min(ans,x)
print(ans)
数を消していって同じ数しか残らないようにする。
同じ数が続いている個所は意味がない気がしたので排除しました。排除後の出現位置を調べました。出現位置が端を含むかどうかで手数が変わるのをよしなに計算しました。
D. Number into Sequence
def prime_t(t):
i=2
while i**2<=t:
if t%i==0:
return 0
i+=1
return 1
def prime_list(tt):
p_list=[]
for i in range(2,tt+1):
if prime_t(i):
p_list.append(i)
return p_list
w=110000
l=prime_list(w)
t=int(input())
for i in range(t):
n=int(input())
p=n
d={}
x=[0,0]
for i in l:
while n%i==0:
if i in d: d[i]+=1
else: d[i]=1
n//=i
if d[i]>x[1]:
x[0]=i
x[1]=d[i]
if x[1]<2:
print(1)
print(p)
else:
ans=[]
for i in range(x[1]-1):
ans.append(x[0])
ans.append(p//(pow(ans[0],len(ans))))
print(len(ans))
print(*ans)
巣因数分解します。累乗の指数が最大のもの活用して解の数列を作ります。360は23と32と51です。 2 2 90 が解になります。
単純に割り切れる関係で数列を作るには指数が最大の23を2つ連続で並べて、残りは2とそれ以外全て数の積を数列の末尾に追加すると解になるはずです。多分
E. Number of Simple Paths
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;++i)
#define sc1(a) scanf("%d",&a)
#define sc2(a,b) scanf("%d %d",&a,&b)
int main(){
int t,n,x,y;
sc1(t);
rep(i,t) {
sc1(n);
vector<set<int>> g(n);
rep(j,n) {
sc2(x,y);
--x,--y;
g[x].insert(y);
g[y].insert(x);
}
vector<int> val(n,1);
queue<int> leafs;
rep(j,n) if (g[j].size()==1) leafs.push(j);
while (!leafs.empty()) {
int v=leafs.front();
leafs.pop();
int to=*g[v].begin();
val[to] += val[v];
val[v]=0;
g[v].clear();
g[to].erase(v);
if (g[to].size()==1) leafs.push(to);
}
long long ans=0ll;
rep(j,n) {
ans+=val[j]*1ll*(val[j]-1)/2;
ans+=val[j]*1ll*(n-val[j]);
}
printf("%lld\n",ans);
}
return 0;
}
上記のコード自体は解説記事の写経です。
頂点がN個で、辺もN本で辺がそれぞれ異なる頂点と接続されていれば必ず閉路があるグラフになるはずです。閉路のみなのか、閉路にいくつかの頂点が接続されているかはどちらもあり得ます。
問題文にあるNote、2番目のケースではwhileループ処理後のvalは {0,2,1,1} となっているはずです。多分。
閉路の外に接続されている頂点がある頂点には1より大きい値が入っているはずです。 val[to] += val[v]; がされているので。
この外れている部分は ans+=val[j]*1ll*(val[j]-1)/2; で計算します。val[j]の値の分だけ頂点があります。スタートの頂点はval[j]の分だけあります。ゴールはval[j]-1になります。なりますがこれですが数え方が二重になるので2で割ります。
これ以外の移動は val[j]*1ll*(n-val[j]) で計算します。これは2で割りません。2つの頂点の間で移動の仕方が2通りあります。閉路になっているので移動の仕方が2通りあります。なのでこの式で計算できます。
