Educational Codeforces Round Round 86(Rated for Div.2)のA～Eまでの解説です。
今回も無事にA～Dまでの4完を達成しレートを伸ばすことができました＊(ただ、レート1899と紫にあと1足りなかったのでかなり悔しかったです)。
問題のアドレスは以下になります↓
https://codeforces.com/contest/1342
公式の解説(Editorial)は以下になります↓
https://codeforces.com/blog/entry/76633

A問題:

操作1のみを用いてxとyの両方を0にする場合と、操作2をxとyのどちらか一方が0になるまで行い、その後残った数を0にする場合を考えれば十分です。
これらはそれぞれO(1)で求められるので、この問題を解くことができました。

サンプルコード(Python):
https://codeforces.com/contest/1342/submission/78131188

t=int(input())
for _ in range(t):
   x,y=map(int,input().split())
   a,b=map(int,input().split())
   ans1=(x+y)*a #操作1のみを用いる場合
   ans2=min(x,y)*b+(max(x,y)-min(x,y))*a #操作2を用いてから操作1を用いる場合
   print(min(ans1,ans2))

B問題:

文字の種類が2以下であることから、適切に文字を挿入することでkを2以下にすることができます。
また、kが1となるためには元の文字列のすべての文字が等しい必要があります。
したがって、元の文字列のすべての文字が等しいとき、元の文字列をそのまま出力すればよいです。
また、元の文字列に0と1の両方が存在するとき、k=2となる単純な構成法が存在します。
元の文字列の1文字目が1のとき、'10'を|t|回繰り返した文字列が、元の文字列の1文字目が0のとき、'01'を|t|回繰り返した文字列が、それぞれ条件を満たします。
以上によりこの問題を解くことができました。

サンプルコード(Python):
https://codeforces.com/contest/1342/submission/78140426

t=int(input())
for _ in range(t):
   s=input()
   l=len(s)
   if len(set(s))==1:
       print(s)
   else:
       if s[0]=='0':
           print('01'*l)
       else:
           print('10'*l)

C問題:

(x mod a) mod b != (x mod b) mod aとなる個数を数えるのは難しそうなので、代わりに(x mod a) mod b = (x mod b) mod aとなる個数を数えることを考えます。
明らかに、1<=x<max(a,b)のとき、(x mod a) mod b = (x mod b) mod aを満たします。
またmax(a,b)<=xのとき、上記の式を満たすのはxがk*lcm(a,b)<=x<k*lcm(a,b)+max(a,b)を満たす場合に限ります。
したがって、k*lcm(a,b)<=x<k*lcm(a,b)+max(a,b)を満たすxのうち、区間[l,r]に含まれるものの個数を求めることで、この問題を解くことができます。
[k*lcm(a,b),k*lcm(a,b)+max(a,b)-1]の全部が区間[l,r]に含まれるようなkの個数はr//lcm-l//lcmで求めることができ、[k*lcm(a,b),k*lcm(a,b)+max(a,b)-1]がlを含むとき、区間に含まれる部分を(l//lcm(a,b))*lcm(a,b)+max(a,b)-1-l+1により、rを含むとき区間からはみ出る部分を(r//lcm(a,b))*lcm(a,b)+max(a,b)-1-rによりそれぞれ求めることができるので、この問題を解くことができました。

サンプルコード(Python):
https://codeforces.com/contest/1342/submission/78165136

def gcd(a,b):
   if b==0:
       return a
   else:
       return gcd(b,a%b)

t=int(input())
for _ in range(t):
   a,b,q=map(int,input().split())
   d=max(a,b)
   lcm=(a*b)//gcd(a,b)
   ans=[]
   for _ in range(q):
       l,r=map(int,input().split())
       tmp=max(min(d-1,r)-l+1,0)
       tmp+=(r//lcm-l//lcm)*d
       if l//lcm!=0 and (l//lcm)*lcm+d-1>=l:
           tmp+=(l//lcm)*lcm+d-1-l+1
       if r//lcm!=0 and (r//lcm)*lcm+d-1>=r:
           tmp-=(r//lcm)*lcm+d-1-r
       ans.append(r-l+1-tmp)
   print(*ans)

D問題:

Ciは単調減少な数列なので、要素を降順にソートし、上から追加していくことを考えます。
優先度付きキューによりすでに要素が追加された列のうち長さが最小のものを管理し、すでに要素が追加された列の個数cntを別途持っておくとにします。
すると、ある時点で見ている要素iについて、長さが最小の列の長さ<Ciを満たすとき、その要素をその列に追加することができ、そうでないとき、cnt+1番目の列にその要素を追加することになります。
これをすべての要素について行えばよく、この計算量はO(NlogN)となるのでこの問題を解くことができました。

サンプルコード(Python):
https://codeforces.com/contest/1342/submission/78190553

import heapq

n,k=map(int,input().split())
arr=list(map(int,input().split()))
arr=sorted(arr,reverse=True)
arr2=[0]+list(map(int,input().split()))
ans=[[] for _ in range(n)]
q=[]
heapq.heappush(q,(0,0))
right=1
for i in range(n):
   cnt,pos=heapq.heappop(q)
   if cnt+1<=arr2[arr[i]]:
       ans[pos].append(arr[i])
       heapq.heappush(q,(cnt+1,pos))
   else:
       ans[right].append(arr[i])
       heapq.heappush(q,(cnt,pos))
       heapq.heappush(q,(1,right))
       right+=1
cnt=0
for i in range(n):
   if len(ans[i])==0:
       break
   else:
       cnt+=1
       ans[i]=[len(ans[i])]+ans[i]
print(cnt)
for i in range(cnt):
   print(*ans[i])

E問題:

すべてのルークの移動範囲がすべてのマスを覆う必要があることから、すべてのルークは行または列についてそれぞれ1つ置かれている必要があります。
このことから、k>=nの場合条件を満たすルークの置き方は存在しません。
また、k=0のときは明らかに答えはn!となります。
1<=k<nのとき、行または列について、複数のルークが置かれた行または列が存在します。
これは対称なので、行または列について場合の数を求め、それを2倍することで答えを得られます。
したがって、以下では行について複数のルークが置かれた行が存在するときの場合の数の求め方を述べます。
1<=k<nのとき、ルークを(n-k)行のどこかに置くことで、必ず互いに攻撃しあうルークの個数をkにすることができます。
このような取り方は、(n-k)行から(n-k)行を選ぶのに(n-k)C(n-k)通り、ルークを(n-k)行のどこかに置くのに(n-k)^n通りあることから、(n-k)C(n-k)*(n-k)^n通りとなります。
ただし、(n-k)^n通りには、ルークを(n-k-1)行のどこかに置く場合の数、(n-k-2)行のどこかに置く場合の数、…、ルークを0行のどこかに置く場合の数がそれぞれ含まれています。
したがって、まずルークを(n-k-1)行のどこかに置く場合の数を取り除くことを考えます。
このような取り方は、(n-k)行から(n-k-1)行を選ぶのに(n-k)C(n-k-1)通り、ルークを(n-k-1)行のどこかに置くのに(n-k-1)^n通りあることから、(n-k)C(n-k-1)*(n-k-1)^n通りとなります。
これを取り除くと、今度は逆に(n-k-2)行のどこかに置く場合の数が足りなくなります。
したがって、同様の計算により(n-k)C(n-k-2)*(n-k-2)^n通りを足し合わせます。
すると、今度はまた(n-k-3)行のどこかに置く場合の数が超過します。
これをルークを0行のどこかに置く場合の数に到達するまで繰り返します。
この計算は1からnまでの階乗とその逆数を前計算しておき、n乗の部分の計算に繰り返し2乗法を用いることでO(NlogN)で行うことができます。
最後に、ルークを置く(n-k)行の取り方はnC(n-k)であることと、行と列について状態が対称であることから、上記で得られた値にnC(n-k)と2を掛けることで、求める答えを得ることができます。

サンプルコード(Python):
https://codeforces.com/contest/1342/submission/78268081

mod=998244353
n,k=map(int,input().split())
fact=[1] #1からNまでの階乗を前計算する
for i in range(1,n+1):
 fact.append((fact[-1]*i)%mod)
revfact=[1] #1からNまでの階乗の逆数を前計算する
for i in range(1,n+1):
 revfact.append(pow(fact[i],mod-2,mod))
if k>=n: #K>=Nとなるような条件を満たすルークの置き方は存在しない
 print(0)
elif k==0: #K=0のときはN!が答えとなる
 print(fact[n])
else:
 ans=0
 for i in range(n-k+1): #(n-k)行にルークを配置する場合の数を包除原理により求める
   if i%2==0:
     ans+=pow(n-k-i,n,mod)*fact[n-k]*revfact[i]*revfact[n-k-i]
     ans%=mod
   else:
     ans-=pow(n-k-i,n,mod)*fact[n-k]*revfact[i]*revfact[n-k-i]
     ans%=mod
 print((ans*fact[n]*revfact[k]*revfact[n-k]*2)%mod) #答えは(上記の場合の数)*(n行から(n-k)行を選ぶ場合の数)*2に等しい