AOJ 2021 Princess in Danger

i番目の町にいて残り時間がjである状態を(i,j)としてこれらの状態間を移動にかかる時間ないしは経過時間をコストとする辺でつなぎ、グラフを作る。あとはDijkstra

#include <bits/stdc++.h>
using namespace std;

#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define INF 1000000

struct edge{int to,cost;};

typedef vector<edge> edges;
typedef pair<int,int> P;

void dijkstra(vector<edges> &g,vector<int> &dist,int s){
    int v=g.size();
    dist.assign(v,INF);dist[s]=0;
    priority_queue<P, vector<P>,greater<P> > que;
    que.push(P(0,s));
    while(!que.empty()){
        P p=que.top();que.pop();
        int vp=p.second;
        if(dist[vp]<p.first) continue;
        REP(i,g[vp].size()){
            edge e=g[vp][i];
            if(dist[e.to]>dist[vp]+e.cost){
                dist[e.to]=dist[vp]+e.cost;
                que.push(P(dist[e.to],e.to));
            }
        }
    }
}

int main(){
	int N,M,L,K,A,H;
    while(cin >> N >> M >> L >> K >> A >> H && N){
        vector<bool> fr(N,false);
        vector<edges> g(N*(M+1));
        fr[A]=true;
        fr[H]=true;
        REP(i,L){
            int tmp;
            cin >> tmp;
            fr[tmp]=true;
        }
        REP(i,K){
            int X,Y,T;
            cin >> X >> Y >> T;
            for(int j=T;j<=M;j++){
                int xk=X*(M+1)+j-T;
                int yk=Y*(M+1)+j-T;
                g[X*(M+1)+j].push_back((edge){yk,T});
                g[Y*(M+1)+j].push_back((edge){xk,T});
            }
        }
        REP(i,N)REP(j,M){
            if(fr[i]) g[i*(M+1)+j].push_back((edge){i*(M+1)+j+1,1});
        }
        vector<int> dist(N*(M+1));
        dijkstra(g,dist,A*(M+1)+M);
        int res=INF;
        REP(i,M+1){
            res=min(res,dist[H*(M+1)+i]);
        }
        if(res==INF) cout << "Help!" << endl;
        else cout << res << endl;
    }
	return 0;
}

SRM 655 div1 easy BichromePainting

左端から順に塗りつぶして考えていくと、テストケースにうまくいかないものがあり、そこから手が出なかった。
最終状態からk*kの正方形領域内に'B'と'W'の一方のみが存在するものがあれば、その領域を'?'で塗りつぶす。以下これを繰り返して最終的にn*n全体が'?'で埋まればPossible。

Topcoderの問題演習量が圧倒的に足りない感じ。

[参照記事]
SRM 655 div1 easy:BichromePainting - mayoko’s diary

class BichromePainting {
public:
bool degenerate(vector<string> &b,int y,int x,int k){
    int n=b.size();
    if(y+k-1>=n || x+k-1>=n) return false;
    char c='?';
    for(int i=y;i<=y+k-1;i++)for(int j=x;j<=x+k-1;j++){
        if(b[i][j]!='?'){
            if(c=='?'){
                c=b[i][j];
            }else if(c!=b[i][j]){
                return false;
            }
        }
    }
    if(c=='?') return false;
    for(int i=y;i<=y+k-1;i++)for(int j=x;j<=x+k-1;j++){
        b[i][j]='?';
    }
    return true;
}

bool isPossible(vector<string> &b){
    int n=b.size();
    REP(y,n)REP(x,n){
        if(b[y][x]!='?') return false;
    }
    return true;
}

string isThatPossible(vector <string> board, int k) {
	int n=board.size();
    bool flag=false;;
    while(1){
        REP(y,n)REP(x,n){
            if(degenerate(board,y,x,k)) flag=true;
        }
        if(!flag) break;
        flag=false;
    }
    if(isPossible(board)) return "Possible";
    else return "Impossible";
}
}

AOJ 1296 Repeated Substitution with Sed

string:size_typeとかstring:nposとかよく知らなかったので調べながら書いた。BFSで調べていくが、文字列の長さで枝刈りするだけではTLEしたので、setで既に生成された文字列をメモした。

#include <bits/stdc++.h>
using namespace std;

#define REP(i,n) for(int i=0;i<(int)(n);i++)

string rp(string str,string a,string b){
    string res=str;
    string::size_type pos=res.find(a);
    while(pos!=string::npos){
        res.replace(pos,a.size(),b);
        pos=res.find(a,pos+b.size());
    }
    return res;
}

int main(){
	int n;
    while(cin >> n && n){
        vector<string> a(n),b(n);
        string s,g;
        REP(i,n) cin >> a[i] >> b[i];
        cin >> s >> g;
        queue<pair<string,int> > que;
        set<string> st;
        que.push(make_pair(s,0));
        st.insert(s);
        int res=-1;
        while(!que.empty()){
            pair<string,int> p=que.front();
            que.pop();
            if(p.first==g){
                res=p.second;
                break;
            }
            REP(i,n){
                string tmp=rp(p.first,a[i],b[i]);
                if(tmp.length()>g.length()) continue;
                if(st.find(tmp)!=st.end()) continue;
                que.push(make_pair(tmp,p.second+1));
                st.insert(tmp);
            }
        }
        cout << res << endl;
    }
	return 0;
}

AOJ 1315 Gift from the Goddess of Programming

区間[a,b]と[c,d]の共通部分の長さはmax(0,min(b,d)-max(a,c))であることに注意して全探索する。最初、配列を小さく取り過ぎてREした。

#include <bits/stdc++.h>
using namespace std;

#define REP(i,n) for(int i=0;i<(int)(n);i++)
typedef pair<int,int> P;

int blessedTime(int a0,int b0,int a1,int b1){
    int aa=max(a0,a1);
    int bb=min(b0,b1);
    return max(0,bb-aa);
}

int main(){
    int n;
    while(cin >> n && n){
        vector<vector<P> > pr(600);
        REP(i,n){
            int M,D,h,m,p;
            string e;
            scanf("%d/%d %d:%d",&M,&D,&h,&m);
            cin >> e;
            scanf("%d",&p);
            int time=m+h*60+D*24*60+M*31*24*60;
            if(e=="I"){
                pr[p].push_back(make_pair(time,-1));
            }else{
                pr[p][pr[p].size()-1].second=time;
            }
        }
        int bt[600]={};
        for(int i=1;i<600;i++){
            REP(j,pr[i].size()){
                REP(k,pr[0].size()){
                    bt[i]+=blessedTime(pr[0][k].first,pr[0][k].second,pr[i][j].first,pr[i][j].second);
                }
            }
        }
        sort(bt,bt+600);
        cout << bt[599] << endl;
    }
    return 0;
}