とりあえず切る位置を表すmemo[左側][右側]の4000*4000の配列を用意してい動的計画法で解けばいいのか?
端から攻めていくかな?
とにかくこの手の問題は当たり前に言えることを探し当てて、最後は貪欲法に持って行ければ一番いいパタンだけど?
一つ考えた。
右と左に切断した時、右の個数*右の重さの総計+左の個数*左の重さの総計が最大化される場所できればいいのではないだろうか?
#include<stdio.h>
#include<algorithm>
#include<set>
#define lli long long int
struct B{
lli w;
int p;
bool operator<(const B& b)const{
return w<b.w;
}
};
std::set<B> memo;
lli sums[4002],ans;
lli saiki(int down,int up,lli herf){
if(down+1>=up)return sums[up]-sums[down];
B b;
b.w=herf;
std::set<B>::iterator it=memo.lower_bound(b);
int p1=(*it).p;
lli w1=(*it).w;
lli wR=sums[up]-sums[p1-(herf!=w1)];//右側
lli wL=sums[p1]-sums[down];//左側
lli re=0;
if(wL<wR){
re=saiki(down,p1,wL/2+sums[down]);
re+=saiki(p1,up,wR/2+sums[p1]);
}else{
re= saiki(p1-(herf!=w1),up,wR/2+sums[p1-(herf!=w1)]);
re+=saiki(down,p1-(herf!=w1),wL/2+sums[down]);
}
ans+=re;
return re;
}
int main(){
int n;
lli w;
std::set<B> body;
B b;
b.w=0;
b.p=0;
scanf("%d",&n);
//memo.insert(b);//0番の番兵
for(int i=1;i<=n;i++){
scanf("%lld",&w);
b.p=i;
b.w+=w;
sums[i]=b.w;
memo.insert(b);
}
ans=0;
saiki(0,n,sums[n]/2);
printf("%lld\n",ans);
}
2412 Village
解法
左端から右端へ精査していきます。
ある家のy座標より上下r以内で、x座標の距離がrまでの家との接続を検証すれば答えが出ます。
このために、x座標が左にある家からソートし、これを一つずつ調べていきます。
接続できるか調べる家の集合はy座標を優先してソートし今検証している家よりr左にある家は消去しながら家を追加していきます。
つながりを表す木構造はどの家もr以内にあるトいうことを利用して一つでも接続が見つかればそれを1本繋げるだけでR以内にある全部の家が木構造でつながります。
この問題最初ずっと前に問題を読んで解を全く思いつかず、何の脈絡もなく今日突然答えを思いついた次第です。
#include<stdio.h>
#include<vector>
#include<map>
#include<set>
#include<algorithm>
#include<math.h>
struct House{
double x,y;
int no;
};
class xSorter {
public:
bool operator()(const House& l, const House& r) const {
if(l.x!=r.x)return l.x<r.x;
return l.y<r.y;
}
};
class ySorter {
public:
bool operator()(const House& l, const House& r) const {
if(l.y!=r.y)return l.y<r.y;
return l.x<r.x;
}
};
House hs[200001];
std::vector<int> cons[200001];
int spents[200001]={0};
void saiki(int no){
spents[no]=1;
for(int i=0;i<cons[no].size();i++){
if(spents[cons[no][i]]==0){
saiki(cons[no][i]);
}
}
}
int main(){
int n;
double r;
scanf("%d %lf",&n,&r);
for(int i=0;i<n;i++){
scanf("%lf %lf",&hs[i].x,&hs[i].y);
hs[i].no=i;
}
std::sort(hs,hs+n,xSorter());
std::set<House,ySorter> sHouse;
std::set<House,ySorter>::iterator itD,itU,it;
House h,hD,hU,h2;
int p=0;
for(int i=0;i<n;i++){
h=hs[i];
hD.y=h.y-r-1;
hD.x=-10000000;
hU.y=h.y+r+1;
hU.x=h.x;
itD=sHouse.lower_bound(hD);
itU=sHouse.upper_bound(hU);
for(it=itD;it!=itU;it++){
h2=(*it);
if(r*1.001>=hypot(h.x-h2.x,h.y-h2.y)){
cons[h.no].push_back(h2.no);
cons[h2.no].push_back(h.no);
break;
}
}
while(h.x-hs[p].x>r*1.001){
sHouse.erase(hs[p]);
p++;
}
sHouse.insert(h);
}
int ans=0;
for(int i=0;i<n;i++){
if(spents[i]==0){
saiki(i);
ans++;
}
}
printf("%d\n",ans);
}
2417 Flick Input
解法
簡単すぎるので特に解法なし。
そのまま手前から処理していくだけです。
#include<stdio.h>
int main(){
char text[1010],c,c1;
char out2[6]={"aiueo"};
char out1[20]={"w kstnhmyrw"};
int no;
scanf("%s",&text);
for(int i=0;text[i]!='\0';i+=2){
c=text[i];
c1=text[i+1];
if(c1=='T')no=0;
if(c1=='L')no=1;
if(c1=='U')no=2;
if(c1=='R')no=3;
if(c1=='D')no=4;
if(c=='0'){
if(c1=='U')printf("nn");
if(c1=='T')printf("wa");
if(c1=='D')printf("wo");
}else if(c=='8'){
if(c1=='U')printf("yu");
if(c1=='T')printf("ya");
if(c1=='D')printf("yo");
}else{
if(c!='1')printf("%c",out1[c-'0']);
printf("%c",out2[no]);
}
}
printf("\n");
}
2419 Acrophobia
解法
とりあえず何も考えず集めた巻物のセットと現在位置とタイムを基準にダイクストラ法の応用でアセプト。
多分解き方としては教科書的。
#include<stdio.h>
#include<map>
#include<string.h>
#include<algorithm>
#include<queue>
struct P{
int x,y,perm,time;
bool operator<(const P& p)const{
return time>p.time;
}
};
int timeMemo[32][101][101];
int main(){
char board[101][101];
int timeBoard[101][101];
int makimono[101][101];
int timeTable[4][4]={ {10000,3,2,1},
{3,3,2,1},
{2,2,2,1},
{1,1,1,1}};
int n,m,gx,gy,mNo=1,all=0,w,h;
scanf("%d %d",&w,&h);
memset(timeBoard,0,sizeof(timeBoard));
memset(makimono,0,sizeof(makimono));
P p,nextP;
for(int i=0;i<h;i++){
scanf("%s",board[i]);
for(int j=0;board[i][j]!='\0';j++){
char c=board[i][j];
if(c=='S'){
p.x=j;
p.y=i;
p.perm=0;
p.time=0;
}else if(c=='G'){
gx=j;
gy=i;
}else if(c=='.'){
}else if(c=='#'){
for(int dx=0;dx<=3;dx++){
for(int dy=0;dy<=3;dy++){
if(i+dy<h &&j+dx <w)timeBoard[i+dy][j+dx]=std::max(timeBoard[i+dy][j+dx],timeTable[dy][dx]);
if(i+dy<h &&j-dx>=0)timeBoard[i+dy][j-dx]=std::max(timeBoard[i+dy][j-dx],timeTable[dy][dx]);
if(i-dy>=0&&j+dx <w)timeBoard[i-dy][j+dx]=std::max(timeBoard[i-dy][j+dx],timeTable[dy][dx]);
if(i-dy>=0&&j-dx>=0)timeBoard[i-dy][j-dx]=std::max(timeBoard[i-dy][j-dx],timeTable[dy][dx]);
}
}
}else if(c=='M'){
makimono[i][j]=mNo;
all+=mNo;
mNo*=2;
}
if(timeBoard[i][j]<1)timeBoard[i][j]=1;
}
}
memset(timeMemo,-1,sizeof(timeMemo));
int dxs[]={1,0,-1,0};
int dys[]={0,1,0,-1};
std::priority_queue<P> qu;
qu.push(p);
while(qu.empty()==false){
p=qu.top();
qu.pop();
//printf("(%d %d %d %d)",p.perm,p.x,p.y,p.time);
if(p.perm==all&&p.x==gx&&p.y==gy)break;
if(timeMemo[p.perm][p.y][p.x]!=-1&&timeMemo[p.perm][p.y][p.x]<=p.time)continue;
timeMemo[p.perm][p.y][p.x]=p.time;
for(int i=0;i<4;i++){
nextP.y=p.y+dys[i];
nextP.x=p.x+dxs[i];
if(nextP.x<0||w<=nextP.x||nextP.y<0||h<=nextP.y)continue;
nextP.perm=(p.perm|makimono[nextP.y][nextP.x]);
nextP.time=p.time+timeBoard[p.y][p.x];
if(timeMemo[nextP.perm][nextP.y][nextP.x]!=-1&&timeMemo[nextP.perm][nextP.y][nextP.x]<=nextP.time)continue;
qu.push(nextP);
}
}
printf("%d\n",p.time);
}
2420 Anipero 2012
解法
とりあえずベーシックに4次元の動的計画法で解いてみたけど、なんかメモリを大量使用してしまった。
考えるのが難しいから4次元はあまりすきではないな。
何かで次元数を下げることが出来るのかな?
#include<stdio.h>
#include<string.h>
int ans[51][51][51][51];//ans[n曲目][折った本数][レベル2の本数][レベル1の本数]=満足度
bool calcOK[51][51][51][51];//同上 計算可能のメモ
int main(){
int n,m;
int a,b,c;
scanf("%d %d",&n,&m);
memset(ans,0,sizeof(ans));
memset(calcOK,false,sizeof(calcOK));
for(int i=0;i<=m;i++){
calcOK[0][i][i][0]=true;
}
int lastAns=-100000000;
for(int i=1;i<=n;i++){
//iはn曲目
scanf("%d %d %d",&a,&b,&c);
for(int j=0;j<=m;j++){
//jは折った数
for(int L2=0;L2<=j;L2++){
//前回折ったLevel2の数
for(int L1=0;L1+L2<=j;L1++){
if(calcOK[i-1][j][L2][L1]==false)continue;
int mMax;
for(int a1=0;a1<=8&&a1<=L2;a1++){
for(int b1=0;b1+a1<=8&&b1<=L1;b1++){
if(a1==0&&b1==0)mMax=c;
else if(mMax<a*a1+b*b1)mMax=a*a1+b*b1;
}
}
for(int nowL2=0;nowL2+j<=m;nowL2++){
if(calcOK[i][j+nowL2][nowL2][L2]==false){
ans[i][j+nowL2][nowL2][L2]=ans[i-1][j][L2][L1]+mMax;
calcOK[i][j+nowL2][nowL2][L2]=true;
}
if(ans[i][j+nowL2][nowL2][L2]<ans[i-1][j][L2][L1]+mMax){
ans[i][j+nowL2][nowL2][L2]=ans[i-1][j][L2][L1]+mMax;
}
if(i==n&&lastAns<ans[i][j+nowL2][nowL2][L2])lastAns=ans[i][j+nowL2][nowL2][L2];
}
}
}
}
}
printf("%d\n",lastAns);
}
最終更新:2013年02月21日 00:06