AtCoder Beginner Contest 165(ABC165) A～F解説

2020年5月3日 00:48

AtCoder Beginner Contest 165(ABC165)のA～Fまでの解説です。
コンテスト中はA～Eの5完(80:22+7WA)、その後Fも解きました(Eの場合分けで手間取りましたが、ぎりぎり青パフォに乗せることができました)。
問題のアドレスは以下になります↓
https://atcoder.jp/contests/abc165
公式の解説(Editorial)は以下になります↓
https://img.atcoder.jp/abc165/editorial.pdf

A問題:

AからBまでの範囲に含まれるKの倍数の個数が分かれば、この問題を解くことができます。
これは、1からBまでの範囲に含まれるKの倍数の個数と、1からA-1までの範囲に含まれるKの倍数の個数を求めることで得ることができ、1からnまでの範囲に含まれるKの倍数の個数はn//Kにより求めることができるので、B//K-(A-1)//Kが0であれば答えはNG、そうでなければ答えはOKとなります(O(1)で解かずとも、A<=nK<=Bを満たすnが存在するかを全探索により確かめてもよいです、ただいずれにせよA問題で出す内容ではないと思います)。

B問題:

問題文に示されているとおり、今の所持金を(所持金)+(所持金)//100として更新することで最小の年数を求められます。
制約よりX<=10^18なので、X=10^18のときの操作回数が分かれば、この方法で間に合うかを確かめられます。
ここでサンプルケースを見ると、最大のXが与えられた場合に必要な操作回数が3760回であることが分かるので、以上の方法によりこの問題を解くことができました
(2項定理により(1+x)^n>=1+xnであることと、所持金が2倍になる年数が分かれば2^10≒10^3よりそれを60倍することでX=10^18の場合の操作回数が分かることを踏まえると、x=0.01より、高々100年経てば所持金が2倍になるので、X=10^18の場合の操作回数は高々6000回であることが分かり、
サンプルケースに頼らずとも間に合うことが分かります)。

C問題:

最大のケース(N=10,M=10)の場合に、そのような条件を満たすものの個数がいくつあるのかを考えます。
これは重複組み合わせにより(N+M-1)CNとして求めることができ、これより条件を満たすものの個数が高々92378個であることが分かります。
よって、すべてのパターンについてQ個の条件を確かめても、計算回数は高々92378*50≒4.6*10^6であることが分かるので、この問題を全探索により解けることが分かりました。
実装の際は単に10重ループを書くのが簡単でよいです(DFSでの実装が分からないからといって悩むのは損です)。
Pythonの場合はitertools.combinations_with_replacement(range(1,M+1),N)とすることで条件を満たすすべての数列を生成できます。

サンプルコード(Python):
https://atcoder.jp/contests/abc165/submissions/12606378

n,m,q=map(int,input().split())
arr=[list(map(int,input().split())) for _ in range(q)]
ans=0
for i1 in range(1,m+1): #愚直に10重ループを行っても、そのループ回数は高々92378回
 for i2 in range(i1,m+1):
   for i3 in range(i2,m+1):
     for i4 in range(i3,m+1):
       for i5 in range(i4,m+1):
         for i6 in range(i5,m+1):
           for i7 in range(i6,m+1):
             for i8 in range(i7,m+1):
               for i9 in range(i8,m+1):
                 for i10 in range(i9,m+1):
                   tmp=0
                   arrs=[0,i1,i2,i3,i4,i5,i6,i7,i8,i9,i10]
                   for a,b,c,d in arr: #条件を満たす数列について、最大値を求める
                     if arrs[b]-arrs[a]==c:
                       tmp+=d
                   ans=max(ans,tmp)
print(ans)

D問題:

明らかに、f(x)=(Ax)//B-A*(x//B)は周期性を持ち、その周期はBです(f(x+B)=f(x)となることを確かめればよいです)。
これよりxとして0<=x<Bのみを考えればよく、この条件の下では(x//B)=0であることと(Ax)//Bが単調増加となることから、0<=x<Bと0<=x<=Nの両方を満たす最大のxを選べばよいです。
このようなxはmin(B-1,N)として表せるので、この問題を解くことができました。

サンプルコード(Python):
https://atcoder.jp/contests/abc165/submissions/12659464

a,b,n=map(int,input().split())
x=min(b-1,n) #上記よりxとしてmin(B-1,N)を選ぶのが最善
print((a*x)//b-a*(x//b))

E問題:

ある組(i,j)について、iからjへの距離abs(i-j)とjからiへの距離abs(N+i-j)を考えることとします。
このとき、N回のラウンドで、abs(i-j)またはabs(N+i-j)が等しくなるすべての(i,j)の組は一度ずつ対戦します。
したがって、対戦カードとしてはじめに選ぶM個の2数の組(ai,bi)は、abs(ai-bi)とabs(N+ai-bi)がすべて異なるようにしなくてはなりません。
Nが奇数のとき、1からNまでの数を両端から取って対戦カードを組むと、
それらの組はabs(ai-bi)とabs(N+ai-bi)がすべて異なる値になります(∵Nが奇数よりabs(ai-bi)とabs(N+ai-bi)の偶奇が異なり、abs(ai-bi)はN-1から2ずつ減少していくので、これらの値が重複することはありません)。
一方Nが偶数のとき、abs(ai-bi)とabs(N+ai-bi)の偶奇が等しいことから、上記の構成方法を取るとabs(ai-bi)またはabs(N+ai-bi)が等しくなる組が2つずつできてしまいます。
これを回避するためには、abs(ai-bi)またはabs(N+ai-bi)がすでに見た値になるとき、またはabs(ai-bi)==abs(N+ai-bi)となるとき、biを-1する代わりに-2すればよいです(∵biを-2することでそれまでのabs(ai-bi),abs(N+ai-bi)と偶奇が入れ替わるので、重複しなくなります)。
また制約より、以上の取り方でM個の組を生成できることが分かります。
以上によりこの問題をO(N)で解くことができました。

サンプルコード(Python):
https://atcoder.jp/contests/abc165/submissions/12661245

n,k=map(int,input().split())
ans=[]
a=1
b=n
s=set()
for _ in range(k):
 s.add(abs(a-b))
 s.add(abs(n+a-b)%n)
 ans.append([a,b])
 a+=1 #基本的には1からNまでの数を両端から取っていく
 b-=1
 if abs(a-b) in s or abs(n+a-b)%n in s or abs(a-b)==abs(n+a-b):
   #上記の条件を満たすとき、右側から取っている数を1小さくして偶奇を入れ替える
   b-=1
for i in range(k):
 print(*ans[i])

F問題:

愚直な解法として、各頂点まで見たときの最長増加部分列をパラメータに持つDFSが考えられます。
しかし、これは制限時間には間に合わないので、この解法を改善する必要があります。
この解法が制限時間に間に合わないのは、最長増加部分列を複数保持していることが原因です。
したがって、最長増加部分列を1つだけ用い、各頂点まで見たときの最長増加部分列を求めることができれば、この問題を解くことができます(∵DFSの計算量はO(N)、各頂点について最長増加部分列を求めるために2分探索を行うのでトータルO(NlogN)になります)。
これは、ある頂点で最長増加部分列を更新するとき、DFSの行きの時点で更新した場所と元の値をスタックに記録しておき、DFSの戻りの時点でスタックから更新した場所と元の値を取り出し、最長増加部分列をその頂点で更新する前の状態に戻すことで実現できます。
以上によりこの問題を解くことができました。

サンプルコード(Python):
https://atcoder.jp/contests/abc165/submissions/12659379

import bisect
import sys
sys.setrecursionlimit(10**7)

def dfs(v):
 #DFSの行き(子ノードに下っていくとき)の処理
 pos=bisect.bisect_left(dp,arr[v]) #最長増加部分列で更新する場所を2分探索により求める
 changes.append((pos,dp[pos])) #更新した要素とその値を記録しておく
 dp[pos]=arr[v]
 ans[v]=bisect.bisect_left(dp,10**18) #1からvまでの最長増加部分列の長さは、最長増加部分列の10**18以外の値の個数に等しい
 for u in g[v]:
   if checked[u]==0:
     checked[u]=1
     dfs(u)
 #DFSの戻り(親ノードに上っていくとき)の処理
 pos,val=changes.pop() #頂点vで更新した最長増加部分列の値を元に戻す
 dp[pos]=val

n=int(input())
arr=[0]+list(map(int,input().split()))
g=[[] for _ in range(n+1)]
for _ in range(n-1):
 a,b=map(int,input().split())
 g[a].append(b)
 g[b].append(a)
ans=[0]*(n+1)
checked=[0]*(n+1)
checked[1]=1
dp=[10**18 for _ in range(n+1)] #最長増加部分列を求めるのに、十分大きな値で初期化しておく
changes=[]
dfs(1)
for i in range(1,n+1):
 print(ans[i])