ABC326のA~D問題の解説
A問題 2UP3DOWN
この問題はもうやるだけです。
Pythonの自分のコード
a,b=map(int,input().split()) if a<b and a+2>=b: print("Yes") elif a>b and a-3<=b: print("Yes") else: print("No")
B問題 326-like Numbers
制約が小さいので(326-like Numbersは3桁の数だから)、単純な探索が通ります。
Nに1ずつ足していってその都度326-Like Numberか確認していけばよいです。
ぼくは何を思ったのか、さきにすべての326-like numberをSetに格納して、1ずつ足していって326-like numberが確認するときにそのSetに入っているかどうかで判定するようにしていました。
Pythonの自分のコード
rotti=[] for i in range(9): for ipp in range(10): rotti.append(str(i+1)+str(ipp)+str((i+1)*ipp)) n=int(input()) rotti=set(rotti) for i in range(n,1000): if str(n) in rotti: print(n) exit() n+=1
C問題 Peak
いもす法(?)みたいな感じでやりました(たぶん…)
Stackに左側にあるプレゼントから足していって、その時足したプレゼントよりM以上離れているプレゼントはもうとれないものにします。
1つプレゼントを足すたびにそのとき取れるプレゼントの数を確認し、最大の数を更新していきます。
一つの範囲でとれるプレゼントの数を全部チェックしていくとTLEになってしまうので、このような工夫が必要です(説明が下手くそでごめんなさい)。
Pythonの自分のコード
n,m=map(int,input().split()) a=sorted(list(map(int,input().split()))) stack=[] iti=0 ans=0 i=0 while i<n: hako=a[i] while i<n and a[i]==hako: stack.append(a[i]) i+=1 while iti<len(stack): if stack[iti]<=hako-m: iti+=1 else: break ans=max(len(stack)-iti,ans) print(ans)
D問題 ABC Puzzle
この問題は全探索が通ります。
…と言ってもすべてのマスに対して全探索するのではさすがに間に合わないので、工夫して全探索する必要があります。
いろんなやり方があると思いますが、ぼくのやった方法を説明します。
ひとつの行、列にA,B,Cがちょうど一個ずつ含まれるて、一番端に近いのが配列Rや配列Cの要素とおんなじ(ここの説明が下手)並べ方はNが最大の5であった場合でもABC..の並び替えであるので20通りしかありません。ぼくは各列に対してこれを全部試しました(20^5)。
次に、その方法で作った二次元配列などが、条件をすべて満たしているかどうかを確認します。
…この方法を繰り返して、全部の並べ方が終わるまでに条件を満たすものが見つかったらその配列などを出力し、そうでなかったらNoを出力すればよいです。
自分で説明したのに言うのも何ですが、公式の解説のほうがめちゃくちゃわかりやすいです(というか自分のやった方法はほとんど公式の解説とおんなじ)。
まあ…この解説は、ヒントぐらいには丁度いいかもしれないですね〜
頑張ってください!(?)
Pythonの自分の例
stack=["A","B","C"] n=int(input()) if n>=4: stack.append(".") if n>=5: stack.append("#") iti=0 box=["A","B","C",".","#"] while len(stack[iti])<n: hako=stack[iti] for i in range(n): if not box[i] in hako: stack.append(hako+box[i]) iti+=1 stack=stack[iti:len(stack)] rotti=[[]*1 for i in range(3)] for i in range(len(stack)): hako=list(stack[i]) hako2="" for ipp in range(n): if hako[ipp]=="#": hako2=hako2+"." else: hako2=hako2+hako[ipp] iti=0 for iti in range(n): if hako2[iti]==".": continue if hako2[iti]=="A": rotti[0].append(hako2) elif hako2[iti]=="B": rotti[1].append(hako2) elif hako2[iti]=="C": rotti[2].append(hako2) break if n==5: count=20 elif n==4: count=8 else: count=2 bit=[] for i in range(count): bit.append([i]) iti=0 while len(bit[iti])<n: hako=bit[iti][0:len(bit[iti])] for i in range(count): hako.append(i) bit.append(hako[0:len(hako)]) hako.pop() iti+=1 bit=bit[iti:len(bit)] for i in range(3): rotti[i]=list(set(rotti[i])) r=list(input()) c=list(input()) for i in range(len(bit)): grid=[["."]*n for i in range(n)] hako=bit[i][0:len(bit[i])] for ipp in range(n): if r[ipp]=="A": count=0 elif r[ipp]=="B": count=1 else: count=2 hako2=rotti[count][hako[ipp]] for k in range(n): grid[ipp][k]=hako2[k] #縦向きでABCの個数が一個ずつか check=0 for ipp in range(n): hako=set() for k in range(n): if grid[k][ipp]==".": continue if grid[k][ipp] in hako: check=1 break hako.add(grid[k][ipp]) if len(hako)!=3 or check==1: check=1 break if check==1: continue #Cの言うとおりになっているかどうかチェック for ipp in range(n): hako=c[ipp] for k in range(n): if grid[k][ipp]==".": continue if grid[k][ipp]!=hako: check=1 break if check==1: break if check==0: break else: print("No") exit() print("Yes") for i in range(n): for ipp in range(n): print(grid[i][ipp],end='') print()
E問題は…diffだけ見ればD問題とほぼおんなじ難易度ですが…ぼくはまだ期待値を習ってないのでよくわかんなかったです^^
最後までありがとうございました。