TopCoder SRM 610 Div1
こんにちはtatsyです。
本日はSRM610に参加しました。結果はChallengeして、Challengeされ返され50ptどまり。Mediumは時間内に解けなかったですが、今回のMediumは下手したらEasyより簡単だったんじゃないかな？その辺も含めて解説していきたいと思います。
Easy (250点)
問題
小さなマス目で区切られた長方形のボードがある。各マス目には白か黒の色が塗られている。このボードの部分でチャッカー模様のようになっている部分のうち面積が最大と成るものを見つけ、その面積を求めよ。
解法
僕の場合は、問題を見た瞬間にDPっぽい感じで面積を更新していくんだなぁ、と思い考え始める。あるdp[y][x]がdp[y-1][x]、dp[y][x-1]、dp[y-1][x-1]から求まらないかを考え、それっぽいコードを書いて提出。Challengeされる、という感じでした。
さて、実際の解法はどうかというと、DPっぽく管理すべきは実は面積ではなく、白、黒が交互に並ぶ「幅」です。あるマス目に注目した時に、そのマスを含めて左側に何個、白黒が並ぶのかを数えておきます。
面積の最大値を求めるときは、あるマスからスタートして、ボード上を下に走査していきます。白、黒が交互に並んでいる限り、注目マスから下に見ていったときの横の最小連続数を見ていくと、今の注目マスが右上に繰るような部分チェッカーの面積が求まります。
あとは、この考え方に基づいて、その中で面積が最大になるものを求めればいいです。たぶんコードを見たほうがしっくり来ると思います。
#include <fstream>
#include <sstream>
#include <string>
#include <algorithm>
#include <functional>
#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(int i=0; i<n; i++)
#define REPP(i,s,e) for(int 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 dp[111][111];
class TheMatrix {
public:
int MaxArea(vector <string> board) {
int w = board[0].size();
int h = board.size();
memset(dp, 0, sizeof(dp));
REP(y,h) {
dp[y][0] = 1;
REPP(x,1,w-1) {
if(board[y][x] != board[y][x-1]) {
dp[y][x] = dp[y][x-1] + 1;
} else {
dp[y][x] = 1;
}
}
}
int ret = 1;
REP(y,h) {
REP(x,w) {
int ma = dp[y][x];
ret = max(ma, ret);
REPP(k,y+1,h-1) {
if(board[k][x] != board[k-1][x]) {
ma = min(ma, dp[k][x]);
ret = max(ret, ma * (k - y + 1));
} else {
break;
}
}
}
}
return ret;
}
};
Medium (550点)
問題
あるパイロットが任務をこなしながら飛行機を操縦することを考える。ある任務iをこなすには燃料をduration[i]だけ消費し、その任務のあとでrefuel[i]だけ燃料が供給される。ただし全てのiについてduration[i] > refuel[i]が成り立っているものとする。このとき、パイロットがこなせる任務の最大数を求めよ。
解法
問題の条件として、任務の最大数が50、燃料に関する情報が最大5000、さらに問題の情報から残り燃料は単調減少であることなどを見て、ナップザックの変形問題だなぁと思う。あとはどの順番に任務をこなすかを考えるかだ、と思っているうちにタイムアップ。
結論から言うとrefuel[i]が大きい順に任務をこなしていくのがいい。もしrefuel[i]が同じなら、duration[i]が大きいものからこなしていくのがいい。その理由を説明します。
まず、この問題において、いくつかの任務をこなしたあとの残り燃料は、それまでにこなしてきた任務の順番には関係ありません。そういう意味でナップザック的な問題でどの任務を優先的に調査するかさえ決定すればDPで簡単に問題が解けます。
refuel[i]が大きい順に取ったほうが良い理由は簡単で、より多くの任務をこなすには最終的に消費可能になる燃料の合計値が大きいほうが有利だからです。最終的に消費可能になる燃料の合計値は初期燃料Fとこなしてきた任務のrefuelの合計になるので、refuel[i]が大きいものを優先的に選ぶべきです。
次に、refuelが同じ値のときにdurationが大きい順に選んだほうがよい理由です。もしある任務iとjのrefuelが同じでduration[i] > duration[j]だとしましょう。もしどちらか一方しか任務をこなせないとするならば、当然duration[j]を選んだほうが有利なわけですが、これはナップザック的調べ方から言うと問題なさそうです。
問題となるのは両方を行える可能性があるときです。先ほども申し上げたように、もし両方を行ったとするなら、その後の残り燃料はiを先にやろうがjを先にやろうが変わりません。ところが、このときに必要な燃料が少ないjの方から先に行うと、その後の燃料がduratiobn[i]より小さくなって、j -> iという順番では任務を行えなくなる可能性があるのです。
以上の理由から、refuelが大きいものを優先かつ、refuelが同じならdurationが大きいものを優先し、ナップザック的にDPを走らせればよいということになります。
#include <fstream>
#include <sstream>
#include <string>
#include <algorithm>
#include <functional>
#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(int i=0; i<n; i++)
#define REPP(i,s,e) for(int 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
lint dp[55][5055];
class AlbertoTheAviator {
public:
int MaximumFlights(int F, vector <int> duration, vector <int> refuel) {
int n = (int)duration.size();
memset(dp, -1, sizeof(dp));
vector<pll> v(n);
REP(i,n) {
v[i] = pll(refuel[i], duration[i]);
}
sort(ALL(v), greater<pll>());
dp[0][F] = 0;
REPP(i,1,n) {
REP(e,5001) {
dp[i][e] = dp[i-1][e];
}
REP(e,5001) {
if(dp[i-1][e] >= 0) {
if(e >= v[i-1].second) {
lint del = v[i-1].second - v[i-1].first;
dp[i][e-del] = max(dp[i][e-del], dp[i-1][e] + 1);
}
}
}
}
lint res = 0;
REP(e,5001) {
res = max(res, dp[n][e]);
}
return (int)res;
}
};
まとめ
あくまで感覚の話ですが、最近はMediumでも惜しいところまで思考はいっているので、もう少しでMediumに挑戦できるところまでは来ているじゃないかなと思います。まぁ、結論から言うと全然解けてないわけですが。
また1週間後にあるので、ぼちぼちと練習をしながら待ちたいと思います。