AOJ 2426 Treasure Hunt

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2426

個の点と 個の長方形が与えられる。各長方形の辺上または内部にある点の数を求めよ。

解法

座標圧縮・累積和の前計算といった工夫をしないとTLEする。

template<typename T>
inline void compless(vector<T> & c){
    sort(all(c));
    c.erase(unique(all(c)),c.end());
}
template<typename T>
inline size_t idx(T i, vector<T> const& c){
    return lower_bound(all(c),i) - c.begin();
}
 
int n,m;
int xs[5000], ys[5000];
int sum[5100][5100]={};
 
int main(){
    scanf("%d%d",&n,&m);
    vector<int> x(n),y(n);
    rep(i,n){
        scanf("%d%d",xs+i,ys+i);
        x[i]=xs[i];
        y[i]=ys[i];
    }
    compless(x);
    compless(y);
    rep(i,n){
        int fx=idx(xs[i],x);
        int fy=idx(ys[i],y);
        sum[fy+1][fx+1]++;
    }
    rep(i,y.size())rep(j,x.size()){
        sum[i+1][j+1]+=sum[i+1][j]+sum[i][j+1]-sum[i][j];
    }
 
    rep(i,m){
        int lx,ly,rx,ry;
        scanf("%d%d%d%d",&lx,&ly,&rx,&ry);
        lx = idx(lx,x);
        rx = idx(rx+1,x);
        ly = idx(ly,y);
        ry = idx(ry+1,y);
        printf("%d\n",sum[ry][rx]-sum[ry][lx]-sum[ly][rx]+sum[ly][lx]);
    }
}

AOJ 2428 Lost Number

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2428

穴あきの数式が与えられる。穴に適当な文字を入れて計算結果を最大化せよ。

解法

構文解析はエラーが起こったらメッセージ付きの例外を投げる実装にするのが一番実装もデバッグも楽だと思う。

文字の入れ方は高々 通りしかないのでパーサを書いて全探索する。(と)の間には<operator>がちょうど1個だけ入るので事前にチェックする。

inline bool valid(int x){ return 0<=x && x<1024; }
 
char e[128];
 
inline bool ispm(char c){
    return c=='+' || c=='-';
}
inline bool ispd(char c){
    return c=='*' || c=='/';
}
 
int num(char* &p);
int fac(char* &p);
int term(char* &p);
int expr(char* &p);
 
int num(char* &p){
    int res = 0;
    if(isdigit(*p)){
        ;
    }else{
        throw "num begin";
    }
    while (isdigit(*p)){
        res<<=1;
        res+=*p-'0';
        p++;
    }
 
    if(*p=='\0' || *p==')' || ispm(*p) || ispd(*p)){
        ;
    }else{
        throw "num end";
    }
 
    if(!valid(res)) throw "overflow";
    return res;
}
 
int fac(char* & p){
    int res = 0;
    if(*p=='(' || isdigit(*p)){
        ;
    }else{
        throw "fac begin";
    }
 
    if(*p=='('){
        p++;
        res += expr(p);
        p++;
    }else if(isdigit(*p)){
        res += num(p);
    }
    if(*p=='\0' || *p==')' || ispm(*p) || ispd(*p)){
        ;
    }else{
        throw "fac end";
    }
 
    if(!valid(res)) throw "overflow";
    return res;
}
 
int term(char* & p){
    int res;
    if(*p=='(' || isdigit(*p)){
        res = fac(p);
    }else{
        throw "term begin";
    }
    while(1){
        if(*p=='*'){
            p++;
            res *= fac(p);
        }else if(*p=='/'){
            p++;
            res /= fac(p);
        }else if(*p=='\0' || *p==')' || *p=='+' || *p=='-'){
            break;
        }else{
            throw "term end";
        }
    }
 
    if(!valid(res)) throw "overflow";
    return res;
}
 
int expr(char* & p){
    int res;
    if(*p=='(' || isdigit(*p)){
        res=term(p);
    }else{
        throw "exp begin";
    }
 
    while(1){
        if(*p=='+'){
            p++;
            res += term(p);
        }else if(*p=='-'){
            p++;
            res -= term(p);
        }else if(*p=='\0' || *p==')' || ispm(*p) || ispd(*p)){
            break;
        }else{
            throw "exp end";
        }
        if(!valid(res)) throw "overflow";
    }
 
    return res;
}
 
bool check(char* e){
    stack<int> s;
    for(int i=0;e[i];i++){
        if(e[i]=='(')s.push(i);
        else if(e[i]==')'){
            if(s.size()){
                int j=s.top();
                s.pop();
                int depth=0;
                bool ok=false;
                loop(k,j,i+1){
                    if((ispm(e[k]) || ispd(e[k])) && depth==1) ok=true;
                    else if(e[k]=='(') depth++;
                    else if(e[k]==')') depth--;
                }
                if(!ok) return false;
            }else{
                return false;
            }
        }
    }
    return s.size()==0;
}
 
int solve(){
    int ps[10];
    int c=0;
    for(int i=0;e[i];i++){
        if(e[i]=='.'){
            ps[c++]=i;
        }
    }
    int fine=1;
    rep(i,c)fine*=7;
    int ans=-1;
    rep(mask,fine){
        int k=mask;
        rep(i,c){
            int p=k%7;
            static const char cs[]="1-(*0+)";
            e[ps[i]]=cs[p];
            k/=7;
        }
        if(!check(e)) continue;
        try{
            auto it=e;
            ans=max(ans,expr(it));
            // cout << e << " : " << "ok" << endl;
        }catch(const char* c){
            // cout << e << " : " << c << endl;
        }
    }
    return ans;
}
 
int main(){
    scanf("%s",e);
    cout << solve() << endl;
}

AOJ 2431 House Moving

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2431

1 から までの整数を並び替えた列 が与えられる。 をコスト で好きな場所に移動できる。昇順にソートするのに必要なコストの最小値を求めよ。

解法

移動させるときはまとめて移動させればいいので、和が最大な増加部分列を求め、それをコストの総和 から引く。

番目まででとれるコストの最大値

とし、普通の最長増加部分列問題のように と更新していった。最大値を探すときに愚直にループを回すと になってしまうのでDP配列を Fenwick 木で持って まで高速化する。

和以外の演算の Fenwick 木を書いたのは初めてだった。

template <typename T>
struct fenwick_tree {
    vector<T> x;
    fenwick_tree(int n) : x(n, 0) { }
    T max(int j) {
        T S = 0;
        for (; j >= 0; j = (j & (j + 1)) - 1) S = std::max(x[j],S);
        return S;
    }
    void chmax(int k, T a) {
        for (; k < x.size(); k |= k+1) x[k] = std::max(x[k],a);
    }
};
 
int main(){
    ll n;scanf("%lld",&n);
    fenwick_tree<ll> dp(n+1);
    for(int i=0;i<n;i++){
        int x;scanf("%d",&x);
        dp.chmax(x,dp.max(x-1)+x);
        // for(int i=1;i<=n;i++){
        //     printf("%lld ",dp.max(i)-dp.max(i-1));
        // }
        // puts("");
    }
    printf("%lld\n",(ll)n*(n+1)/2 - dp.max(n));
}

AOJ 2429 marukaite

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2429

のグリッドがある。各マスは初期状態でoが書かれているか書かれていないかのどちらか一方である。各マスに対して、空白のときに書くコストと既にあるoを消すコストが与えられる。同じ行/列にoがちょうど1個になるように書いたり消したりするときの最小値をもとめよ。

解法

(2時間くらい考えて解けなかったので他人の答えを見ました。)

最小費用量で解ける。

個の頂点 を作り、マス に書くことに正のコスト、消すことに負のコストを持たせて容量1の辺 を張る。さらに容量1コスト0の辺 を張り、 から へ容量 のフローを流したときの最小費用を求める。

初期状態のコストをその状態から何もない状態にするのに必要なコストとし、そこに上で求めた最小費用を足すと答えになる。

int n;
Weight W[128][128], E[128][128];
char f[128][128];
 
void solve(){
    Weight C=0;
    rep(i,n)rep(j,n){
        if(f[i][j]=='o')C+=E[i][j];
    }
 
    Graph g(n*2+2);
    int s=n*2, t=n*2+1;
    rep(i,n){
        add_edge(g,s,i,1,0);
        add_edge(g,i+n,t,1,0);
    }
    rep(i,n)rep(j,n){
        if(f[i][j]=='o'){
            add_edge(g,i,j+n,1,-E[i][j]);
        }else{
            add_edge(g,i,j+n,1,W[i][j]);
        }
    }
 
    printf("%d\n",C+primal_dual(g,s,t,n));
    static int ans[10000][3];
    int cnt=0;
 
    rep(i,g.size()){
        rep(j,g[i].size()){
            auto & e=g[i][j];
            if(e.is_rev || e.cost==0) continue;
            if(f[e.src][e.dst-n]=='o' && e.cap!=0){
                cnt++;
                ans[cnt][0]=e.src+1;
                ans[cnt][1]=e.dst-n+1;
                ans[cnt][2]=0;
            }else if(f[e.src][e.dst-n]=='.' && e.cap==0){
                cnt++;
                ans[cnt][0]=e.src+1;
                ans[cnt][1]=e.dst-n+1;
                ans[cnt][2]=1;
            }
        }
    }
    printf("%d\n",cnt);
    rep(i,cnt){
        printf("%d %d %s\n",ans[i][0],ans[i][1],ans[i][2]==0 ? "erase" : "write");
    }
}
 
int main(){
    scanf("%d",&n);
    rep(i,n)rep(j,n){
        scanf("%d",&W[i][j]);
    }
    rep(i,n)rep(j,n){
        scanf("%d",&E[i][j]);
    }
    rep(i,n){
        scanf("%s",f[i]);
    }
    solve();
}

AOJ 2425 A Holiday of Miss Brute Force

問題

変な六角座標上での最短路問題。移動にかかるコストが時間によって変わる。(座標, 時間, 無視した回数)を状態に持ってダイクストラ法で探索した。実装が面倒。

ソースコード

ll const inf = 1<<28;
double const pi = acos(-1);
 
int sx,sy,gx,gy;
int n;
int fx[1000], fy[1000];
int lx,ly;
int g[256][256];
inline int & ref(int arr[256][256], int x, int y){
    return arr[y+128][x+128];
}
 
inline int valid(int x,int y){
    return abs(x)<=lx && abs(y)<=ly;
}
 
struct state {
    int x,y,t, ign;
    bool operator<(const state& s)const{
        if(ign != s.ign) return ign>s.ign;
        return t>s.t;
    }
};
 
int d[6][256][256];
 
int solve(){
    priority_queue<state> q;
    rep(i,6)rep(j,256)rep(k,256)d[i][j][k]=inf;
    q.push({sx,sy,0,0});
    ref(d[0],sx,sy) = 0;
 
    while(q.size()){
        auto s=q.top();q.pop();
        int t=s.t, x=s.x, y=s.y, ign=s.ign;
        // printf("x:%d y:%d t:%d ign:%d\n",x,y,t,ign);
        if(ref(d[t%6], x, y) > ign) break;
        if(x==gx && y==gy) return ign;
        static const int dx[]={0, 1, 1, 0,-1,-1, 0};
        static const int dy1[]={1, 0,-1,-1,-1, 0, 0};
        static const int dy2[]={1, 1, 0,-1, 0, 1, 0};
 
        rep(i,7){
            int nx=x+dx[i];
            int ny=y+(x&1 ? dy2[i] : dy1[i]);
            int nign;
            if(i!=6 && i==abs(x*y*t)%6 && valid(nx,ny) && ref(g,nx,ny)!=1){
                nign=ign;
            } else {
                nign = ign+1;
                if(!valid(nx,ny) || ref(g,nx,ny)==1){
                    nx=x, ny=y;
                }
            }
 
            if(ref(d[(t+1)%6], nx, ny) > nign){
                // printf("(%d,%d) -> (%d,%d) t:%d ign:%d dir:%d\n",x,y,nx,ny,t,ign,i);
 
                ref(d[(t+1)%6], nx, ny) = nign;
                q.push({nx,ny,t+1, nign });
            }
        }
    }
    int ans=inf;
    rep(i,6)ans=min(ans,ref(d[i],gx,gy));
    if(ans==inf) ans=-1;
    return ans;
}
 
int main(){
    while(scanf("%d%d%d%d",&sx,&sy,&gx,&gy)!=EOF){
        scanf("%d",&n);
        memset(g,0,sizeof(g));
        rep(i,n){
            int x,y;scanf("%d%d",&x,&y);
            ref(g,x,y)=1;
        }
        scanf("%d%d",&lx,&ly);
        printf("%d\n",solve());
    }
}

AOJ 1264 Concert Hall Scheduling

追記 : タグが間違っていたのを修正

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1246

コンサートホールが2つあリ、 日から 日までの期間を料金 で使用したいという申し込みが 個来ている。期間が被らないように2つのコンサートホールにうまく割り振ったときの の合計の最大値を求めよ。

解答

個目までの申し込みで、ホールAは 日目以降、ホールBは 日目以降の予定を開けるように設定したときの合計の最大値
として更新していった。(漸化式はソースコードを見て。)予約の終了日の最大値を として計算量は になる。

ちなみに最小費用流でも解ける。AOJ の Public Solutions で人の答えを見て気づいたが、そっちの方は単純明快すぎてびっくりした。

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

#define loop(i,a,b) for(int i=(a); i<int(b);i++)
#define rep(i,b) loop(i,0,b)

struct triple {
    int l,r,w;
};

triple a[1000];
int dp[2][400][400]; // i,j 以降は空いている
int n;

int solve(){
    memset(dp,0,sizeof(dp));
    sort(a,a + n,[](triple const& a,triple const& b){
            return a.l < b.l;
        });
    rep(i,n){
        auto next=dp[i&1];
        auto cur=dp[i+1&1];
        int l=a[i].l,r=a[i].r,w=a[i].w;
        rep(j,380)rep(k,380){
            next[j][k]=cur[j][k];
            if(j) next[j][k]=max(next[j][k],next[j-1][k]);
            if(k) next[j][k]=max(next[j][k],next[j][k-1]);

            if(j==r) next[j][k]=max(next[j][k],cur[l][k]+w);
            if(k==r) next[j][k]=max(next[j][k],cur[j][l]+w);
        }
    }
    return max(dp[0][370][370],dp[1][370][370]);
}


int main(){
    while (scanf("%d",&n),n){
        rep(i,n){
            int l,r,w; scanf("%d%d%d",&l,&r,&w);
            r++;
            a[i]={l,r,w};
        }
        printf("%d\n",solve());
    }
}

Codeforces Round #260 (Div. 2)

ooo-- = 1630 (+90), expert Rank: 382 でした。それなりの速度でコンスタントに3問解ければDiv1に行ける雰囲気ですね。

Cをもっと速く解いてEに時間を掛けたかったです。Dは解ける気がしなかったので無視しましたがTrie木(トライ木と読む)というデータ構造を使えれば良かったらしいです。

A

読解に苦労したけど かつ になるような組があるか見ればばいい。

int main(){
    int n; cin >> n;
    vector<pair<int, int>> v(n);
    rep(i, n){
        int a, b;
        scanf("%d %d", &a, &b);
        v[i] = make_pair(a, b);
    }
    sort(all(v));

    bool ans = true;
    rep(i, n - 1){
        if (v[i].second >= v[i + 1].second){
            ans = false;
            break;
        }
    }
    if (ans){
        cout << "Poor Alex";
    }
    else{
        cout << "Happy Alex";
    }
    cout << endl;
}

B

以下 で考えます。フェルマーの小定理より に対して です。

のとき
のとき
のとき
のとき

制約が異様に大きいですが4で割った余りを調べるには下2桁だけ見ればいいです。

int solve(string s){
    if (s.size() >= 2){
        s = s.substr(s.size() - 2);
    }
    stringstream ss(s);
    int t; ss >> t;
    if (t % 4 == 0){
        return 4;
    }
    else{
        return 0;
    }
}

int main(){
    string s;
    while(cin >> s)
        cout << solve(s) << endl;
}

C

数列 の中に が現れる回数を とし、 が小さい順に取っていくことにします。 を取るか判断するとき、 を取るのと を取るのとで最終的に得られるスコアの大きい方を選べば良いことになります。

番目を取ったときの 番目以降で取れるスコアの最大値
番目を取らなかったときの 番目以降で取れるスコアの最大値

という漸化式の をメモ化再帰で求めました。

1次元配列のループDPで求める方法もあるようです。

ll cnt[100000 + 100];
ll dp[100000 + 100][2];

ll M;

ll solve(ll k, bool f){
    if (i == M + 2) return 0;

    ll & res = dp[k][f];
    if (res != -1) return res;
    res = 0;

    // kを取る場合
    // k+1は取れなくなるので 一旦cnt[k+1]を0にする。
    ll t = cnt[k + 1];
    cnt[k + 1] = 0;
    res = max(res, cnt[k] * k + solve(k + 1, 0));
    cnt[k + 1] = t;

    // kを取らない場合
    res = max(res, solve(k + 1, 1));

    return res;
}

int main(){
    ll n;
    while (cin >> n){
        memset(cnt, 0, sizeof(cnt));
        memset(dp, -1, sizeof(dp));
        M = 0;
        rep(i, n){
            ll t; cin >> t;
            cnt[t]++;
            M = max(M, t);
        }
        cout << solve(0, 1) << endl;
    }
}

D

問題把握した瞬間に諦めました。

E

で直径を求める方法を UTPC2013 C で見たことがあったので手を付けていたけど、問い合わせクエリの度に直径を求める方法( なのでTLEする)より速くできなかった。解けてる人の解答を見て理解できたので後で解き直します。