2022 TCO Algo Round 2A MedがHackされてEasy一完。
— titia (@titia_til) May 21, 2022
Medは1→2000000 みたいな奴が直接作れないことに気付けなかった。
これでもRound3には進めるようなので、まあ。
TopCoder SRMのレートは1636→1621
2022 TCO Algo Round 1A 全完13位。システムテスト通ってほっとした。
— titia (@titia_til) April 16, 2022
Easy 後ろのindexから順に見て、〇に大きい数字を、その後×に小さい数字を割り当て。
Mid Aの目が出る確率をPA、Bが出る確率をPBとすると、PA+PB*PAとPB*PBを比較する。PAとPBはDPで求める。
Hard ×のindexの積。Midより簡単では？
mod=1000000007
class TreeTokens ():
def placeMax(self, N, G, L, seed):
state = seed
E=[[] for i in range(N)]
for i in range(1,N):
state = (state * 1103515245 + 12345) % (1<<31)
tmp = (state // 1000) % L
p = max(0, i-1-tmp)
E[i].append(p)
E[p].append(i)
#print(E)
ROOT=G
QUE=[ROOT]
Parent=[-1]*(N+1)
Parent[ROOT]=N # ROOTの親を定めておく.
TOP_SORT=[] # トポロジカルソート
while QUE: # トポロジカルソートと同時に親を見つける
x=QUE.pop()
TOP_SORT.append(x)
for to in E[x]:
if Parent[to]==-1:
Parent[to]=x
QUE.append(to)
CC=[-1]*N
for x in TOP_SORT[::-1][:-1]:
if CC[x]==-1:
CC[x]=1
if Parent[x]==ROOT:
continue
CC[Parent[x]]=max(CC[Parent[x]],CC[x]+1)
AC=[0]*N
AC[ROOT]=0
ANS=0
QUE=[ROOT]
while QUE:
x=QUE.pop()
MAX=-1
if len(E[x])==1 and x!=ROOT:
ANS+=AC[x]
ANS%=mod
for to in E[x]:
if to==Parent[x]:
continue
MAX=max(CC[to],MAX)
USE=0
for to in E[x]:
if to==Parent[x]:
continue
if CC[to]==MAX and USE==0:
USE=1
AC[to]=(AC[x]*2+1)%mod
else:
AC[to]=1
QUE.append(to)
return ANS%modmod=10**9+7
DP=[[0],[0],[0,1],[0,2],[0,6,3]]
for i in range(5,1501):
X=[0]*(i//2+1)
for j in range(1,i//2+1):
if i%2==0 and j==i//2:
X[j]=(DP[-2][j-1]*(i-1))%mod
else:
X[j]=(DP[-1][j]*(i-1)+DP[-2][j-1]*(i-1))%mod
DP.append(X)
class ExpectedValue():
def solve(self, N):
S=sum(DP[N])
ANS=0
for i in range(len(DP[N])):
ANS=ANS+i*DP[N][i]
ANS%=mod
return (S*N-ANS)*pow(S,mod-2,mod)%mod
#include <bits/stdc++.h>
#include <bits/stdc++.h>
using namespace std;
class FlightPlan
{
public:
long long fly(int R, int C, vector<int> H, int cup, int cdn, int clr)
{
set<long long> S;
S.clear();
vector<long long> DP(R * C);
for (int i = 0; i < R * C; i += 1)
{
DP[i] = 9999;
S.insert(H[i]);
}
DP[0] = 0;
long long ANS = 1000000000000000000;
for (auto s : S)
{
if (s < H[0])
{
continue;
}
if (s < H[R * C - 1])
{
continue;
}
deque<int> Q;
Q.push_back(0);
for (int i = 0; i < R * C; i += 1)
{
DP[i] = 9999;
}
DP[0] = 0;
while (Q.size())
{
int x = Q.front();
Q.pop_front();
int r = x / C;
int c = x % C;
if (r + 1 < R && H[(r + 1) * C + c] <= s && DP[(r + 1) * C + c] > DP[r * C + c] + 1)
{
DP[(r + 1) * C + c] = DP[r * C + c] + 1;
Q.push_back((r + 1) * C + c);
}
if (r - 1 >= 0 && H[(r - 1) * C + c] <= s && DP[(r - 1) * C + c] > DP[r * C + c] + 1)
{
DP[(r - 1) * C + c] = DP[r * C + c] + 1;
Q.push_back((r - 1) * C + c);
}
if (c + 1 < C && H[r * C + c + 1] <= s && DP[r * C + c + 1] > DP[r * C + c] + 1)
{
DP[r * C + c + 1] = DP[r * C + c] + 1;
Q.push_back(r * C + c + 1);
}
if (c - 1 >= 0 && H[r * C + c - 1] <= s && DP[r * C + c - 1] > DP[r * C + c] + 1)
{
DP[r * C + c - 1] = DP[r * C + c] + 1;
Q.push_back(r * C + c - 1);
}
if (DP[(R - 1) * C + C - 1] < 9999)
{
long long ANSX = 0;
ANSX += (s - H[0]) * cup;
ANSX += (s - H[(R - 1) * C + C - 1]) * cdn;
ANSX += DP[(R - 1) * C + C - 1] * clr;
if (ANS > ANSX)
{
ANS = ANSX;
}
}
}
}
return ANS;
}
};
class EpicPartition():
def createPartition(self, N):
if N%4!=0:
return ""
k=N*6
ALL=k*(k+1)//2
CK=(ALL//2)//(k//3)
ANS=["a"]*k
ANS[-1]="c"
for i in range(CK-k//6,CK+k//6-1):
ANS[i]="c"
f=0
for i in range(k):
if f< k//3 and ANS[i]!="c":
if f%2==0:
ANS[i]="a"
else:
ANS[i]="b"
f+=1
elif ANS[i]!="c":
if f%2==1:
ANS[i]="a"
else:
ANS[i]="b"
f+=1
return "".join(ANS)
class CardDrawPoints():
def expectedScore(self, count):
LEN=len(count)
if max(count)==0 or len(count)==1:
return 0
LIST=[-1]*(1<<LEN)
def calc(A):
if LIST[A]!=-1:
return LIST[A]
rest=[0]*LEN
NOW=0
for i in range(LEN):
rest[i]=count[i]
if A & (1<<i)!=0 and count[i]>0:
NOW+=i
rest[i]-=1
SUM=sum(rest)
if SUM==0:
return NOW
ANS=float(0)
for i in range(LEN):
if A & (1<<i)!=0:
continue
else:
ANS+=float(calc(A|(1<<i)))*rest[i]/SUM
if NOW>ANS:
LIST[A]=NOW
return NOW
else:
LIST[A]=ANS
return ANS
for i in range((1<<LEN)-1,-1,-1):
calc(i)
return LIST[0]
import bisect
class ArraySorting():
def arraySort(self, A):
N=len(A)
DP=[1<<31]*N
fr=[-1]*N # 復元用のリスト
for i in range(N):
a=A[i]
pos=bisect.bisect_right(DP,a)
DP[pos]=a
if DP[pos-1]==1<<31:
fr[i]=1
else:
fr[i]=DP[pos-1]
ANS=0 # LISの長さ
for i in range(N):
if DP[i]!=1<<31:
ANS=i
LASTV=DP[i]
NEXT=LASTV
B=[]
for i in range(N-1,-1,-1):
a=A[i]
if a==NEXT:
B.append(a)
NEXT=fr[i]
else:
B.append(NEXT)
return B[::-1]
class EncloseArea():
def enclose(self, A):
if A%2!=0:
return tuple()
if A>2402:
return tuple()
ANS=[["."]*50 for i in range(50)]
ANS[0][0]="/"
ANS[0][1]="\\"
ANS[1][0]="\\"
ANS[1][1]="/"
S=2
for i in range(1,49):
if S==A:
break
ANS[i][i]="."
ANS[i+1][i+1]="/"
ANS[i][i+1]=ANS[i+1][i]="\\"
S+=2
if S==A:
A=[]
for ans in ANS:
A.append("".join(ans))
return tuple(A)
NOWP=[0,1]
NOWM=[1,0]
def rewrite1(x,y):
if ANS[x-1][y]==".":
ANS[x-1][y]="/"
else:
ANS[x-1][y]="."
ANS[x][y]="."
ANS[x-1][y+1]="\\"
ANS[x][y+1]="/"
def rewrite2(x,y):
if ANS[x][y-1]==".":
ANS[x][y-1]="/"
else:
ANS[x][y-1]="."
ANS[x][y]="."
ANS[x+1][y-1]="\\"
ANS[x+1][y]="/"
while True:
x,y=NOWP
if 0<=x-1<50 and 0<=y+1<50:
rewrite1(x,y)
S+=2
NOWP[0]+=1
NOWP[1]+=1
if NOWP[0]==49 or NOWP[1]==49:
MIN=min(NOWP)
NOWP[0]-=MIN
NOWP[1]-=MIN
NOWP[1]+=2
if S==A:
break
x,y=NOWM
if 0<=x+1<50 and 0<=y-1<50:
rewrite2(x,y)
S+=2
NOWM[0]+=1
NOWM[1]+=1
if NOWM[0]==49 or NOWM[1]==49:
MIN=min(NOWM)
NOWM[0]-=MIN
NOWM[1]-=MIN
NOWM[0]+=2
if S==A:
break
if S==A:
A=[]
for ans in ANS:
A.append("".join(ans))
return tuple(A)
class StringRings():
def expectedRings(self, A, B):
ANS=0
for i in range(A):
ANS+=1.0/(2*i+1)
for i in range(B):
ANS+=1.0/(A*2+i+1)
return ANS
#include <bits/stdc++.h>
using namespace std;
class IterateOverACube {
public:
vector <int> findCell(int N, long long index){
index+=1;
vector <int> L;
for (int i=1;i=0;i-=1){
L.push_back(i);
}
for (int i=0;i<=N;i+=1){
L.push_back(0);
}
int LEN=L.size();
int i=0;
int j=0;
vector<long long> S;
S.push_back(1);
long long SUM=1;
while (i=index){
SUM=i;
rest=index-(NOW-S[i]);
break;
}
}
NOW=0;
int x=0;
for (int i=0;i=rest){
rest=rest-(NOW-L[SUM-i]);
x=i;
break;
}
}
int SYZ=SUM+1-x;
int z=min(SYZ,N)-rest;
int y=SUM-x-z;
return {x,y,z};
}
};
class LandSplitter():
def cheapest(self, N, A, B):
if A==B:
if N%A!=0:
return -1
else:
x=N//A
return A*A* (1+(x-1))*(x-1)//2
def check(x,A,B): # 残りxのとき, A～Bを使って分割可能か調べる
t=x//A
s=B-A
if x<=t*(A+s):
return 1
else:
return 0
for useb in xrange(N//B,-1,-1): #Bを使う回数を大きい方から探索して,
if check(N-useb*B,A,B)==1: #分割可能なときにBを使う回数とする.
break
else:
return -1 # 分割可能なことがなければ、不可能
M=N-useb*B # Bを使った残り
ANS=M*(useb*B)+B*B*((1+(useb-1))*(useb-1)//2) # ここまでのコスト
usea=max(0,-(-(M-B)//A)) # Aの使用回数
if usea==0: # Aを使わなくて良いときは既に分割できている
return ANS
S=M-usea*A # Aを使った残り
ANS+=S*(usea*A)+A*A*((1+(usea-1))*(usea-1)//2) # 残りのコスト
return ANS