diverta 2019 Programming Contest A~E

コンテストに遅刻したので戒めに解きました。

問題文 Tasks - diverta 2019 Programming Contest

A

N-K+1を出力すればいいです.

B

問題

整数R,G,B,Nが与えられたとき, 以下を満たす(r,g,b)の組はいくつあるか？

$R r + G g + B b = N$

ただし, R,G,B,Nはそれぞれ1以上3000以下.

解法

rとgが決まると上式よりbが一意に定まる.

このことから, rとgに関して二重forを回すとO(N²)となって間に合う.

C

問題

2文字以上10文字以下の文字列がN個与えられます.

全ての文字列を任意の順番で結合し, 1つの文字列を作ろうとしたとき, 'AB'という部分文字列は最大で何個含まれますか?

解法

与えられる文字列の, 最初の文字と最後の文字のみに着目して, 4つのパターンに分類すると, 貪欲法により解くことが出来ます.

具体的には, 以下のように定めるとうまくいきます.

B~A
x~A
B~x
それ以外

この場合分けでうまくいく理屈は, 紙で実験しないと理解し辛いのですが, 以下のように説明できます.

2つの文字列を結合した際に'AB'の数を増やすためには, 1つ目の文字列の最後が'A'で 2つ目の文字列の最初が'B'である必要があります.

そして, それ以外の条件の時で, 'AB'の数が増えることは無いです.

そのため, 最後が'A', 最初が'B'であるパターンを列挙すると答えに寄与するすべての場合を列挙したことになります.

この場合分けが出来れば, 以下の貪欲法で結合することでACがもらえます.

  int ans; //自明な'AB'を既に数え上げているとする
    if(ba != 0){//「B~A」が存在するとき
        ans += (ba-1);//「B~A」は置けるだけ置く
        if(bx!=0){ //その後ろに「B~x」を繋ぐ
            ans++;
            bx--;
        }
        if(xa!=0){//手前に「x~A」を繋ぐ
            ans++;
            xa--;
        }
    }
    ans += min(xa,bx);//好きな位置に「x~AB~x」を置けるだけ置く
    cout << ans << endl;

4つのパターンの優先順位を考えた時, 「B~A」は優先的につないだ方が良さそうなので, 繋ぎます.

このとき, 「B~A」の後ろに「B~x」をつなぐとスコアが1稼げるので, 繋ぎます.

また, 「B~A」の手前に「x~A」をつないでもスコアが1稼げるので, 繋ぎます.

あとは好きな位置に「x~A」と「B~x」を繋いだ文字列を設置します.

以上です.