Arc's Laboratory

プログラミングとかの研究室

AtCoder Beginner Contest (ABC) 106 を解いてみた

AtCoder Beginner Contest (ABC) 106 の解法ログです。

問題文はAtCoder公式からどうぞ。

注:ソースコードの変数と解法中の文字は無関係です

A - Garden

解法

算数の問題にこういうのありましたね。道の重なりに注意。

ソースコード

int main(void) {
    int a, b;
    cin >> a >> b;
    cout << a * b - a - b + 1 << endl;

    return 0;
}

B - 105

解法

Nが小さいので、N以下の数で割ったあまりを全て見ていけばOK。

余り0になる場合が8つあるなら、その数は約数を8個持つ。

ソースコード

int main(void) {
    int n;
    cin >> n;
    int result = 0;
    for (int i = 1; i <= n; i += 2) {
        int count = 0;
        for (int j = 1; j <= i; j++) {
            if (i % j == 0)
                count++;
        }
        if (count == 8)
            result++;
    }

    cout << result << endl;

    return 0;
}

C - To Infinity

解法

1<=n<=K文字目に1以外の文字が存在する場合、5000兆日経つと、たとえK=10^18でも1以外の文字がKの場所に到達する(指数関数は一瞬で膨れ上がるので)。

そうでない場合は5000兆日経ってもK文字目は1のまま。

K文字目まで1が続くのなら1を、そうでないなら最初に出現した1以外の文字を出力する。

ソースコード

int main(void) {
    std::string s;
    int64_t k;
    cin >> s;
    cin >> k;
    for (int i = 0; i < k; i++) {
        if (s[i] != '1') {
            cout << s[i] << endl;
            return 0;
        }
    }
    cout << '1' << endl;

    return 0;
}

D - AtCoder Express 2

解法

愚直に解く場合、『クエリ(p,q)に対して、「全列車に対しp<=L,R<=qであるかを調べる」』という解法を思いつける。計算量はO(Q*M)なので間に合わない。

都市の数が少ないことに着目すると、train[L][R]=LからRに向かう電車の数という配列を作ることができそう。この配列を利用して「p<=L,R<=qを満たす場所を足していく」という解法を思いつける。計算量はO(QN^2)。……計算量増えてるじゃーん!!

しかし、「p<=L,R<=qを満たす場所を足していく」処理は累積和を利用することでO(N)に落とせる。ということで、先程の配列から累積和を作ってクエリに答えればAC。

ソースコード

(printf/scanfで書いてます)

int main(void) {

    int n, m, q;
    cin >> n >> m >> q;
    int train[501][501] = {};
    int cum[501][501]   = {};

    int m1, m2;
    for (int i = 0; i < m; i++) {
        scanf("%d%d", &m1, &m2);
        train[m1][m2]++;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cum[i][j] = cum[i][j - 1] + train[i][j];
        }
    }

    int a, b;
    int answer;
    for (int i = 0; i < q; i++) {
        answer = 0;
        scanf("%d%d", &a, &b);
        for (int j = a; j <= b; j++) {
            answer += cum[j][b];
        }
        printf("%d\n", answer);
    }

    return 0;
}

その他

37分全完やったぜ。

AtCoder Beginner Contest (ABC) 105を解いてみた

AtCoder Beginner Contest (ABC) 105の解法をまとめてみます。今回はD問題が詳しめです。

問題文はAtCoder公式からどうぞ。

注:ソースコードの変数と解法中の文字は無関係です

A - AtCoder Crackers

解法

なるべく公平に配るなら、

  • N%K==0のとき 差は0
  • N%K!=0のとき 差は1

になる。

ソースコード

int main(void) {
    int n,k;
    cin>>n>>k;
    if(n%k==0){
        cout<<"0"<<endl;
    }else{
        cout<<"1"<<endl;
    }
 
    return 0;
}

B - Cakes and Donuts

解法

7ドルのドーナツを買う→残額が4で割り切れるならtrue、割り切れないならドーナツをもう一つ→……というふうにやっていく。

一応4ドルのケーキを買った後で判定する処理も書いたけど無駄だった。

ところでArcとかいう人はこの問題で2WAも出しているそうですよ。酷いですね。

ソースコード

int main(void) {
    int n;
    cin >> n;
    bool can_buy = false;
    if (n % 7 == 0 || n % 4 == 0) {
        can_buy = true;
    } else {
        for (int i = 0; i <= n; i += 7) {
            if ((n - i) % 4 == 0) {
                can_buy = true;
                break;
            }
        }
        for (int i = 0; i <= n; i += 4) {
            if ((n - i) % 7 == 0) {
                can_buy = true;
                break;
            }
        }
    }
 
    if (can_buy)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
 
    return 0;
}

C - Base -2 Number

解法

10進数nを普通の2進数に変換する際の処理を考えてみると、

nが0になるまで{

(a-1ビットで表現できる最大の数)<nを満たすような最大のaを探す
2進数a桁目にフラグを立てる
n-=2^(a-1)

}を繰り返す

と言う風になる。これを応用して、

nが0になるまで{

n<(a-1ビットで表現できる最小の数)か(a-1ビットで表現できる最大の数)<nを満たすような最大のaを探す
-2進数a桁目にフラグを立てる
n-=(-2)^(a-1)

}を繰り返す

という処理を作ってみる。

ソースコード

const long long MAX_N = 1000000000;
const long long MIN_N = -1000000000;
 
int main(void) {
    int n;
    cin >> n;
    if (n == 0) {
        cout << 0 << endl;
        return 0;
    }
 
    bool is_on[101] = {};
    std::vector<long long> max;
    std::vector<long long> min;
 
    // max,minを計算
    //max[a]=(aBitで表現できる最大値)
    max.push_back(0);
    min.push_back(0);
    long long add = 1;
    int count     = 0;
    while (1) {
        count++;
        if (count % 2 == 1) {
            max.push_back(max[count - 1] + add);
            min.push_back(min[count - 1]);
        } else {
            max.push_back(max[count - 1]);
            min.push_back(min[count - 1] + add);
        }
        if (max[count] >= MAX_N && min[count] <= MIN_N)
            break;
        add *= -2;
    }
 
    int top_digit = 0;
    while (n != 0) {
        if (n > 0) {
            int digit = 1;
            while (max[digit] < n) {
                digit++;
            }
            is_on[digit] = true;
            if (top_digit == 0)
                top_digit = digit;
            n -= std::pow(-2, digit - 1);
        } else {
            int digit = 1;
            while (min[digit] > n) {
                digit++;
            }
            is_on[digit] = true;
            if (top_digit == 0)
                top_digit = digit;
            n -= std::pow(-2, digit - 1);
        }
    }
 
 
    for (int i = top_digit; i >= 1; i--) {
        if (is_on[i])
            cout << 1;
        else
            cout << 0;
    }
    cout << endl;
 
    return 0;
}

D - Candy Distribution

解法

累積和を計算した後、累積和のそれぞれの項に対してMで割った余りを計算。 Mで割った余りがiであるような項がn個あるなら、それらの項から2つを選択すると条件を満たす和が得られる。個数はn C 2。これをそれぞれのiに対して計算することで答えが得られる。

実装

実装がきつかったので詳しめに書いてみる。

「余りがiであるような項の個数」をどう保持するか?

余りのパターンはM通り存在するから、配列を用意するとメモリが足りない。

公式PDFにもある通り、std::map系のコンテナを利用することになる。今回の実装はstd::multimapを利用している。キーを余り、値を累積和の項にして、count(i)で個数を取得する作戦。なおmap系を利用するのは今回が初めてな模様。

イテレータを最初から最後まで回して、前に見たキーと別のキーが出現したら計算用関数を呼び出す事にした(キーが順番通りに出現する必要があるのでunordered_multimapは使えない)。

unorderedの実装ってどうやるんでしょうね……。

組み合わせの数n C 2をどう計算するか?

ソースコードコメントアウトした関数のように、階乗を利用して計算するとlong longでもオーバーフローしてREを吐く。階乗をなめたらいけない。

結局「n!を少しずつ計算→途中で(n-2)!か2!の因数で約分できそうだったら約分」というクッッッッソ醜いやり方で押し通した。

……と、ここまで書いたが実は全て罠n C 2なら普通に(n-1)+(n-2)+...+2+1を計算するだけで済む。

これに気づいたのはACした後の話でしたとさ。

コンパイラによって異なる言語実装

GCC5.4.1、ローカル環境のClang(clang-902.0.39.2)だと、ローカル変数宣言時に自動で0初期化が行われる。

Clang 3.8.0だと初期化が行われないらしく、結果「ClangでコンパイルするとWAになる」という現象が発生していた。

とりあえず明示的にint hoge=0としておいた方が精神衛生上よろしいかも。

ソースコード

/*
long long factorial(long long n) {
    long long result = 1;
    for (long long i = 1; i <= n; i++) {
        result *= i;
    }
    return result;
}
 
long long combination(long long n, long long r) {
    long long result = factorial(n) / factorial(n - r) / factorial(r);
    return result;
}
*/
 
long long combination_improved(long long n, long long r) {
    long long d      = n - r;
    long long result = 1;
    while (n > 1 || d > 1 || r > 1) {
        if (n > 1) {
            result *= n;
            n--;
        }
        if (d > 1 && result % d == 0) {
            result /= d;
            d--;
        }
        if (r > 1 && result % r == 0) {
            result /= r;
            r--;
        }
    }
    return result;
}
 
int main(void) {
    long long n, m;
    long long count;//Clangだと初期化の必要あり
    long long cum[100001];
    std::multimap<long long, long long> mod_map; //(mod M,number)
    cin >> n >> m;
    long long m1;
    for (int i = 0; i < n; i++) {
        cin >> m1;
        if (i == 0)
            cum[i] = m1;
        else
            cum[i] = cum[i - 1] + m1;
    }
    for (int i = 0; i < n; i++) {
        mod_map.insert(std::make_pair(cum[i] % m, cum[i]));
    }
 
    int prev = m;
    for (auto itr : mod_map) {
        if (prev != itr.first) {
            if (itr.first == 0) {
                if (mod_map.count(0) >= 1)
                    count += combination_improved(mod_map.count(0) + 1, 2);
            } else {
                if (mod_map.count(itr.first) >= 2) {
                    count += combination_improved(mod_map.count(itr.first), 2);
                }
            }
        }
        prev = itr.first;
    }
 
    cout << count << endl;
 
    return 0;
}

おまけ

散っていったコードに敬意を。(?????)

Mujin Programming Challenge 2018 を解いてみた

無人コン(参加者800人以上)の解法メモです。

問題文はAtCoder公式からどうぞ。

注:ソースコードの文字と解法中の文字は無関係です

A - コンテスト名

文字列MUJINSを比較するだけ。

ソースコード

int main(void) {
    std::string s;
    std::string ans;
    cin >> s;
    ans = "MUJIN";
    for (int i = 0; i < 5; i++) {
        if (ans[i] != s[i]) {
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;

    return 0;
}

B - セキュリティ

一文字ずつ読んでシミュレート、0になったらYesを返して即return 0

一番最初に0人だった(A==0)場合もYesになることに注意。

ソースコード

int main(void) {
    cout << std::fixed << std::setprecision(10);
    int a;
    cin >> a;
    std::string s;
    cin >> s;

    if (a == 0) {
        cout << "Yes" << endl;
        return 0;
    }

    for (int i = 0; i < (int)s.size(); i++) {
        if (s[i] == '+') {
            a++;
        } else {
            a--;
        }
        if (a == 0) {
            cout << "Yes" << endl;
            return 0;
        }
    }
    cout << "No" << endl;

    return 0;
}

C - 右折

解けてないです><

あるマスで右折するルートの総数は、

左、上、右、下に(そのマスを除いて).がa,b,c,d個並んでいた場合a*d+b*a+c*b+d*c=(a+c)*(b+d)で求められる

このことを利用していけばO(NM)で解けるはずです(通らないよぅ……)。

D - うほょじご

解法

準備

数の組に対して、

enum status { ns = 0, wj, wa, ac };
//ns(No Submission)は未確認
//wj(Waiting for Judging)は確認中
//wa(Wrong Answer)は無限回操作ができないと確定
//ac(Accepted)は無限回操作ができると確定

を定義する。

status grid[x][y]=(x,y)のstatusとしておく。

初期状態では(0,n)(n,0)(nは任意の整数)のみwa、その他はns

探索

あるnsの数の組(x,y)に対して、とりあえず一回操作をしてみる。

操作後の数の組(a,b)の状態によって、以下のことを行う。

grid[a][b]==nsの場合

grid[a][b]=wjとして、さらにstd::vector<std::pair<int, int>> vecに数の組をpush_back()しておく(後で役に立つ)。 vecは「探索中に通過したwjの状態の記録」として考えてください。

その後、(a,b)をもう一度操作。

grid[a][b]==waの場合

waになっている組になったら、その数の組が向かう先は(0,n)(n,0)しかない。

探索中に通った数の組についても同じことが言える。

vecに保存しておいたすべての数の組(s,t)に対して、grid[a][b]=waにする。(vecに保存しないでgrid[][]を全探索すると時間が掛かるが、vecに保存すると計算量を落とせる)

grid[a][b]==ac、grid[a][b]==wjの場合

探索中にwjにたどり着いた場合、以降は無限回操作ができる。

また、無限回操作ができると確定した状態にたどり着いた場合、無限回操作ができる(それはそう)。

探索中に通った数の組は無限回操作が可能、と言えるので、vecに保存しておいたすべての数の組(s,t)に対して、grid[a][b]=acにする。

仕上げ

あとはgrid[x][y]==acになっている場所を数えて終了。

ソースコード

void dp_search()となっていますが、DPと言えるかは人それぞれだと思います。

enum status { ns = 0, wj, wa, ac };

int n, m;
status grid[1000][1000];

int rev(int x) {
    int a, b, c;
    int reverse;
    if (x >= 100) {
        a = x / 100;
        x -= a * 100;
        b = x / 10;
        x -= b * 10;
        c = x;
        reverse = c * 100 + b * 10 + a;
    } else if (x <= 9) {
        reverse = x;
    } else {
        b = x / 10;
        x -= b * 10;
        c = x;
        reverse = c * 10 + b;
    }
    return reverse;
}

void dp_search(int x, int y, std::vector<std::pair<int, int>> vec) {
    if (grid[x][y] == wa) {
        //終了措置
        for (int i = 0; i < vec.size(); i++) {
            int a = vec[i].first;
            int b = vec[i].second;
            grid[a][b] = wa;
        }

    } else if (grid[x][y] == ac || grid[x][y] == wj) {
        //成功措置
        grid[x][y] = ac;
        for (int i = 0; i < vec.size(); i++) {
            int a = vec[i].first;
            int b = vec[i].second;
            grid[a][b] = ac;
        }
        return;
    } else {
        grid[x][y] = wj;
        if (x < y)
            x = rev(x);
        else
            y = rev(y);
        if (x < y)
            y -= x;
        else
            x -= y;
        vec.push_back(std::make_pair(x, y));
        dp_search(x, y, vec);
        return;
    }
}

int main(void) {
    cout << std::fixed << std::setprecision(10);
    cin >> n >> m;

    for (int i = 0; i <= 999; i++) {
        for (int j = 0; j <= 999; j++) {
            grid[i][j] = ns;
        }
    }
    for (int i = 0; i <= 999; i++) {
        grid[0][i] = wa;
        grid[i][0] = wa;
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (grid[i][j] == ns) {
                std::vector<std::pair<int, int>> vec;
                vec.push_back(std::make_pair(i, j));
                dp_search(i, j, vec);
            }
        }
    }

    int answer = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (grid[i][j] == ac) {
                answer++;
            }
        }
    }
    cout << answer << endl;
    return 0;
}

これ以降

やってません

まとめ

時間内では2完でした。

腕、落ちてないか?? 青になれるのか???

ABC072/ARC082を解いたので記録を残す

だいぶ昔のやつですが、ABC072/ARC082のA~D問題を解いたので記録を残します。

問題文はAtCoder公式からどうぞ。

A - Sandglass2

ans=x-tをして、ans>=0だったらそのまま出力。それ以外だったら0を出力。

int main(void)
{
    int x, t;
    cin >> x >> t;
    int answer = x - t > 0 ? x - t : 0;
    cout << answer << endl;
 
    return 0;
}

B - OddString

一文字飛ばしで文字を足していく。実装ゲー。

int main(void)
{
    std::string s;
    std::string answer;
    cin >> s;
    for (int i = 1; i <= (int)s.size(); i++)
    {
        if (i % 2 == 1)
        {
            answer += s[i - 1];
        }
    }
    cout << answer << endl;
 
    return 0;
}

C - Together

{\displaystyle a_i}{\displaystyle a_i-1}{\displaystyle a_i}{\displaystyle a_i+1}になれる。

{\displaystyle x}に対して、count[x-1]++; count[x]++; count[x+1]++;をしていった後、どのcount[]が最大の値かを調べればOK。

イメージとしては「長さnの直線上に積み木を3つずつ積んでいく」感じ。一番高く積み上がった場所が答え。

int main(void)
{
    int n;
    int count[100000] = {};
 
    cin >> n;
    int m1;
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &m1);
        count[m1]++;
        if (m1 - 1 >= 0)
            count[m1 - 1]++;
        if (m1 + 1 < 100000)
            count[m1 + 1]++;
    }
 
    int max = 0;
    for (int i = 0; i < 100000; i++)
    {
        if (count[i] > max)
            max = count[i];
    }
 
    cout << max << endl;
 
    return 0;
}

D - Derangement

{\displaystyle p_i\neq i}である所をt,そうでない所をfとする。

ffとなっている所をスワップするとttにできる。

また、ftとなっている所をスワップしてもttにできる(数は1つずつしかないため、スワップ後にtがfになってしまうことはない)。

貪欲的に「fが見つかったら右隣とスワップして、さらに右隣の場所から検索を再開する」という操作をしていけばいい(自分のソースコードだと無駄な処理をしています)。

int main(void)
{
    int n;
    int answer = 0;
    int m1;
    std::vector<int> number;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &m1);
        number.push_back(m1);
    }
 
    for (int i = 0; i <= n; i++)
    {
        if (number[i] == i + 1)
        {
            if (i + 1 < n && number[i + 1] == i + 2)
            {
                answer++;
                i++;
            }
            else
            {
                answer++;
            }
        }
    }
 
    cout << answer << endl;
 
    return 0;
}

AtCoder Beginner Contest (ABC) 090 / AtCoder Regular Contest (ARC) 091 レビュー

AtCoder Beginner Contest (ABC) 090 / AtCoder Regular Contest (ARC) 091 の個人的解法解説とレビューです。

今回はABC/ARCのC問題&D問題のみとなります。

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

C - Flip,Flip, and Flip......

とりあえず解いてみる

最大のカード枚数は10^18。全部シミュレートしてると間に合わない。

実際に操作してみる。

カードの置かれているマスの四隅は4回操作される。最終的には表になる。

カードの置かれているマスの辺上(四隅を除く)は6回操作される。最終的には表になりる。

その他のマスは9回操作される。最終的には裏になる。

ということで、カードの枚数-辺上(四隅含む)にあるカードの枚数、つまりN*M-(2*N+2*M-4)を出力すれば良さげ。

……ほんとかな?

カード1枚だけ、つまりN=1 && M=1の状況だとどうなるだろうか。「四隅」「辺」が定義されないので、答えが変わってきそうな気がする。同様に、N=1 && M≠1の場合も「四隅」が定義されないのでマズそう。

コーナーケースがありそうなので、順に調べていく。

N=1 && M=1 のとき(「四隅」「辺」の定義が不可能)

1回操作されるので、1枚だけ裏になる。上記の式に当てはめてみると……そのまま使えそう。

N=1 || M≠1 のとき(「四隅」の定義が不可能)

端の2枚は2回操作される。最終的には表。

その他は3回操作される。最終的には裏。

つまり、M-2を出力すれば良い。上の式に当てはめてみると……1*M-(2*1+2*M-4)=-M+2になってしまう。

修正する

コーナーケースがあるので、以下のように修正。

if(N==1 && M!=1){ //コーナーケース
    cout<<M-2<<endl;
}else{
    cout<<N*M-2*N-2*M+$<<endl;
}

自分のソースコードだと無駄な条件分岐が……。

こんな感じで解けた。計算量はO(1)

D - Remainder Reminder

ソースコードこちら

とりあえず解いてみる

愚直解は「1<=a,b<=Nを満たす組(a,b)に対して、a%b>=Kであるかを確かめる」と言った感じだろうか。計算量はO(N^2)。Nは最大10^5なので間に合わない。

せめてO(N)ぐらいには落としたいところ。ということで、「組の一方の値が与えられたとき 、有り得るもう一方の値の個数をO(1)で求める」アルゴリズムを作ってみる(これなら、「与える一方の値」を1からNまで動かして和を取ることでO(1*N)で解ける)。

計算量を削っていこう

bを「与える」と上手く行ったので解説。

f:id:arcslab:20180312160947p:plain
ARC091-D_解説

表は、N=10の設定で「aをbで割った余り」を示している。余りがK=2以上のところには色が塗ってある。

値には、長さbの周期が見られることが分かる(表の赤線を参照)。

また、b>Kを満たすbについてのみ考えれば良いことが分かる。

表の中で「周期」がいくつ見られるかを「sequence」に記載した。この値はマス数/周期の長さ、すなわち(1+N)/bで求められる。

「周期」に含まれるマスの中で、余りがK以上のマスがいくつ有るかを「sequenceによるanswer」とした。この値はsequenceの値*一周期に存在する余りK以上のマスの数、すなわちsequence*(b-K)で求められる。

また、「周期」に含まれないマスの中で、余りがK以上のマスがいくつ有るかを「remain」とした。この値は周期に含まれないマスの数-K、すなわち(1+N-sequence*b)-Kで求められる(負数になることがあるので、その場合は0扱い)。

以上の計算をすることで、「bの値が与えられたとき 、有り得るaの値の個数をO(1)で求める」ことができた。bをK+1からNまで動かして和をとれば、O(N)で解ける。

K=0のときがコーナーケース。この場合はN*Nを出力しておく。

まとめ

考察回&コーナーケース回避回だったなぁという印象。1WA吐きましたが、50分で二問解けました。

最大パフォ更新。最近は調子がいい。

AtCoder Beginner Contest (ABC) 089 レビュー

今回は良かったぞ。

AtCoder Beginner Contest (ABC) 089の個人的解法解説とレビューです。

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

A - Grouping 2

ソースコード

最大化問題。できるだけ3人グループを作っていきたい。

3人グループの数はN/3で求められる。

ここでちょっと考えると、N-N/3の答えは1か2。この余りをどっかのグループに押し込んでしまえばいい。

よって、N/3を出力すればいい。main関数がたったの4行だった。

B - Hina Arare

ソースコード

P W Gのひなあられが存在することが保証されている。

つまり、Yが存在すればFour、存在しなければThreeを出力すればいい。

C - March

ソースコード

名前の先頭の文字しか使わないので、残りの情報は切り捨てる。

名前がMで始まる人の数をtop[0]、Aで始まる人の数をtop[1]……とする。

「M,A,R」で始まる3人を選んだと仮定する。この場合の組み合わせ数はtop[0]*top[1]*top[2]で求められる。

うまくループを回して、全ての仮定パターン(5 C 3=10通り)の組み合わせの和を求める。

long longを使わないとバグることに注意(1WAした)。

D - Practical Skill Test

ソースコード

計算量はO(Q)O(H*W)ぐらいだと予測。

なんとかして、キューに対してO(1)で答えられるようにしたい 。

最初はdp[i][j]=iからjまでのコストという形でメモ化再帰しようとしたが、O{(H*W)2}かかるので断念。そもそもメモリ確保ができない。

いろいろ考えてたら累積和を使う方法が降ってきた。

rui[i]={i%D(i%D!=0の場合),D(i%D==0の場合)}の場所からiの場所までのコストと定義。

すると、D<iを満たすiに対して、 rui[i]=rui[i-D]+(i-Dの場所からiの場所までのコスト)と計算できる。

キューに対しては、rui[r]-rui[l]を出力する。

計算量はO(H*W+Q)。

まとめ

D問題でだいぶ止まってたんですが、なんとか解けました。

計算量の削減目標を持って考えるの、大事だと思います。

結果はこんな感じ。

最高の成績でした(`・ω・´)

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問題早解きコンテストでしたが、実装に時間取られて死にました。

と思いきや

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