2017-02-05

AtCoder Grand Contest 010 B: Boxes

AtCoder 要考察

AGC010 の B 問題。本番解けなかったけどこれは良問だとおもう。

問題概要

原文 → B: Boxes - AtCoder Grand Contest 010 | AtCoder

$N$ 個の箱が環状に並んでおり、 $i$ 番目の箱に入っている石の数は $a_i$ 個である。

この環状に並ぶ箱に対して、ある箱を選んでそれを $i$ 番目としたとき、 $1$ から $N$ の各 $j$ に対して、 $(i+j)$ 番目の箱から石をちょうど $j$ 個取り除く、という操作が行える。ただし、 $N+k$ 番目の箱は $k$ 番目と同一視するものとする。

この操作を繰り返して全ての石を取り除くことができるかを求めよ。ただし各操作において、取り除きたい個数の石がない箱があるときは、その操作を行えないものとする。

解説

箱の数を $n$ とおくことにします。

まず、この操作を $1$ 回行った時の重要な性質をいくつか見ていきます。

$1$ 回の操作で $\frac{n(n+1)}{2}$ 個の石が取り除かれる
$i$ 番目の箱に入っている石の数の変化量を $h_i$ とおくと、隣接 $2$ 項間の $h$ の差分の和 $\sum_{i=1}^N (h_{i-1} - h_i)$ は $0$ になる

前者は問題文より明らかです。後者は、差分が $-1$ の箇所が $(n-1)$ 個あり、差分が $(n-1)$ の部分が $1$ 個あるため、結果的に差分の和は $0$ になります。

したがって、操作が $k$ 回行われた場合、 $k \times \frac{n(n+1)}{2}$ 個の石が取り除かれ、上述の差分の和は $0$ であることがわかります。特に前者は非常に重要で、これを言い換えると、与えられた数列の項の総和から操作回数を計算できると言えます。

これで数列全体に対する操作の回数はわかりましたので、あとは「どの箱から何回操作を行ったか」の情報がわかれば解けます。以降、数列全体に対する操作の回数を $z$ とします。

$i$ 番目の箱から操作を行う数を $x_i$ とし、元の数列で自分より前の項との差分、すなわち $a_{i-1} - a_i$ を $s_i$ とします。このとき、 $x_i$ はどのように表せるでしょうか？これは、次のことを用いて考えれば良いです。

$i$ 番目から操作を行う回数が $x_i$ 回 → 前の項に比べて $x_i \times (n-1)$ 減っている
$i$ 番目以外から操作を行う回数が $(z-x_i)$ 回 → 前の項に比べて $(z-x_i) \times 1$ 増えている

この事実と、 $s_i$ が「前の項からいくつ減っているか？」を表していることから、次の一次方程式を立てることができます。

$s_i = (n-1)x_i - (z-x_i)$

これを $x$ について解くと、

$x_i = \frac{s_i + z}{n}$

となります。もちろん、 $x_i$ は整数になりますので、分子 $s_i + z$ は $n$ の倍数でなければなりません。

どの箱から何回操作を行ったかの情報さえあれば、数列を構築することができます。 $1$ 番目の数列の値を $O(N)$ で構築すれば、 $2$ 番目以降は前の項の結果を用いて $O(1)$ で計算できるため、結果 $O(N)$ で構築できます。私のソースコードではこの方法で構築した数列と与えられた数列を比較して最終確認をしています。(この最終確認はしてもしなくても良いです)

ソースコード

signed main() {
    int n; cin >> n;
    int a[100010] = {};
    int sum = 0;

    rep(i,0,n) {
        cin >> a[i];
        sum += a[i];
    }

    int cs[100010] = {};
    int ret[100010] = {};
    int cntnum = 0;

    if(sum % (n * (n+1) / 2)) cout << "NO" << endl;
    else {
        cntnum = sum / (n*(n+1) / 2);
        rep(i,0,n) {
            int prev = (i - 1 + n) % n;
            int s = a[prev] - a[i];
            // n で割り切れなければ操作回数が小数になるので不適
            // 結果が負になるのも不適 (操作回数は非負整数)
            if( (s+cntnum) % n != 0 || (s + cntnum) / n < 0) {
                cout << "NO" << endl;
                return 0;
            }
            cs[i] += (s + cntnum) / n;
        }
        rep(i,0,n) ret[0] += cs[i] * ((n - i) % n + 1);
        rep(i,1,n) ret[i] = ret[i-1] - cs[i] * n + cntnum;
        rep(i,0,n) {
            if(ret[i] != a[i]) {
                cout << "NO" << endl;
                return 0;
            }
        }
        cout << "YES" << endl;
    }
    return 0;
}

この、特殊なデータ構造を理解している必要もなく、実際はループと単純な演算だけで答えが導けるっていう考察重視の感じね。さすが最強高校生が考える問題は一味違う・・・。

追記 (2018/02/24): $1$ 年越しに復習したのですが、解説と違う方針で AC しました。

$i$ 番目の山から $1$ 個、 $2$ 個・・・と取っていく操作を行う回数を $p_i$ とおきます。このとき、 $i$ 番目の山の個数と操作回数との関係は次のようになります。

$A_i = p_i + 2p_{i-1} + 3p_{i-2} + \dots + Np_{i+1}$

添字を 1 つずらします。

$A_{i+1} = p_{i+1} + 2p_i + 3p_{i-1} + \dots + Np_{i+2}$

$A_{i}$ から $A_{i+1}$ を引くと、

\begin{align} A_{i} - A_{i+1} &= (N-1)p_{i+1} - \sum_{j \neq i+1} p_j \\ &= N p_{i+1} + \sum_{j} p_{j} \end{align}

となります。これを変形すると $p_{i+1} = \frac{ A_{i} - A_{i+1} + \sum_{j} p_{j} }{N}$ となり、それぞれの操作回数を求めることができます。

あとは剰余とか負の数にならないとかそのへんを確かめればよいです。

#include <cstdio>
using namespace std;

long long int N, A[100010];
int main() {
    scanf("%lld", &N);
    long long int sum = 0, div = N*(N+1)/2;
    for(int i=0; i<N; i++) {
        scanf("%lld", &A[i]);
        sum += A[i];
    }

    bool ok = (sum % div == 0);
    long long int sum_op = sum / div;
    for(int i=0; i<N; i++) {
        long long int val = A[i] - A[(i+1)%N] + sum_op;
        ok &= (val >= 0 && val % N == 0);
    }
    printf("%s\n", ok ? "YES" : "NO");
    return 0;
}

2017-02-02

AtCoder Regular Contest 027 C: 最高のトッピングにしような

AtCoder 動的計画法

またまた DP 自力で解けた記念。

問題概要

原文 → C: 最高のトッピングにしような - AtCoder Regular Contest 027 | AtCoder

$N$ 種類のトッピングがある。トッピング $i$ は $t_i$ 枚のチケットを交換することで入手でき、その価値は $h_i$ である。

チケットにはスペシャルチケットと通常のチケットの $2$ 種類が存在し、どのトッピングにおいてもスペシャルチケット最低 $1$ 枚を含むチケットの組み合わせでなければ交換できない。

いま、スペシャルチケットを $X$ 枚、通常のチケットを $Y$ 枚持っている。トッピングの価値の合計値を最大化せよ。

解説

ナップザックの亜種、ということで動的計画法を使って解いていきます。説明のため、スペシャルチケットは ST と、通常のチケットは RT と略記します。

dp[i][j][k] := i 番目までのトッピングを使って、ST の残りが j 枚で RT の残りが k 枚である時の価値の最大値 となるように配列を用意します。

どちらの種類のチケットも十分な数あると仮定するとき、 $h_i$ 枚のチケットが必要なトッピングに対して使うチケットの組み合わせは $h_i$ 通りありますが、これを全て試していってしまうと DP の更新が $4$ 乗ループになり時間的に間に合いません。どこかを工夫して、計算量を落とせないでしょうか？

今回の場合は、ST と RT を組み合わせて $h_i$ 枚使えば良いとのことですので、使うチケットの枚数はどの組み合わせでも等しいです。さらに、いずれのトッピングも ST が最低 $1$ 枚以上必要であることも重要で、これらを考えると RT の方をなるべく多く使っていけば (ST がなるべく余るように使っていけば) 良いことがわかります。この貪欲で $3$ 乗ループになりますので間に合います。計算量は $O(XYN)$ です。

ソースコード

最初メモ化で書こうと思ったけど、意味不明なコードになったので DP で。

int x, y, n;
int t[310], h[310];
int dp[310][310][310];

signed main() {
    cin >> x >> y >> n;
    rep(i,0,n) cin >> t[i] >> h[i];
    memset(dp, 0, sizeof(dp));
    
    rep(i,0,n) repq(j,0,x) repq(k,0,y) {
        dp[i+1][j][k] = dp[i][j][k];
        if(j+k >= t[i] && j != 0) {
            int p, q;
            if(k >= t[i] - 1) {
                p = 1;
                q = t[i] - 1;
            }
            else {
                p = t[i] - k;
                q = k;
            }
            dp[i+1][j][k] = max(dp[i+1][j][k], dp[i][j-p][k-q] + h[i]);
        }
    }
    int ans = 0;
    repq(i,0,x) repq(j,0,y) ans = max(ans, dp[n][i][j]);
    cout << ans << endl;
    return 0;
}

さすがにナップザックの亜種は割とできるようになってきたけど、他の DP にもトライしてみなければ・・・。

2017-01-31

TopCoder SRM707 Div 2 Med: StepsConstruct

TopCoder

正答率低いのはバグりやすいせいかな。発想自体はそんなに難しくない。

問題概要

原文 → TopCoder Statistics - Problem Statement

$n \times m$ の盤面があり、. は通行可能な座標、# は通行不可能な座標を表す。座標の移動は上下左右の方向のみ許されている。左上の座標からスタートし、右下の座標にちょうど $k$ ステップで到達できるルートが存在するならば、そのルートを出力せよ。なお、同じ座標に何度移動しても構わないものとする。

解説

まず普通に BFS をやってみて、右下に行くまでに最短で何ステップ必要かを求めましょう。この時点で INF になったり $k$ を超えてたりしていると明らかに無理なので弾きます。

次に、 $k$ と最短ステップの偶奇を調べましょう。これが一致していないときも弾きます。

経路復元は、ゴールから再度 BFS していくのがやりやすいと思います。ゴールからたどれば、今いる座標の隣のどこかに (スタートから今いる座標に行くまでのステップ数 - $1$ ) の座標が必ず存在するので、経路復元が可能になります。

ここまで来たら、ステップ数が $k$ になるように適当に増やせば終わりです。手っ取り早いやり方としては、右下の座標の隣のドットと右下の座標に交互に移動し続けるのが良いでしょう。

ソースコード

int dy[]={0, 0, 1, -1};
int dx[]={1, -1, 0, 0};
string dir = "DURL";

int rec[100][100];
class StepsConstruct {
    public:
    string construct(vector<string> board, int k) {
        int n = board.size(), m = board[0].size();
        rep(i,0,n) rep(j,0,m) rec[i][j] = INF;
        rec[0][0] = 0;
        queue<pii> q;
        if(board[0][0] == '.') q.push(pii(0,0));

        while(!q.empty()) {
            pii t = q.front(); q.pop();
            rep(i,0,4) {
                int x = t.fr + dx[i];
                int y = t.sc + dy[i];
                if(x < 0 || x >= n || y < 0 || y >= m) continue;
                if(board[x][y] == '#') continue;
                if(rec[x][y] <= rec[t.fr][t.sc] + 1) continue;
                rec[x][y] = rec[t.fr][t.sc] + 1;
                q.push(pii(x,y));
            }
        }

        if(rec[n-1][m-1] == INF || rec[n-1][m-1] > k) return "";
        if(k % 2 != rec[n-1][m-1] % 2) return "";

        string ret = "";
        int dist = rec[n-1][m-1];
        q.push(pii(n-1, m-1));
        int repdir = -1;
        while(!q.empty()) {
            pii t = q.front(); q.pop();
            rep(i,0,4) {
                int x = t.fr + dx[i];
                int y = t.sc + dy[i];
                if(x < 0 || x >= n || y < 0 || y >= m) continue;
                if(rec[x][y] != dist - 1) continue;
                if(repdir == -1) repdir = i;
                ret += dir[i ^ 1];
                dist--;
                q.push(pii(x, y));
            }
        }
        reverse(ret.begin(), ret.end());
        while(ret.size() != k) ret = ret + dir[repdir] + dir[repdir ^ 1];
        return ret;
    }
};

今回はすんなり行けたけど、この手の問題って本番書いたらバグりそうでこわい。

hogecoder

tsutaj 競技プログラミングの記録

AtCoder Grand Contest 010 B: Boxes

問題概要

解説

ソースコード

AtCoder Regular Contest 027 C: 最高のトッピングにしような

問題概要

解説

ソースコード

TopCoder SRM707 Div 2 Med: StepsConstruct

問題概要

解説

ソースコード