2 - マスコットの片付け (Mascots) (JOI2013春合宿2日目)

数え上げはそこそこ得意だと思っていたのに、解けなくて解説を見たので。

問題リンク

問題概要

R×Cのマス目に好きな順番でコマを1マスに1つずつ置いていく。いくつかのマスには最初からコマが置かれている。

コマが置かれたマスが長方形をなす回数を最大化するようなコマの置き方は何通りか。

解法

 後半部分のみを解説します。

長方形を

• 上に伸ばす
• 下に伸ばす
• 左に伸ばす
• 右に伸ばす

操作を考えると、これらはそれぞれ回数が決まっていて、かつそれぞれの操作の際に長方形の縦もしくは横の長さの階乗が組み合わせ総数にかかります。

ここで一旦上下と左右をそれぞれ同一視すると

• 縦に伸ばす
• 横に伸ばす

の2パターンになります。当然回数は決まっています。

例えば、上2回・下1回・左1回・右3回の時は

縦3回・横4回になるので

[-][-][-][-][-][-][-]

や

[-][-][-][-][-][-][-]

などのパターンが考えられます。

ここで各操作にかかる係数はその時点での長方形の縦・横幅のみに依存する

(ここがポイントで、今は縦・横の操作の回数という観点でのみ考えているので、「上の操作ばっかりではみ出す」みたいなことは考えなくて良い)

ので、状態数がせいぜいR×CのDPで計算可能です。

最後に、縦と横の操作にそれぞれ上下・左右を割り当てます。

[-][-][-][-][-][-][-]

のパターンからは例えば

[-][-][-][-][-][-][-]

のような割り当てが可能ですが、

この割り当ては上下と左右で独立、かつ全てのパターンについて同じ式

(「縦の回数」個から「上の回数」個を選ぶ組み合わせ数と、「横の回数」個から「左の回数」個を選ぶ組み合わせ数の積)

なので、単純に掛けてしまえば良いです。

まとめると

• 上方向と下方向(左方向と右方向)の遷移は同じ式なので、同一視してみると状態としては単純に横幅と縦幅だけを考えていることになる。
• 横幅と縦幅だけを状態として見る場合、DPがO(RC)で出来る。
• その後上下・左右をそれぞれ分離する。全パターンに対し同じ係数を掛けているので、結局全体にそれを掛ければ良い。

となる。

提出

https://atcoder.jp/contests/joisc2013-day2/submissions/23933535

感想

途中の操作をあえて抽象化する(上下・左右を同一視する)のが難しい。

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種類の文字を考えるのは複雑なので、まず次の問題を考える。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

提出 

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

感想

橙になった。

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