TopCoder SRM 609 Div1
こんにちはtatsyです。
本日はSRM609の解説をいたします。さっそく参ります。
Easy (250点)
問題
ある文字列がk個の連続する’>’で始まり、そのあとにk個の連続した’<‘が現れて終わる、というようなものを魔法の呪文と呼ぶ。たとえば”»>«<“は魔法の呪文である。ある’>’と’<‘からなる文字列が与えられたとき、適当に文字を削除して得られる最大の呪文の長さはいくつかを求めよ。
解法
この問題はどこで’>’と’<‘が切り替わるのかを仮に決めると、その左側にある’>’と右側にある’<‘の数の小さい方を2倍することで呪文の長さが求まります。なので、ある地点より左に何個の’>’が、右に何個の’<‘があるのかを求めておいて、あとから呪文の長さの最大値を求めればいいです。
ただもう少し効率を良くしようとするなら、両端からスタートするコマを用意しておいて、だんだんにその間を狭めながら’>’と’<‘のペアを数えるほうが良いです。詳しくは以下のコードを参照してください。
#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;
#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
typedef pair<int,int> P;
typedef long long LL;
class MagicalStringDiv1 {
public:
int getLongest(string S) {
int n = S.size();
int l = 0;
int u = n-1;
int res = 0;
while(l <= u) {
if(S[l] == '>' && S[u] == '<') {
res += 2;
l++;
u--;
}
if(S[l] == '<') l++;
if(S[u] == '>') u--;
}
return res;
}
};
Medium (500点)
問題
K種類の色つきのボールがある。各ボールの個数はパラメータA, B, C, Dから一意にX[i]個に決定される(決定方法は公式の問題文を見てください)。この時、各ボールを最大K個のボールからなるパックに分けたい。ただし、パックにボールを入れるときは、
- (A) 同じボールだけを詰める
- (B) K種類のボールのうちのいくつかを1つずつ詰める
のいずれかしかできない。このとき、最小何パックでボールを分けられるか。
解法
まずボールの並び順は関係ないのでX[i]はあらかじめソートしてしまっても大丈夫です。さらにパックを選ぶ順番も別に関係がないので、(A)を先にまとめてやっても、(B)を先にまとめてやっても構いません。
では(A)の詰め方と(B)の詰め方はどちらの方が効率の良いパッキングといえるでしょうか？実は(A)の詰め方をするとき、最大のK個が取れるならば、これが最も効率が良いということになります。
なぜなら、今残っているボールの種類すべてでK個ずつボールを減らそうとするなら、1個ずつK回パッキングするよりも、各色をK個ずつ取っていった方が少ないパックしか使わないからです。
なので各X[i]をKで割って、そのあまりについて別に考えます。この際、何回(B)のパッキングを使うかさえ決めれば、X[i]はすべてK以下になっているので、何パックですべてを分けられるかが決まります。よってすべての1からKの値を試して、もっともパックが少なくなる回数を求めます。
最後にあらかじめ各X[i]を割って求めた(A)のパック数と、後から別に求めたパック数を足せば答えがでます。
#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;
#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
typedef long long lint;
typedef pair<lint,lint> pll;
const lint INF = 1ll << 60;
vector<lint> X;
class PackingBallsDiv1 {
public:
int minPacks(int K, int A, int B, int C, int D) {
vector<lint> X(K);
X[0] = A;
REPP(i,1,K-1) {
X[i] = (X[i-1] * B + C) % D + 1;
}
lint ans = 0;
REP(i,K) {
ans += X[i] / K;
X[i] %= K;
}
lint m = X.size();
lint t = INF;
sort(ALL(X));
REP(i,K) {
if(i >= X[m-1]) {
t = min(t, (lint)i);
break;
}
lint a = upper_bound(ALL(X), i) - X.begin();
t = min(t, i + K - a);
}
ans += t;
return (int)ans;
}
};
まとめ
今回はEasyがだいぶ簡単だったようでみんな超高速で解けていたので5分とかからず解いてもレートが下がるという悲劇が起きました。Mediumもあと一歩のところまで来ていたのですが、(A)の操作を優先していいというところに気づけづに時間切れとなりました。レートが伸び悩んでいますね、うーん。