hitoare日記

たまに書きます

E - Shorten ABC(AtCoder Regular Contest 110)

解説とは若干違う解法。

問題リンク

atcoder.jp


問題概要

 A,B,Cからなる長さNの文字列が与えられる。

この文字列に、次の操作を0回以上繰り返して得られる文字列は何通りか。

  • 連続する2文字で、文字が異なっているものを選び、そのどちらとも異なる文字1つに置き換える(すなわち、AB,BA→C、AC,CA→B、BC,CB→Aと置き換える)
解法

 Aを1、Bを2、Cを3とする数列と見る。

すると、操作は連続する2要素をxorをとったもので置き換える操作に言い換えられる。

自分の解法では、ここからさらに累積xorをとった。

こうすることで、操作は単純に前の要素の消去に言い換えられるので、部分列の数え上げに帰着できる。ただし、同じ要素が連続するようなものはダメ、かつ一番後ろの要素は消去できないので、「同じ要素が連続しない、最後の要素を含む部分列の総個数」を数えることになる。

サンプル1を例に変換の過程を示す。

ABAAC

→ 1 2 1 1 3(A,B,Cを1,2,3に)

→ 1 3 2 3 0 (累積xorをとる)

この時、例えば部分列「1 3 2 0」は、最後のACに対して操作を行ったと考えると文字列「ABAB」に対応していることがわかる。

また、例えば「1 3 3 0」のような数列は作れない。なぜなら、累積xorをとる前の復元すると「1 2 0 3」となり、0に対応する文字は存在しないからである。(これはAA,BB,CCに対して操作を行ってしまったことに相当する) また、1文字目に0が来ることも有り得ない。

これらの条件を満たしていて、かつ2種類以上の文字が存在すれば全ての部分列に対して上の操作を繰り返して得られる(はずだが、未証明)。一方、最初の時点で文字が1種類ならば答えは1になる。

よって、サンプル1の答えは「10」「20」「30」「120」「130」「230」「320」「1230」「1320」「3230」「13230」に対応する11が答え。

 

部分列の数え上げは自分は初めてやったがかなり典型らしく、drkenさんの記事

部分列 DP --- 文字列の部分文字列を重複なく走査する DP の特集 - Qiita

などにまとまっている。

また、JOI2011春合宿のdeciphering - 解読 (Deciphering)がこの問題とほぼ同じ処理になる。

提出

https://atcoder.jp/contests/arc110/submissions/18593134

感想

 最初、同じ部分列でも位置が違えば別々にカウントできると勘違いしていてかなりタイムロスした。その後もかなりバグった。

B - Bracket Score(AtCoder Grand Contest 048)

問題リンク


問題概要

 '(', ')', '[', ']'からなる文字列で、括弧が正しく対応しているものを「良い括弧列」と呼ぶ。

偶数\(N\)と、長さ\(N\)の整数列\(A,B\)が与えられる。

長さ\(N\)の良い括弧列\(s\)に対し、\(i\)文字目が'('または')'ならば\(A_i\)点、'['または']'ならば\(B_i\)点が入る。

合計得点の最大値を求めよ。

解法

一度に4種類の文字を考えるのは複雑なので、まず次の問題を考える。

abからなる\(N\)文字の文字列で、次の性質を満たすのはどのような文字列か。

  • aに'('または')'、bに'['または']'を対応させて、良い括弧列にできる (これを性質(1)とする)

すぐにわかることとして、abの個数はともに偶数個であることが必要である。

次に、文字列が性質(1)を満たすとする。この時、括弧列にした時、連続する2文字で()もしくは[]になる部分があるので、文字列ではaaもしくはbbと同じ文字が連続する部分が存在し、さらにこの2文字を削除してもその文字列は良い括弧列にできる。よってこの操作を繰り返して全ての文字を削除できる。

逆に、この操作が行えない文字列はababab...かbababa...のように奇数番目と偶数番目でabが完全に分かれるパターンしかない。

「連続する2文字を削除する操作」では奇数番目と偶数番目を1つずつ消し、さらに残った文字に対しその文字が奇数番目か偶数番目かという性質は保たれるので、性質(1)を満たさない文字列では奇数番目のaと偶数番目のaの数は異なる(bも同じ)。

よって、文字列が性質(1)を満たすならば次を満たす。

  • 奇数番目のaと偶数番目のaの個数が等しく、奇数番目のbと偶数番目のbの個数も等しい (これを性質(2)とする)。

逆に、文字列が性質(2)を満たすならば性質(1)を満たす。これは、性質(2)を満たす限り連続するaabbが存在し、それを削除した文字列も性質(2)を満たすので、文字の削除を続けて空文字列にすることができ、削除した2文字に括弧を対応させていけば良い括弧列が得られることからわかる。

よって、性質(2)が性質(1)の必要十分条件であることがわかった。

また、性質(2)はaについての条件を満たせば、自動的にbも条件を満たすこと、またabの個数がそれぞれ偶数になることも簡単にわかる。

 

上の考察より、元の問題は次の問題に帰着できる。

長さ\(N\)の整数列\(A\)と\(B\)が与えられる。

次の条件を満たすように\(1 \leq i \leq N\)に対し\(A_i\)と\(B_i\)のどちらかを選んだ時の合計の最大値を求めよ。

  • 偶数番目で選んだA/Bと奇数番目で選んだA/Bの個数が等しい
提出 

https://atcoder.jp/contests/agc048/submissions/17507718

感想

橙になった。

意識して思考過程を多めに書いてみた。

F - Unbranched(AtCoder Beginner Contest 180)

問題リンク


問題概要

 頂点にラベルが振られている\(N\)頂点\(M\)辺の無向グラフであって、以下の条件を満たすものはいくつあるか求めよ。

  • 自己ループを持たない
  • 全ての頂点の次数が2以下
  • 連結成分のサイズの最大値が\(L\)
解法

 2番目の条件より、各連結成分については一本道のようなグラフ(o-o-o-...-o-o)か、単純サイクル、もしくは孤立点しかありえない。よって、連結成分のサイズを決めればその中での辺の数と組み合わせは簡単に求まる。

この問題では\(N\)個の頂点をいくつかの連結成分に分割する必要がある。

ここで、この問題を解く着想を得るために、一旦より簡単な次の問題を考える。

{1,2,...,N}をいくつかのグループに分割する方法は何通りあるか。

これは以下のようなDPで解ける。

\(dp[i] = \{1,..,i\}\)の分け方の総数

とおく。\(dp[1]=1\)である。また、このあとの都合上\(dp[0]=1\)とする。

\(dp[i-1]\)までが求まっているとして\( \{1,...,i\}\)の分け方の総数を求める。

\(i\)が属するグループのサイズを\(j (1 \leq j \leq i) \)とすると、

このようなグループのとり方は\( {}_{i-1}C_{j-1} \)通りある。(\(i\)以外の要素を\( \{ 1,...,i-1\}\)から\(j-1\)個とるため)

また、残りの\(i-j\)個の点の分け方は\(dp[i-j]\)通りである。

よって、\(dp[i] = \sum_{j=1}^{i} {}_{i-1}C_{j-1} \times dp[i-j] \)

となる。

 

元の問題に戻る。

\(dp[i][j][k] \)を

頂点を\(i\)個使って

辺を\(j\)本使って

連結成分の最大値が\(L\)かどうか\( (k=0or1) \)

を満たすようなグラフの総数

として、\(i=1\)から\(N\)まで更新していけば良い。

計算量は\( O(NML) \)になる。

提出

https://atcoder.jp/contests/abc180/submissions/17463080

感想

 初1桁が嬉しくて久々に書いた。