Arc's blog

競プロなど

AtCoder Grand Contest(AGC) 021 レビュー

大爆死

と思ってたらなんとか生きてた

今回はAtCoder Grand Contest(AGC) 021のレビューです。

問題はこちらのAtCoder公式からどうぞ。

A - Digit Sum 2

N以下の任意の値のうち、「各桁の数の和」が最大になるような値を見つけて、その値の「各桁の数の和」を出力する問題。

Nより大きくならないように、できるだけ9で桁を埋めていきたい。

下処理

まず、Nを、桁ごとに配列digit[]に入れる処理をしてみる。

ついでに桁数を表す変数lengthも用意したい。

とりあえず書いてみる

こんなコードを書いてみた。

int length;

long long power(int exp){//10^expを返す
    long long num=1;
    for(int i=0;i<exp;i++){
        num*=10;
    }
    return num;
}

int digitinput(void){
    int i=1;
    int remain;
    while(N>0){
        remain=N%power(i);
        N-=remain;
        digit[i]=remain/power(i-1);
        i++;
    }

    length=i-1;
}

こんな感じで、digit[1]length桁目、digit[2]length-1桁目、という風に値が入る。

しかし。

バグ発生

このコードを書いて、実際に数個のケースでACできることを確認したのだが、実行時にNの桁数が多くなるとFloating point exception: 8と表示されてしまう。

その名の通り浮動小数点周りのエラーみたいだが、原因特定できず。

しゃーない、別のコード書くか。

無理やり突破
void digitinput(void){
    length=SN.length();
    for(int i=1;i<=length;i++){
        digit[i]=SN[length-i]-48;
    }
}

なにをしたかお分かりだろうか……?

stringコンテナのSNに入力を突っ込んで、各桁のASCIIコードをdigit[i]に入れたあとに-48して数値化するクソコードを書いた。

ACできれば何でも良いんだもんっ

ようやく本処理

int solve_sum(int i){
    int sum=0;
    if(digit[i]==0){
        return 0;
    }else{
        int target;
        for(int target=length;target>i;target--){
            sum+=digit[target];
        }
        sum+=digit[i]-1;
        for(int target=i-1;target>=1;target--){
            sum+=9;
        }
    }
    return sum;
    
}

int solve(void){
    int max=0;
    int tempans;

    //maxを初期化
    for(int i=length;i>=1;i--){
        max+=digit[i];
    }

    for(int i=length;i>=2;i--){
        tempans=solve_sum(i);
        if(max<tempans){
            max=tempans;
        }
    }

    return max;
}

何をしているのか具体例で説明する。N=9876と仮定する。length=4である。

まず、max=9+8+7+6=30で初期化。

そのあと、「最高桁>i桁」まではdigit[]の値をそのままsumに加算。

i桁目ではdigit[i]-1を加算。ここでdigit[i]-1が負の値を取る場合は計算しない。

「i-1桁>=1桁」までは9を加算。

こうして計算されたsumを、iを減らしつつ全て試して最大値を出力する。

i=4 sum=8+9+9+9
i=3 sum=9+7+9+9
i=2 sum=9+8+6+9
i=1 sum=9+8+7+6

こんな感じでNを超えないように全探索してみた。

まだまだ計算量削れるかもしれない。43分かけてAC。

これ以降

わからん

まとめ

A問題早解きコンテストでしたが、実装に時間取られて死にました。

と思いきや

緑レート達成したぜ。やったね。