algoNote

プログラミング関連

SRM 718 Div2

※Hardを解いてからアップしようと思って書いてあった記事が下書きにあったので(Hardはまだ解けていませんが)アップしておきます。

SRM718Div2に参加しました。

Hardが解けなかったり、終了間際にmedのミスに気づいてresubmitしたりと満足いく結果ではありませんでしたが、ついに念願の青コーダーになることが出来ました。(嬉しい!)

[easy] RelativeHeights

問題概要

配列hが与えられる。hから任意1要素削除して得られる列において、要素の大きい順にインデックスを並べた列をgとすると、gとしてあり得る列はいくつあるか。

制約

  • {1 \leq |h| \leq 50}

解法

要素の数が50以下なので全探索できます。setなどを使ってカウントすれば良いです。

ソースコード

[medium] InterleavingParenthesisDiv2

問題概要

'(',')'からなる括弧列s1とs2が与えられる。2つの括弧列の左の括弧から任意に取っていってマージされた括弧列を作る。新しく出来る括弧列が次の「正しい括弧列の条件」を満たすとき、括弧列の作り方は何通りあり得るか。(新しく作られる括弧列が同じでも、マージの仕方が違う場合別としてカウントする) 109+7で割った余りを答えなさい。

正しい括弧列の条件

  • ""(空の括弧列)
  • X,Yがそれぞれ正しい括弧列であるとき"XY"
  • Xが正しい括弧列であるとき"(X)"

制約

  • {1 \leq |s1| \leq 50}
  • {1 \leq |s2| \leq 50}

解法

まず、ある括弧列が正しい括弧列かどうか判定する方法を考えます。 ある括弧列について'('→+1、')'→-1として累積和を取って行くときに、途中で和が負になったらその文字列は正しい括弧列ではありません。(括弧列の中に')'に対応する'('が存在しないことになるため) さらに、最後まで和をとったときに0になっていない場合も正しい括弧列ではありません。それ以外は正しい括弧列になります。

そして、この問題を解くために次のDPを考えます

dp[i][j][k][l] := s1をi文字、s2をj文字使ったとき、上で考えた累積和がkであるときに、マージした括弧列の長さがlであるような括弧列の作り方の個数

dpの更新は

  • s1[i]=='(' なら dp[i+1][j][k+1][l+1]+=dp[i][j][k][l];
  • s1[i]==')' なら dp[i+1][j][k-1][l+1]+=dp[i][j][k][l];
  • s2[j]=='(' なら dp[i][j+1][k+1][l+1]+=dp[i][j][k][l];
  • s2[j]=='(' なら dp[i][j+1][k-1][l+1]+=dp[i][j][k][l];

です。(MODで余りを取ることに注意)

求める答えはdp[s1.size()][s2.size()][0][s1.size()+s2.size()]%MODになります。

ソースコード

[hard]

まだ解けていません。。