diverta 2019 Programming Contest A~E
コンテストに遅刻したので戒めに解きました。
問題文 Tasks - diverta 2019 Programming Contest
A
N-K+1を出力すればいいです.
B
問題
整数R,G,B,Nが与えられたとき, 以下を満たす(r,g,b)の組はいくつあるか?
ただし, R,G,B,Nはそれぞれ1以上3000以下.
解法
rとgが決まると上式よりbが一意に定まる.
このことから, rとgに関して二重forを回すとO(N2)となって間に合う.
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」を繋いだ文字列を設置します.
以上です.
D
問題
正の整数Nが与えられます.
Nについて以下の条件を満たす全ての正の整数mの総和を求めてください
- Nをmで割った商とあまりが等しい
解法
N=8の時を実験してみましょう.
商が1の時, 2の時, 3の時を考えると, mに関して以下の方程式が成り立つことが分かります.
以上の観察から, 商がxの時, Nとmに関して以下の方程式が成り立ちます.
上式をmについて解くと, 以下を得ます.
この結果から, mが整数となるためには, xがNの約数でないといけないことが分かります.
Nの約数列挙はで出来るので, すべての約数の列挙が時間内に可能です.
E
問題
解法
考察1
与えられた数列に対して番目の要素まで累積XOR和を取ったときの値を, として定義します.
ここで, がある値を取ったとすると, 最適に分割された数列のXOR和はとなっています.
(そうでないと, 全ての要素のXORの値がになりません!) (入力例2で試すと良いと思います)
よって, について, を決めたときと交互に取るような方法が何通りあるか求めれば良いです.
これはDPを使うとO(N)で解けます.
考察2
一方, が0の場合では, の決め方が最大で通りもあるため, 先ほどのDPを適用するとO(n2)となってしまい, うまくいきません.
そこで, を決め打った時, 最大でどれだけ高速に計算が行えるか考えます.
今, 以下のようなn=25の数列に対する累積和列が存在するとします(これは入力例4です).
- 1 3 6 5 6 0 1 0 8 0 0 3 0 4 2 4 0 0 7 5 0 4 2 0
と決め打って実験していきます.
まず, に現れる4と0以外の要素には興味が無いため, 除去します.
- 0 0 0 0 0 4 4 0 0 0 4 0
また, 4や0が連続する部分はDPで計算を省略できるので, 圧縮します.
- (0,5) (4,2) (0,3) (4,1) (0,1)
以上の操作により, 5要素に圧縮することが出来ました.
また, このような圧縮を行った時の要素数は, 中のの出現数に依存します.
よって, この5要素に対して先ほどのDPを適用するとを決め打ったとき, O(中のの出現数)で計算が可能です.
さらに, 先ほど示した圧縮は0が出現する位置についての累積和を用いると, 同様にO(中のの出現数)で計算が可能です.
あとはを全ての場合について計算してやると,
となり, 解けます.