2개의 댓글이 있습니다.
-
-
Toivoa -
저는 med에서 문제 제대로 안 읽어서 삽질하다 systest에서 fail나고
hard 생각할 시간 별로 없어서 아래와 같이 테이블 두 개 써서 풀었습니다.
t[st][en]: [st, en)을 badge로 빈 칸 없이 채울 수 있는가? 이 테이블은 strncmp 등을 이용해서 잘 만듭니다
q[en][blanks] : [0, en)을 blanks 개의 빈칸으로 채울 때의 longest 길이.
initial: q[0][0] = 0 으로 놓고,
q[x][y]는- q[x - 1]y - 1 // 마지막 칸을 빈칸으로 채우는 경우
- max(q[i][y], x - i) (임의의 i에 대해 t[x][i]가 true인 경우. // [i, x)를 빈 칸 없이 채우는 경우 의 최대값이 됩니다. 답은 이렇게 만들어진 테이블 q에서 max(q[n][j]^2 - j) (0 <= j <= n) 이 됩니다.
14년 전 link
-
-
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
Kureyo
Easy 문제Jingle을 Ringle로 사고 파는 거래를 합니다. 1 Jingle을 X Ringle에 사는 거래시에, Jingle을 판 사람은 floor((X * tax) / 100)만큼을 세금으로 내야합니다. buyOffers, vector sellOffers, int tax)
buyOffers[q] = buyOffers[q] - buyOffers[q] * tax / 100;
for (int q=0;q
for (int q=0;q
{
grid ;=0 && x
if (org==1 && (cnt<2 || cnt>3)) return 0; _grid)
if (grid[q][w] == '?')
word;
if (Visit[a][b]) return Dp[a][b];
{ parts, vector badges)
word=badges;
{[이 글은 과거 홈페이지에서 이전된 글입니다. 원문보기]
1 Jingle을 사고 파는 제안들의 리스트가 주어집니다. buyOffers의 각 원소 멤버는 1 jingle을 그 가격에 사려는 사람이 있다는 뜻이고,
sellOffers의 각 원소 멤버는 1 Jingle을 그 가격에 파려는 사람이 있다는 뜻입니다.
buyOffers, sellOffers, tax가 주어질때 당신이 얻을 수 있는 최대 이득을 Ringle로 반환하세요.
당신은 다른 사람의 판매 제안은 얼마든지 수락할수 있지만, 다른 사람의 구매 제안은 충분한 Jingle이 있을때만 가능합니다.
흑자가 불가능하다면, 0을 반환하세요.
풀이싸게사서 비싸게 판다[...]라는 마인드를 품고, 또한 Jingle을 Ringle로 다시 환수할때 세금을 내야하므로, 각 구매제안은 세금만큼의 비율을 깎아두고 봐야합니다.
가능한 이득이 나는 제안을 모두 수락하고 싶으므로, 판매제안중에서 가장 저렴하게 살수있는 k개와 구매제안중에서 가장 비싸게 팔수있는 k개를 수락하는 전략으로 갑니다.
(더 좋은 제안이 있는데 굳이 비싸게 사거나 싸게 팔 필요는 없잖아요?)
이득이 최대화하기 위해선, k+1번째에서는 판매제안과 구매제안의 만남이 적자를 낳게 되는 때이겠죠.(혹은 k가 가능한 최대 제안일수도 있겠습니다)
그러므로 각 판매제안/구매제안을 역순과 정순으로 정렬해서 각각 매칭했을때 적자를 낳지 않는한 계속 더한 것이 답이 됩니다.=)
코드#include
#include
#include
using namespace std;
struct
JingleRingle
{
int profit(vector
{
for (int q=0;q
sort( buyOffers.rbegin(), buyOffers.rend() );
sort( sellOffers.begin(), sellOffers.end() );
int best = 0;
for (int q=0;q
if (buyOffers[q] - sellOffers[q]<=0) break;
best += buyOffers[q] - sellOffers[q];
}
return best;
}
};Med 문제라이프 게임은 초기 상태에 따라 이것의 진화를 보여주는 시뮬레이션입니다. 이건 2차원의 셀상에서 이루어지는데, 각 셀은 죽은 상태/산 상태가 있습니다. 각 셀은 8개의 이웃을 갖습니다. 초기상태에서 산 상태의 셀과 죽은 상태의 셀을 알고나면, 진화는 매 스텝스텝마다 일어납니다. 각 스텝마다 셀은 아래와 같이 변합니다:
- 각 살아있는 셀은 2 미만이나 3초과의 살아있는 셀과 이웃하면 죽습니다.
- 각 죽어있는 셀은 정확히 3개의 살아있는 셀과 이웃하면 살아납니다.
- 그 외의 경우는 이전 상태를 유지합니다.
모든 셀은 그 상태가 즉시 바뀌고, 계산에 필요한 값들은 바뀌기전에 전부 계산됩니다.초기 상태의 직사각형 영역을 나타내는 문자열 벡터, grid가 주어집니다. 1은 살아있는 셀, 0은 죽어있는 셀, ?는 현재 어떤 상태인지 알수없는 셀을 나타냅니다. 어떤 셀도 하나 초과의 ?셀과 인접하지 않습니다. 주어진 영역 밖에는 처음엔 전부 죽어있다고 가정합니다. ?셀을 0 또는 1로 정하되 1스텝뒤의 살아있는 셀을 최대화 시키고자 합니다. 다음 스텝에서 가능한 살아있는 셀의 최대수를 반환하세요.
풀이어떤 셀도 2개 이상의 ?셀과 마주하지않기 때문에, 2개 이상의 ?셀이 동시에 영향을 주는 영역은 존재하지 않습니다. 그러므로 각각의 ?셀에 대해 독립적인 문제로 바뀝니다. 즉, 주변의 8개 셀을 최대한 많이 살리는 방향으로 그리디하게 결정해주면 된다는 뜻이죠. 주의할 점: 예제 3을 보시면, grid외의 영역(좌표상으론 음수가 된다거나 하는 지점들)에도 셀이 살 수가 있습니다. 문제에선 약간 모호하게 넘어갔던 더라 다들 많이 낚이셨을듯-_-; 저같은 경우는 걍 탐색범위를 [-1,n]으로 바꿨다가 -1과 unsigned 값인 vector.size()를 비교해버려서 삽질을 해버렸죠ㅠㅠ
코드//1:alive 0:dead
//No cell will have more than one neighbor of type '?'
//All cells outside of the area described by grid are initially dead.
#include
#include
#include
using namespace std;
int dx[8]={-1,-1,-1,0,0,1,1,1};
int dy[8]={-1,0,1,-1,1,-1,0,1};
vector
int after(int y,int x)
{
//cout << y << " " << x << endl;
int cnt = 0;
for (int q=0;q<8;++q)
{
int yy = y + dy[q];
int xx = x + dx[q];
if (xx<0 || xx>=grid[0].length()) continue;
if (yy<0 || yy>=grid.size()) continue;
cnt += (grid[yy][xx] == '1');
}
int org = 0;
if (y>=0 && y
if (org==0 && (cnt==3)) return 1;
return org;
}
int setVal(int y,int x,int v)
{
int ret = 0;
grid[y][x] = v + '0';
for (int q=0;q<8;++q)
{
int yy = y + dy[q];
int xx = x + dx[q];
//if (xx<0 || xx>=grid[0].length()) continue;
//if (yy<0 || yy>=grid.size()) continue;
ret+=after(yy,xx);
}
return ret+after(y,x);
}
struct
FuzzyLife
{
int survivingCells(vector
{
grid = _grid;
for (int q=0;q
{
int a = setVal(q,w,0);
int b = setVal(q,w,1);
if (a>b) grid[q][w]='0';
else grid[q][w]='1';
}
int ret =0 ;
for (int q=-1;q<=(int)grid.size();++q) for (int w=-1;w<=(int)grid[0].length();++w) ret += after(q,w);
return ret;
}
};Hard 문제긴 문자열('parts')이 벡터-스트링의 형태로 주어지고, 이를 여러개의 (아마)작은 문자열 배지들('badges')로 커버하려고 합니다.
문자열위에 놓인 배지들은 서로 접할수는 있지만 겹칠수는 없으며, 배지들의 갯수는 충분합니다.
A를 문자열내에서 배지에 의해 덮힌 가장 긴 연속 문자열의 길이라고 하고,
B를 문자열내에서 배지에 의해 덮이지 않은 문자들의 수라고 할때
A^2-B를 최대화 해주세요.
- parts의 원소의 수는 1이상 20개 이하고 각 원소의 길이는 1 이상 50 이하.
- badges의 원소의 수는 1이상 50개 이하고 각 원소의 길이는 1 이상 50 이하.
- 모든 문자열은 영 대문자로 이루어져있음.
- badges의 원소들은 서로 다름.
풀이긴 문자열의 길이가 잘해야 1000정도이기 때문에, A를 loop를 돌려볼수 있습니다. 임의의 i<=j에 대해서, [i,j]가 (1)badges들로 커버가 가능한 영역이면, [0,i-1], j+1,L-1에서 (2)안 덮힌 가장 적은 원소의 수를 구해서 그것을 각각 때주면 되는데, (2)의 경우 우리가 좋아하는[...] DP로 쉽게 해결이 됩니다.- T[i,j] := i부터 j까지를 badge들로 덮을때 가능한 적은 안 덮힌 문자들의 수.
- T[i,j] = 0 "if i>j"
- T[i,j] = min(1+T[i+1,j], T[i+a.length,j]) [a는 i,j안에 들어가는 임의의 badge] "otherwise."
다만, 각 i,j에 대해 모든 badge가 매칭되는지 체크하는 것은 제법 느릴 수 있기 때문에 미리 시작점 i와 badge a가 매칭되는지를 체크해두어야합니다.그리고 (1) 또한 우리가 구한 T값을 이용해서 알수있는데 T[i,j]가 0이라면 전부 덮혔다는 이야기니까 쉽게 알수있죠. =)
디테일은 아래 코드를 참조해 주세요
코드//Define:
//A as the length of the longest contiguous sequence of letters covered with the badges
//B as the number of letters that are uncovered
// The score of the arrangement is A^2-B.
#include
#include
#include
using namespace std;
string obj;
vector
int L,N;
int Dp[1000][1000];
int Visit[1000][1000];
int HasMatched[1000][1000];
int Match[1000][1000];
int isMatch(int start,int id)
{
if (HasMatched[start][id]) return Match[start][id];
HasMatched[start][id]=1;
if (start + word[id].length() <= obj.length() && obj.substr(start,word[id].length()) == word[id])
return Match[start][id]=1;
return Match[start][id]=0;
}
int minUncover(int a,int b)
{
if (b
Visit[a][b]=1;
int ret = b - a + 1;
ret = min(ret,1+minUncover(a+1,b));
ret = min(ret,1+minUncover(a,b-1));
for (int q=0;q
if (isMatch(a,q) && a+word[q].length()-1<=b)
ret = min(ret, minUncover(a+word[q].length(),b));
}
return Dp[a][b] = ret;
}
struct HandlesSpelling
{
int spellIt(vector
{
for (int q=0;q
L = obj.length();
N = word.size();
int ret = -L;
for (int q=0;q
int a = minUncover(0,q-1);
int b = minUncover(q,w);
int c = minUncover(w+1,L-1);
if (b==0)
{
int res = (w-q+1) * (w-q+1) - a - c;
if (res>ret) ret=res;
}
}
return ret;
}
};
14년 전