GCJ 2013 Round1Aをできる限り解説

Tatsuya Yatagawa
Programming Contest

本日行われたGCJ2013のRound1Aですが、無事通過してRound2に進めました。

僕の成績としては

  • A-Small, A-Large
  • B-Small,
  • C-Small

の早解きで500位くらいという感じです。

C-Largeはちょっとやり方不明なのですが、それ以外の部分を解説してきたいと思います。

A. Bullseye

この問題はカラスよけの目玉みたいなものを書いていくという問題です。与えられている条件は、

  • 初期状態では半径rの白色の円が描かれている
  • その外側に黒いリングと白いリングを交互に書いていく
  • リングの幅はいずれの色も1cm幅とする *$\pi cm^2$だけ塗れる

解くべき問題は持っている$t ml$のペンキで何個の黒いリングが描けるでしょう？というものです。

さてn個のリングを描くのに必要なペンキの量は等差数列の和として求めることができます。今、半径が$r_1$まできている時、次のリングを描くのに必要なペンキの量は

$$ (\pi (r_1 + 1)^2 - \pi r_1^2) / pi = 2r_1 + 1 $$

です。

黒いリングと白いリングは交互にやってくるわけですから、n個のリングを描くのに必要なペンキの総量は初項$4 \pi$の等差数列の和です。つまり、

$$ (2r+1)n + 2 pi n (n-1) $$

になります。

これさえ分かれば、あとは二分探索で、必要なペンキの量がt以下になる最大のリング数nを求めればよいということになります。

Largeをやるときの注意として、普通に計算すると必要なペンキの量がlong longの範囲を超えてしまうという点があります。一瞬、多倍長演算が必要では？という疑問にかられますが、必要なペンキの量をよく見るとnの倍数になっているので、比較するときは必要なペンキの量とtとをnで割って比較すればこれを防げます。

以下がSmall、Largeともに通るコードです。


#include <sstream>
#include <string>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <bitset>
#include <queue>
#include <stack>
#include <utility>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cctype>
using namespace std;

typedef pair<int,int> pii;
typedef vector<int> vi;
typedef long long ll;

#define rep(i,n) for(int i=0; i<n; i++) 
#define repa(i,s,e) for(int i=s; i<=e; i++)
#define repd(i,s,e) for(int i=s; i>=e; i--)

int T;
ll r, t;

ll paint(ll n) {
    return (2*r+1) + 2 * (n-1);
}

int main() {
    cin>>T;
    rep(k,T) {
        cin>>r>>t;
        ll lower = 0;
        ll upper = 2000000000;
        while(lower < upper-1) {
            ll mid = (upper + lower) / 2;
            ll p = paint(mid);
            if(p <= (t/mid)) {
                lower = mid;
            } else {
                upper = mid;
            }
        }
        printf("Case #%d: %lldn", k+1, lower);
    }
}

B. Manage your Energy

この問題はお仕事をしている人がエネルギーを使いながら仕事をして、最大の合計パフォーマンスを出す方法を求める問題です。

ある仕事に捧げるエネルギーとタスクの重要度？みたいなものの積がそのタスクのパフォーマンスになります。タスクを終えると若干エネルギーが回復します。要は、このエネルギーの増減をうまく利用してパフォーマンスの合計値が最大になるようにします。

とはいえ、この問題Largeを解くのはそれほど簡単ではありません。というわけで、SmallとLargeを分けて解説したいと思います。

まず、Smallですが、使えるエネルギーの最大値Eとタスクの数Nに注目します。これらの値の範囲と見ると、Eが最大5、Nが最大10となっています。ということは、全ての場合を尽くしても$5^{10}$通りしかありません。ですから、これらを幅優先探索で全て調査してあげます。

このやりかたでとりあえずSmallは通ります。以下がSmall用のコードです。


#include <sstream>
#include <string>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <bitset>
#include <queue>
#include <stack>
#include <utility>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cctype>
using namespace std;

typedef pair<int,int> pii;
typedef vector<int> vi;
typedef long long ll;

#define rep(i,n) for(int i=0; i<n; i++) 
#define repa(i,s,e) for(int i=s; i<=e; i++)
#define repd(i,s,e) for(int i=s; i>=e; i--)

int T, E, R, N;
int v[11];
int maxval;

void dfs(int e, int g, int d) {
    if(d == N) {
        if(maxval < g) {
            maxval = g;
        }
        return;
    }

    for(int i=0; i<=e; i++) {
        int ne = min(E, (e-i) + R);
        int ng = g +i * v[d];
        dfs(ne, ng, d+1); 
    }
}

int solve() {
    maxval = 0;
    dfs(E, 0, 0);
    return maxval;
}

int main() {
    cin>>T;
    rep(t,T) {
        cin>>E>>R>>N;
        rep(i,N) cin>>v[i];
        printf("Case #%d: %dn", t+1, solve());
    }
}

さて、問題はLargeです。

僕が問題を見た感じでは、少し先までタスクの重要度を見て、貪欲法的に解くのかなと思い、コードを書きましたがLargeは通りませんでした。wataさんのコードを参考にして理解した部分を解説したいと思います。

基本的な方針は貪欲法と動的計画法の組み合わせです。保存しておくべき項目は

  1. エネルギーがi番目の状態前に最大の状態になるようにタスクをこなす場合の合計パフォーマンスの最大値
  2. エネルギーをi番目の状態で全て使う場合の合計パフォーマンスの最大値

という二つの場合の合計パフォーマンスです。

あとはこれらの値を適宜更新しながら動的計画法で問題を解きます。とはいえ更新の仕方も結構難しいです。もう少し詳しく解説したいところですが、正直8割くらいしか分かっていないというのと、人のコードを載せるのはどうなのよ、ということでこれ以上は割愛します。すみません。

C. Good Luck

さてCはLargeがよく分からないのでSmallだけ解説します。

これも問題のサイズに注目してみます。SmallはNが最大3、Mが2から5、Kが最大7です。

はい、もう分かりましたね。そうです。全ての場合はたった4^3 です。ですので、これも深さ優先探索で、全ての場合を調べます。

具体的には、1つの数を決めたら、K個の積のうち割り切れるものを割ります。3個の数字を選んだあとで全ての数字が1になっていたら成功です。

以下がSmall用の正解コードです。


#include <sstream>
#include <string>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <bitset>
#include <queue>
#include <stack>
#include <utility>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cctype>
using namespace std;

typedef pair<int,int> pii;
typedef vector<int> vi;
typedef long long ll;

#define rep(i,n) for(int i=0; i<n; i++) 
#define repa(i,s,e) for(int i=s; i<=e; i++)
#define repd(i,s,e) for(int i=s; i>=e; i--)

int T, R, N, M, K;

bool dfs(vector<int> v, int a, int d) {
    if(a == d) {
        rep(k, K) {
            if(v[k] != 1) return false;
        }
        return true;
    }

    for(int i=2; i<=M; i++) {
        vector<int> u(K);
        std::copy(v.begin(), v.end(), u.begin());
        for(int k=0; k<K; k++) {
            if(u[k] % i == 0) {
                u[k] = u[k] / i;
            }
        }

        if(dfs(u, a+1, d)) {
            printf("%d", i);
            return true;
        }
    }
    return false;
}

int main() {
    cin >> T;
    rep(t,T) {
        printf("Case #%d:n", t+1);
        cin>>R>>N>>M>>K;

        rep(i,R) {
            vector<int> v(K);
            rep(j,K) {
                cin >> v[j];
            }
            dfs(v, 0, N);
            printf("n");
        }
    }
}

感想

今回のGCJでようやくRound1A突破できました。なんで突破できたかと言われると微妙ですが、今回それほど得意な問題が出た、というわけではないので、Smallをとりあえず通すという作戦の勝利でしょうかね？おそらくB、CのLargeは僕の実力では難しかったので、潔く諦めたのが逆に良かったというところだと思います。

次は6月までRoundがないのでTopCoderで早く黄色になれるようにがんばります。

最後までお読みいただきありがとうございました。