2015-04-12

ABC 31 D 多重ループ

Atcoder

$\begin{eqnarray}{}_n H _k = _{n-1+k} C _{k-1} \end{eqnarray}$ をmod 1e9+7 での逆元を使いながら計算すれば良い。

最初 #define MOD 1000000007 としていたが、これだとMODはint型と判断されオーバーフローを起こしてしまってつらかった。

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

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

const ll MOD=1000000007;

ll inverse(ll a){
    ll res=1;
    ll base=a;
    REP(i,33){
        if(((MOD-2)>>i) & 1) res=(res*base)%MOD;
        base=(base*base)%MOD;
    }
    return res;
}

ll fact(ll a){
    ll res=1;
    for(int i=1;i<=a;i++) res=(res*i)%MOD;
    return res;
}

ll nHk(ll n, ll k){
    ll a=fact(n-1+k);
    ll b=inverse(fact(k));
    ll c=inverse(fact(n-1));
    return (((a*b)%MOD)*c)%MOD;
}

int main(){
	int n,k;
    cin >> n >> k;
    cout << nHk(n,k) << endl;
	return 0;
}

2015-04-11

AOJ 2587 Broken Cipher Generator

AOJ

以下のBNFに従ってparserを書く。

・<Cipher>:=(<String>)+
・<String>:='[' + <Cipher> + ']' | <Letter>
・<Letter>:=('+'|'-')* + <Alphabet>

但し、'?'を含むの要素は'A'と同一視する。

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

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

string expr_string();
char expr_letter();

int c;
string s;

string expr_cipher(){
    string res="";
    while(c!=s.length() && s[c]!=']'){
        res+=expr_string();
    }
    return res;
}

string expr_string(){
    string res="";
    char p=s[c];
    if(p=='['){
        c++;
        res=expr_cipher();
        reverse(res.begin(),res.end());
        c++;
    }else{
        res+=expr_letter();
    }
    return res;
}

char expr_letter(){
    int cnt=0;
    while(s[c]=='+' || s[c]=='-'){
        if(s[c]=='+') cnt++;
        else cnt--;
        c++;
    }
    if(s[c]=='?'){
        c++;
        return 'A';
    }
    char res='A'+(s[c]-'A'+cnt+130)%26;
    c++;
    return res;
}

int main(){
    while(cin >> s && s!="."){
        c=0;
        cout << expr_cipher() << endl;
    }
	return 0;
}

2015-04-10

AOJ 2021 Princess in Danger

AOJ

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;
}

2015-04-10

SRM 655 div1 easy BichromePainting

Topcoder

左端から順に塗りつぶして考えていくと、テストケースにうまくいかないものがあり、そこから手が出なかった。
最終状態から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";
}
}

2015-04-09

AOJ 1296 Repeated Substitution with Sed

AOJ

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;
}

2015-04-09

AOJ 1315 Gift from the Goddess of Programming

AOJ

区間[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;
}