AtCoder Grand Contest 020 D - Min Max Repetition

問題概要

整数

• 長さは
• 
• 上記2条件を満たす文字列中で，同じ文字のみからなる部分文字列のうち最長のものの長さが最も短い．
• 上記3条件を満たす文字列中で辞書順最小である．

解法概要

"同じ文字が続いても良い数"

1. ABB…B(Bがk個) ABB…B ABB…B…のprefix
2. AA…A(Aがk個)BAA…ABAA…AB…のpostfix

をくっつける．1.と2.の境目は二分探索で求める．

実装上の学び

最初はstd::stringで文字列を結合したり出力したりするのをやっていたが，解説の解法を実装してもTLE． ACした人のソースコードを参考にchar型の配列で文字列を扱うようにしたところTLEが取れ，その後多少の修正をして無事AC． 2000ms以上かかっていた実行時間が3ms程度に． stringに比べてcharの方が定数倍が軽いとは漠然と思っていたけどまさかこれほどまでとは……．

(追記)

このTLE，std::stringの部分文字列をsubstr()で取得していたことが原因でした． substr()の時間計算量は部分文字列の長さですが，これを

substr()を用いないAC実装例: Submission #1997664 - AtCoder Grand Contest 020

(追記の追記)

"substr()の時間計算量は部分文字列の長さ

TLE実装例: Submission #1998007 - AtCoder Grand Contest 020

ソースコード

#include<cstdio>
#include<cstdlib>
#include<algorithm>

using namespace std;

int main(){
    int q,a,b,c,d;
    scanf("%d", &q);
    for(int i=0;i<q;i++){
        scanf("%d %d %d %d", &a, &b, &c, &d);
        int n = a+b, aa, bb, l = max((a+b) / (b+1), (b+a) / (a+1));

        int ok = 0, ng = a+b+1;
        while(ng-ok > 1){
            int mid = (ok+ng)/2;
            aa = a - mid/(l+1)*l - mid%(l+1);
            bb = b - mid/(l+1);
            
            if((long long)bb < (long long)(aa+1)*(long long)l){
                ok = mid;
            }else{
                ng = mid;
            }
        }

        if(c <= ok){
            for(int j=c-1;j<min(d,ok);j++){
                putchar((j % (l+1) == l)?'B':'A');
            }
        }
        if(ng <= d){
            for(int j=max(ok,c-1);j<min(n,d);j++){
                putchar(((n-j) % (l+1) == 0)?'A':'B');
            }
        }
        puts("");
    }
}

感想

1100点問題初AC．考察が面白い問題だった．

(追記)

不正確な記述&度重なる加筆修正申し訳ありませんでした．

プロの皆さんのおかげでかなり勉強になりました．