ABC324の解説 A~E問題
毎回、この解説はあんまり良くないよ…！とか書いてましたが、めんどくさいのでもうやめちゃいます。てへっ
A問題 Same
この問題は単純なアルゴリズムでも求めることができます。つまり、すべての数字を確認していって、全部の数字が同じだったらYesを出力、そうでなければNoを出力すればよいです。
Pythonの例
n=int(input()) a=list(map(int,input().split())) num=a[0] check=0 for i in range(1,n): if a[i]!=num: check=1 break if check==1: print("No") else: print("Yes")
また、これ以外の方法でも解くことができます。上に書いたように、単純なアルゴリズムだとコードの長さが長くなってしまいます。コンテストにおいて、問題をはやくとくことは重要なので、できるだけ書くコードの長さが短くなるようなアルゴリズムを考えたいです。
ぼくがコンテスト中に書いたコードは、配列Aをソートして、一番前の数字と一番うしろの数字が一緒だったらYesを出力、そうでなければNoを出力する…というアルゴリズムでした。
コード
n=int(input()) a=sorted(list(map(int,input().split()))) if a[0]==a[n-1]: print("Yes") else: print("No")
このように、アルゴリズムの工夫次第では書くコードの長さが減ったりします。
B問題 3-smooth Numbers
N=2^x3^yをみたす場合、Nは２と３だけで割り切ることができます。
ですから、２と３で割れるだけ割って、その結果Nが１になればYes、そうでなければNoを出力するようにすればACを得られます。
Pythonのコード
n=int(input()) while n%2==0: n=n//2 while n%3==0: n=n//3 if n==1: print("Yes") else: print("No")
C問題 Error Correction
一見、難しそうに見えますが、単純にすべての条件をやってみればACを得ることができます。
あまりむずかしいアルゴリズムは使いませんが、実装が少し面倒な問題だったかもしれませんね〜
Pythonの自分のコード
n,s=input().split() ans=[] for i in range(int(n)): t=input() if s==t: ans.append(i+1) continue if len(t)==len(s)+1: iti=0 count=0 if list(t)[0:len(t)-1]==list(s)[0:len(s)]: ans.append(i+1) continue for ipp in range(len(t)): if t[ipp]!=s[iti]: count+=1 continue iti+=1 if count==1: ans.append(i+1) continue if len(t)==len(s)-1: count=0 iti=0 if list(t)[0:len(t)]==list(s)[0:len(s)-1]: ans.append(i+1) continue for ipp in range(len(s)): if s[ipp]==t[iti]: iti+=1 else: count+=1 if count==1: ans.append(i+1) continue if len(s)==len(t): count=0 for ipp in range(len(s)): if s[ipp]!=t[ipp]: count+=1 if count==1: ans.append(i+1) print(len(ans)) print(*ans)
D問題 Square Permutation
この問題は、最初に全探索するアルゴリズムが思いついた人が多かったと思います。ぼくも最初は並び替えてできる整数を全部確かめるものだと思いました。
しかし、その方法だとTLEになります。詳細な数字は省きますが、Nが13だったときは何億か計算することになってしまってとても間に合わなくなってしまいます。
ではどうするのかというと、全探索するのはありえる数の方ではなくて、平方数を全探索します。
つまり、制約としてありえる中で最大の平方数までを先に計算しておいて、その平方数を作ることができるか…というふうにカウントしていけばTLEにならずACを得ることができます。
Pythonの自分のコード
n=int(input()) s=sorted(list(input())) count=len(s) amount=[0] for i in range(1,6000000): amount.append(i*i) ans=0 for i in range(len(amount)): hako=list(str(amount[i])) for ipp in range(count-len(hako)): hako.append("0") hako=sorted(hako) if hako==s: ans+=1 print(ans)
E問題
Twitterなどを見かけていると自分のアルゴリズムとは違う方法で解いている人が多かった気がします（他の人が言っていたのはどんなアルゴリズムだったか忘れてしまいました…）。
ぼくは、DPを使ってときました。
（あとから見返して思いましたが説明が下手くそです）
文字列SがN個あるわけですが、最初にこういう計算をします。
その文字列はTの部分文字列何個目までを含んでいるか…
例えば問題文にのっている入力例１の１つ目のS、”abba”を見ていきます。
このとき、Tはbacなので、Tのうち"ba"までを含んでいることがわかります。
ですからDPの２つ目の要素にインクリメントします。
そんなふうにTの何番目まで行くことのできる文字列は何個あるのか…がわかるようにします。
次はN個の文字列のうち、後ろから見ていったときにTの後ろから何番目までを部分文字列として含んでいるか…を確認していきます。
例えばまた"abba"を見ていったとき、Cを一つも含んでいないのでゼロ番目まで部分文字列として含んでいます（含んでいない）。
そんなふうに見ていってDPの配列のやつと合体して…（語彙力が死にましためっちゃごめんなさいここまで読んだら解ると思います）
自分の（クソ）コード
n,t=input().split() dp=[0]*(len(t)+1) n=int(n) count=len(t) rotti=[] for i in range(n): s=input() iti=0 for ipp in range(len(s)): if t[iti]==s[ipp]: iti+=1 if iti==count: break dp[iti]+=1 rotti.append(s) ans=0 count=len(dp) count2=len(t) for i in range(n): hako=rotti[i] iti=len(hako)-1 for ipp in range(len(dp)): ans+=dp[count-1-ipp] if len(hako)==0: break if ipp+1==len(dp): break while iti>=0 and t[count2-ipp-1]!=hako[iti]: iti-=1 if iti<0: break else: iti-=1 print(ans)
最後までありがとうございました。解説を書くのは難しいですね〜〜
