ABC312のA～D問題の解説を書きたいと思います。いつものことながら、あてになるかはわかりませんが、温かい目で見ていただけると嬉しいです…
A問題 Chord
問題文に書いてある、「 ACE、BDF、CEG、DFA、EGB、FAC、GBD 」の部分をコピーし、リストにそれぞれの各要素を入れ、入力として受け取った文字列が、リストの中に含まれているかどうかを確かめることによって、答えが分かります。
Pythonの例
s=input() a=["ACE","BDF","CEG","DFA","EGB","FAC","GBD"] if s in a: print("Yes") else: print("No")
B問題 TaK Code
問題文中に、「TakCodeは以下のようなものです」と書いてある部分があります。
###.?????
###.?????
###.?????
....?????
?????????
?????....
?????.###
?????.###
?????.###
？の部分は「＃」でも、「.」でもどちらでもよい部分です。ですから、ここの場所は必ずこの記号でなければいけないというところだけを探索すれば、それがTak Codeかどうかわかります。9*9マスを右下に確保できるような四角の左上の頂点を全探索して、個数をカウントします。
Pythonの例…
h,w=map(int,input().split()) rotti = [[] * 1 for i in range(h)] for i in range(h): rotti[i]=list(input()) for i in range(h-8): for ipp in range(w-8): if rotti[i][ipp]!="#": continue if rotti[i][ipp+1]!="#": continue if rotti[i][ipp+2]!="#": continue if rotti[i][ipp+3]!=".": continue #二段目 if rotti[i+1][ipp]!="#": continue if rotti[i+1][ipp+1]!="#": continue if rotti[i+1][ipp+2]!="#": continue if rotti[i+1][ipp+3]!=".": continue #三段目 if rotti[i+2][ipp]!="#": continue if rotti[i+2][ipp+1]!="#": continue if rotti[i+2][ipp+2]!="#": continue if rotti[i+2][ipp+3]!=".": continue #四段目 if rotti[i+3][ipp]!=".": continue if rotti[i+3][ipp+1]!=".": continue if rotti[i+3][ipp+2]!=".": continue if rotti[i+3][ipp+3]!=".": continue #添え字で６ if rotti[i+5][ipp+5]!=".": continue if rotti[i+5][ipp+6]!=".": continue if rotti[i+5][ipp+7]!=".": continue if rotti[i+5][ipp+8]!=".": continue #添え字で７ if rotti[i+6][ipp+5]!=".": continue if rotti[i+6][ipp+6]!="#": continue if rotti[i+6][ipp+7]!="#": continue if rotti[i+6][ipp+8]!="#": continue #添え字で８ if rotti[i+7][ipp+5]!=".": continue if rotti[i+7][ipp+6]!="#": continue if rotti[i+7][ipp+7]!="#": continue if rotti[i+7][ipp+8]!="#": continue #9 if rotti[i+8][ipp+5]!=".": continue if rotti[i+8][ipp+6]!="#": continue if rotti[i+8][ipp+7]!="#": continue if rotti[i+8][ipp+8]!="#": continue print(i+1,ipp+1)
C問題 Invisible Hand
（適切な解き方かわかりませんが、自分のやった方法を書きます）
例えば、りんごをX 円で売ってもよいと考える売り手の人数をP人、りんごをX円で買ってもよいと考える買い手の人数をQ人とすると、P人とQ人が変わる境界の値はすでに決まっています。それは、数列A、数列Bの各要素と、その要素＋１の値と、その要素ー１の値です。それ以外の値で、その値に１を足したりすることによって、PとQの人数が変わるということはありえないので、ここを全探索してあげて、その中でPがQより大きかった値のうち、最小のものを出力すればよいです。また、TLEにならないように、PとQの値を求める時には二分探索を使用します。
また、全探索する値に０円も追加しました。
Pythonの例（コンテスト中にあせりながら実装したので汚いです…）
import bisect def rotti(x): global a,b,m hako=bisect.bisect(a,x) hako2=bisect.bisect(b,x-1) hako2=m-hako2 if hako>=hako2: return 0 else: return 1 n,m=map(int,input().split()) a=sorted(list(map(int,input().split()))) b=sorted(list(map(int,input().split()))) saisyou=10000000000000000000000 for i in range(n): if rotti(a[i])==0: saisyou=min(saisyou,a[i]) if rotti(a[i]+1)==0: saisyou=min(saisyou,a[i]+1) if rotti(a[i]-1)==0: saisyou=min(saisyou,a[i]-1) for i in range(m): if rotti(b[i])==0: saisyou=min(saisyou,b[i]) if rotti(b[i]+1)==0: saisyou=min(saisyou,b[i]+1) if rotti(b[i]-1)==0: saisyou=min(saisyou,b[i]-1) if rotti(b[len(b)-1]+1)==0: saisyou=min(saisyou,b[len(b)-1]+1) if rotti(a[len(a)-1]+1)==0: saisyou-min(saisyou,a[len(a)-1]+1) if rotti(0)==0: saisyou=min(saisyou,0) if rotti(b[0]-1)==0: saisyou=min(saisyou,b[0]-1) if rotti(a[0]-1)==0: saisyou=min(saisyou,a[0]-1) print(saisyou)
D問題 Count Bracket Sequences
この問題はDPを使って解くことができます。DPについて知らない方は、ネットなどで調べてみてください。基本的なことが分かれば、この問題は特に難しくはないと思います。
まず、文字列の長さが２で割ることができなければ、括弧列にすることは絶対に不可能なので、文字列の長さが２の倍数であることを前提に説明します。
どうやってDPをするのかというと、「Ｎ個までの文字列の中で、i番目までに何個の ( を置いたか」でDPをします。
それぞれの要素の中で、何通りかをどんどん足していき、最終的に出力するのは、N個のうち、N/2個の ( を置いたときの値です。
また、括弧列は、ひとつの（）のセットの中で、 ) が ( より先に設置することはできないので、Ｎ個までの中で、置いた ( が ) を置いた個数より少ない場合は、そこを０通りにしてあげることによって、うまく計算することができます。
また、そのまま愚直に計算していくと、今回は値が大きくなってしまいます。答えとして出力するときは998244353のあまりを出力すればよいので、DPをしているときも、どんどんあまりをとってよいです。あまりをとらないと実行時間がかかってTLEになってしまいます。
Pythonの例
s=list(input()) if len(s)%2==1: print(0) exit() noruma=len(s)//2 mod=998244353 dp=[[0] * (noruma+1) for i in range(len(s)+1)] dp[0][0]=1 count=-1 for i in range(len(s)): count+=1 if s[i]=="(": for ipp in range(noruma): if count-ipp>ipp: continue dp[i+1][ipp+1]=(dp[i+1][ipp+1]+dp[i][ipp])%mod continue elif s[i]==")": for ipp in range(noruma): if count-ipp>ipp: continue dp[i+1][ipp]=(dp[i+1][ipp]+dp[i][ipp])%mod dp[i+1][noruma]=(dp[i+1][noruma]+dp[i][noruma])%mod continue for ipp in range(noruma): if count-ipp>ipp: continue dp[i+1][ipp]=(dp[i+1][ipp]+dp[i][ipp])%mod dp[i+1][ipp+1]=(dp[i+1][ipp+1]+dp[i][ipp])%mod dp[i+1][noruma]=(dp[i+1][noruma]+dp[i][noruma])%mod print(dp[len(dp)-1][len(dp[len(dp)-1])-1]%mod)
最後までありがとうございました！少しでも役にたてれば幸いです。
