AGC 004に参加しました

昨日の夜AGCに参加していました。
AのみACと惨敗でした。しかもAはlong long つけ忘れて一回WAしました。
B問題についてメモしておきます。解説見たらスッとわかりました。

agc004.contest.atcoder.jp

n色のスライムがいます。高橋君は全色のスライムを飼いたいです。高橋君は以下の二つの操作を行えます。

• i番目の色のスライムを一匹捕まえて飼う。このときa[i]時間かかる。

• 魔法を唱えて、今飼っているスライムの色をひとつ後ろにずらす。つまりi番目の色のスライムがi + 1番目の色のスライムになる。ただしn番目の色のスライムは1番目の色のスライムになる。このときx時間かかる。

このとき、全色のスライムを飼うのに最短で何時間かかるか求めなさい、という問題です。

回答はこんな感じです。

    #include <cstdio>
    #include <iostream>
    #include <cmath>
    #include <cstring> 
    #include <sstream>
    #include <iostream>
    #include <algorithm>
    #include <cstdlib>
    #include <map>
    #include <queue>
    #include <utility>
    #include <vector>
    #include <set>
    #include <memory.h>
    #include <iomanip>
    #include <bitset>
    #include <list>
    #include <stack>
     
    using namespace std;
     
    #define pai 3.14159265359
    #define mod 1000000007
     
    long long int b[2001][2001];
     
    int main()
    {
        long long int n, x;
        cin >> n >> x;
        long long int a[2001];
        for(int i = 1; i <= n; i++){
            cin >> a[i];
        }
        for(int i = 1; i <= n; i++){
            b[i][0] = a[i];
        }
        for(int i = 1; i <= n; i++){
            for(int j = 1; j < n; j++){
                int moto = i - j;
                if(moto < 1) moto += n;
                b[i][j] = min(b[i][j - 1], a[moto]);
            }
        }
        // b[i][j]は魔法j回以下つかったときにスライムiを得るためのスライムを捕まえるのにかかる最短時間
        long long int ans = (long long int)pow(mod, 2);
        for(int i = 0; i < n; i++){
            // iは魔法を使う回数
            long long int result = x * i;
            for(int j = 1; j <= n; j++){
                result += b[j][i];
            }
            ans = min(ans, result);
        }
        cout << ans << endl;
        return 0;
    }

全体で魔法を使う回数をk回としたとき、i番目のスライムを得る最短時間は、{a[i], a[i - 1], ... a[i - k]}の最小値になります。たとえば、a[i - j]が最小値であるとします。i - j番目のスライムは魔法をj回使うとi番目のスライムになります。したがって、魔法をk - j回使ったのちにi - j番目のスライムを捕まえ、その後j回魔法を使えばいいわけです。スライムを捕まえる行為と魔法を唱える行為の順番はどうでもいいので、このように考えることができます。
コメント通り、b[i][j]は魔法j回以下つかったときにスライムiを得るためのスライムを捕まえるのにかかる最短時間になります。motoというのが捕まえるべきスライムの番号になっています。
あとは魔法を使う回数を固定、そのときの最短時間を求め、さらにそのうちの最小値を求めれば答えが出ます。

bの大きさは2000 * 2000ということで、main内で宣言するとセグフォ起こすんですよね…問題を解くときにセグフォを起こすような配列は使わなくてもいいはずだ、と思い込んでいたのでこの方法を思いつけませんでした…今度から気をつけたいです。