TopCoder Open 2014 Algorithm Round 2A
こんにちはtatsyです。
今回はTCOのRound2Aを解説します。
Easy (250点)
問題
4×4のボードがある。16個のブロックが用意されていて、それぞれのブロックは底面が1×1、高さがheight[i]である。このブロックをボード上に並べるとき、外側に見えている面の面積を最大にしたい。その最大の面積を答えよ。
解法
テストケースの1が結構ヒントになる。1が8個、2が8個あるときには2が互いに隣り合わないようにチェッカー模様のように並べるのが最適になる。
ここからわかることはブロックを高い方のグループと低い方のグループで分けて、チェッカー状にそれを配置するのが良いということ。
これを踏まえて最終的に見える面が何に依存しているかを考えると、上記の並べ方では低い方のグループの並べ方にしか面積が依存していないことが分かる。
全てのブロックの底面以外が見えているとするとその面積は
16 + sum_i (height[i] * 4)
になる。
これに低いグループのブロックで隠れる部分の面積は場所によって違うことが分かる。角に来る2つのブロックは2面しか隠さないのに対して、内側に入る2つのブロックは4面とも隠す。それ以外の4つのブロックは3面を隠す。
そう考えると、多くの面を隠す部分に低いブロックを持って来た方が良いということになる。これで正解が得られる。
ちなみにチェッカーに並べるよりも最適な解が存在しないことはどこかのブロックを入れ替える計算を試しにやってみるとわかる。
#include <fstream>
#include <sstream>
#include <string>
#include <algorithm>
#include <numeric>
#include <vector>
#include <map>
#include <set>
#include <bitset>
#include <queue>
#include <stack>
#include <utility>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <climits>
using namespace std;
typedef long long lint;
typedef pair<lint,lint> pll;
#define REP(i,n) for(lint i=0; i<n; i++)
#define REPP(i,s,e) for(lint i=s; i<=e; i++)
#define ALL(a) (a).begin(), (a).end()
#define PRT(a) cerr << #a << " = " << (a) << endl
#define PRT2(a, b) cerr << #a << " = " << (a) << ", " << #b << " = " << (b) << endl
int mask[8] = {4,4,3,3,3,3,2,2};
class SixteenBricks {
public:
int maximumSurface(vector <int> H) {
sort(ALL(H));
int res = 16;
REP(i,H.size()) {
res += 4 * H[i];
}
REP(i,8) {
res -= 2 * mask[i] * H[i];
}
return res;
}
};
Medium (500点)
問題
幅がとても狭い道にオオカミが住んでいる。オオカミiはX座標a[i]を持つ位置にいて、今からb[i]に向かいたい。ただし、道の途中でオオカミはすれ違うことができない。その代り道の端には広場があり、そこでは順番が入れ替わることができる。今、道には0からLまでの整数座標が割り当てられていて、広場は0とLの位置にある。すべてのオオカミがゴールに辿りつくための最小手数はいくつか？
解法
まず一番単純なケースから考えると、オオカミは道の真ん中で順序が入れ替われないので、a[i]の順序とb[i]の順序が入れ替わらなければ単純にabs(a[i] – b[i])を足しあげていけばいい。
では、真ん中の方にいるオオカミの順序が変化しなくてはならないときはどうかというと、その場合には順序が入れ替わらなければならないグループ以外のオオカミの順序が変わらないとしても、右側か左側かのグループのオオカミが広場まで移動しなくてはいけない。
より複雑なケースになると、どちらかの広場に移動したあと、もう一方の広場まで移動するオオカミが必要になる場合もある。
じゃあ、どうするのかというと、移動の仕方の戦略は大きく2つに分けられる。
最初の状態で左のグループ、真ん中のグループ、右のグループと3つに分けたとき、真ん中のグループの順序を入れ替える必要がないとき。この時は、左のグループと右のグループがそれぞれ左側の広場と右側の広場に移動し、そこから自分のゴールへ向かえばいい。
最初の状態で左のグループと右のグループの2つに分ける。同様に最後の状態で左のグループと右のグループの2つに分ける。もし最初のグループと最後のグループで入っているグループが違えば、そのオオカミは左から右、あるいは右から左へと移動する。
この2つの戦略の場合の数は1の場合、左と真ん中のグループの区切りと真ん中と右のグループの区切りがO(N^2)あり、2の場合、最初の状態での区切り線と最後の状態での区切り線の入れ方がO(n^2)ある。それぞれのケースについて移動のコストを求める計算はO(n)なので全体ではO(n^3)になり、計算量は問題なし。
コードに微妙にコメントを入れたので、たぶんなんとなく理解できると思います(笑)。
#include <fstream>
#include <sstream>
#include <string>
#include <algorithm>
#include <numeric>
#include <vector>
#include <map>
#include <set>
#include <bitset>
#include <queue>
#include <stack>
#include <utility>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <climits>
using namespace std;
typedef long long lint;
typedef pair<lint,lint> pll;
#define REP(i,n) for(lint i=0; i<n; i++)
#define REPP(i,s,e) for(lint i=s; i<=e; i++)
#define ALL(a) (a).begin(), (a).end()
#define PRT(a) cerr << #a << " = " << (a) << endl
#define PRT2(a, b) cerr << #a << " = " << (a) << ", " << #b << " = " << (b) << endl
typedef pair<int,int> pii;
const lint INF = 1ll<<60;
class NarrowPassage {
public:
int l;
int n;
vector<int> a;
vector<int> b;
vector<pii> A;
vector<pii> B;
lint calc1(int le, int ri) {
// check grouping
set<int> lg, mg, rg;
for(int i=0; i<n; i++) {
int x = A[i].second;
if(i < le) lg.insert(x);
else if(i < ri) mg.insert(x);
else rg.insert(x);
}
for(int i=0; i<n; i++) {
int x = B[i].second;
if(i < le && lg.count(x) == 0) return INF;
if(le <= i && i < ri && mg.count(x) == 0) return INF;
if(ri <= i && rg.count(x) == 0) return INF;
}
// check order of mid group
for(int i=le; i<ri; i++) {
if(A[i].second != B[i].second) return INF;
}
lint ret = 0;
for(int i=0; i<n; i++) {
int x = A[i].second;
if(i < le) ret += a[x] + b[x];
else if(i < ri) ret += abs(a[x] - b[x]);
else ret += 2*l - a[x] - b[x];
}
return ret;
}
lint calc2(int at, int bt) {
// move to each end
lint ret = 0;
set<int> lg, rg;
for(int i=0; i<n; i++) {
int x = A[i].second;
if(i < at) {
ret += a[x];
lg.insert(x);
} else {
ret += l - a[x];
rg.insert(x);
}
}
// move to each goal
for(int i=0; i<n; i++) {
int x = B[i].second;
if(i < bt) {
ret += b[x];
if(lg.count(x) == 0) {
ret += l;
}
} else {
ret += l - b[x];
if(rg.count(x) == 0) {
ret += l;
}
}
}
return ret;
}
int minDist(int L, vector <int> a_, vector <int> b_) {
this->l = L;
this->a = a_;
this->b = b_;
this->n = (int)a.size();
A.clear();
B.clear();
REP(i,n) {
A.push_back(pii(a[i], i));
B.push_back(pii(b[i], i));
}
sort(ALL(A));
sort(ALL(B));
// divide into 3 groups
lint ans = INF;
for(int le=0; le<n; le++) {
for(int ri=le; ri<=n; ri++) {
ans = min(ans, calc1(le, ri));
}
}
// divide into 2 groups
// some wolves move one end to another
for(int a_th=0; a_th<=n; a_th++) {
for(int b_th=0; b_th<=n; b_th++) {
ans = min(ans, calc2(a_th, b_th));
}
}
return ans;
}
};
まとめ
今回はEasyを結構早めに通せました。僕が通したときは同じ部屋で2人しかできてなかったですね。コード自体は結構はやくできていたのですが、本当にチェッカー状に並べるのが最適なのかを確認するのに時間がかかりました。
テストケース1を見たときに多くの人はチェッカーで良いのでは？と思ったと思うので、その確認がある意味重要だったかなと思います。
あとの低い方を並べるときに場所によって隠す面の数が違うという話ですが、ここの部分は気づかなかったとしても低い方の並べ方を8!通りすべて試せばいいだけなので、オプションといえばオプションです。
Mediumは「ああ、これは左、真ん中、右のグループに分けて考えるんだな」というところまでは思いついていたのですが、両端の間を動くオオカミが必要になる場合が考えられていなくて、テストケースが通らないまま終了でした。
今回は順位が200位台後半。Tシャツ獲得はすべてのラウンドで獲得した順位の最大値を使ってソートされるらしいので、あと2ラウンドあることを考えるとかなり厳しいですね。
少なくとも200位以内には入らないとダメかな。とりあえず次も頑張ります。
最後までお読みいただき、ありがとうございました。