AOJ 2431 House Moving

データ構造 DP Fenwick木 AOJ

問題

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

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

解法

移動させるときはまとめて移動させればいいので、和が最大な増加部分列を求め、それをコストの総和 {\frac{1}{2} n(n+1)} から引く。

{ dp(i) := i} 番目まででとれるコストの最大値

とし、普通の最長増加部分列問題のように { dp(i) = \max(\{ dp(j)+x_i | 1 \le j \le i-1 \}) } と更新していった。最大値を探すときに愚直にループを回すと {O(n^{2})} になってしまうのでDP配列を Fenwick 木で持って {O(n\log n)} まで高速化する。

和以外の演算の 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

AOJ 最小費用流 グラフ

問題

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

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

解法

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

最小費用量で解ける。

{2n+2} 個の頂点 {S,T,s_1, \cdots , s_n, t_1, \cdots , t_n} を作り、マス {(i,j)} に書くことに正のコスト、消すことに負のコストを持たせて容量1の辺 {s_i \rightarrow t_i} を張る。さらに容量1コスト0の辺 {S \rightarrow s_i} {t_i \rightarrow T} を張り、{S} から {T} へ容量 {n} のフローを流したときの最小費用を求める。

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

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

AOJ グラフ 六角座標 ダイクストラ法

問題

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

ソースコード

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

AOJ DP グラフ 最大流

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

問題

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

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

解答

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

ちなみに最小費用流でも解ける。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)

Codeforces DP メモ化再帰 グラフ 木の直径 UnionFind 数学 フェルマーの小定理 文字列 トライ木

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

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

A

読解に苦労したけど {a_i \le a_j} かつ {b_i > b_j} になるような組があるか見ればばいい。

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

以下{\mod 5} で考えます。フェルマーの小定理より {x = 1,2,3,4} に対して {x^{n} = x^{n\%4} } です。

{n \% 4 = 0 } のとき { 1^{0} + 2^{0} + 3^{0} + 4^{0} = 4 }
{n \% 4 = 1 } のとき { 1^{1} + 2^{1} + 3^{1} + 4^{1} = 10 = 0 }
{n \% 4 = 2 } のとき { 1^{2} + 2^{2} + 3^{2} + 4^{2} = 1^{2} + 2^{2} + (-2)^{2} + (-1)^{2} = 0 }
{n \% 4 = 3 } のとき { 1^{3} + 2^{3} + 3^{3} + 4^{3} = 1^{3} + 2^{3} + (-2)^{3} + (-1)^{3} = 0 }

制約が異様に大きいですが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

数列 { a_i } の中に { k } が現れる回数を { c_k } とし、{a_i} が小さい順に取っていくことにします。 {k} を取るか判断するとき、{(k+1) \times c_{k+1} } を取るのと {k \times c_k} を取るのとで最終的に得られるスコアの大きい方を選べば良いことになります。

{ f(i,false) := } {i-1} 番目を取ったときの {i} 番目以降で取れるスコアの最大値
{ f(i,true) := } {i-1} 番目を取らなかったときの {i} 番目以降で取れるスコアの最大値

という漸化式の { f(0,true) } をメモ化再帰で求めました。

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

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

AtCoder Regular Contest #027

ARC AtCoder DP 貪欲 UnionFind 文字列

oxo-で117th
Bが通らない理由がまだわからない

A

ふつうに60進数で引き算する

int main(){
    int h,m;cin>>h>>m;
    int ans=0;
    ans+=(18-h-1)*60 + 60-m;
    cout << ans << endl;
}

B

UnionFind木で同じ数字を表す文字をUnionしていき、答えの初期値1をそれぞれの集合に数字が含まれるなら1倍、数字が含まれず {s_1, \ s_2} の先頭の文字を含むなら9倍、そうでないなら10倍にしていく。

なぜか通らないので後で見直します。

// UnionFindはSpaghettiSourceのもの

string s,t;
int n;
ull solve(){
    if(n==1){
        if(isdigit(s[0]) || isdigit(t[0])) return 1;
        else return 10;
    }
 
    UnionFind uf(256);
    rep(i,n){
        uf.unionSet(s[i],t[i]);
    }
    map<char,set<char>> m;

    rep(i,n){
        m[uf.root(s[i])].insert(s[i]);
        m[uf.root(t[i])].insert(t[i]);
    }
 
    ull ans=1;
    each(e,m){
        int k=10;
        each(c,e.second)if(isdigit(c))k=1;
        ans*=k;
    }
    if(!isdigit(s[0]) && !isdigit(t[0])){
        ans/=10;
        ans*=9;
    }
    return ans;
}
 
int main(){
    while(cin>>n){
        cin>>s>>t;
        cout<<solve()<<endl;
    }
}

C

ナップサック問題をひねった問題。

{dp(i,x,y):=} {i} 番目までの品物でSチケットを {x} 枚、普通のチケットを {y} 枚残すように取ったときの嬉しさの最大値
とし、残っているチケットの使い方を考えながら更新していく。 使うときの価値はどちらのチケットも同じなので、なくなると困るSチケットを節約して使う。いまいち自信はなかったけどAcceptされた。

int dp[512][512][512]だとMLEするからint dp[2][512][512]としてdp[0]とdp[1]を交互に使いまわすように書きなおした。int dp[300][300][300]だと収まったらしい。

int X,Y,N;
int t[512],h[512];
int dp[2][512][512];
 
int solve(){
    memset(dp,0,sizeof(dp));
    rep(i,N){
        rep(x,X+1)rep(y,Y+1){
            dp[(i+1)&1][x][y] = dp[i&1][x][y];
            int uy = min(y,t[i]-1);
            int ux = t[i]-uy;
            if(1<=ux && ux<=x && 0<=uy && uy<=y){
                dp[(i+1)&1][x][y] =
                    max(dp[i&1][x][y],
                        dp[i&1][x-ux][y-uy]+h[i]);
            }
        }
    }
    int ans=0;
    rep(i,X+1)rep(j,Y+1){
        ans=max(ans, dp[N&1][i][j]);
    }
    return ans;
}
 
int main(){
    while(cin>>X>>Y){
        cin>>N;
        rep(i,N)cin>>t[i]>>h[i];
        cout<<solve()<<endl;
    }
}

AOJ 1283 Most Distant Point from the Sea

AOJ ICPC 幾何 山登り法 二分探索

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1283
多角形の内部の点で、辺との距離の最小値が最大になる点を求めよ。

解法

初めは他の人と同じように想定解の二分探索でやっていたが、謎のWAが解決できなかったから次のような山登り法?のような探索に変えた。

適当な内点を初期値として、最も距離が小さい辺と逆側に少しずつ動かしていった。
このアイデアは http://d.hatena.ne.jp/y_mazun/20121218/1355851934 を参考にした。
適当な3点を選び、その内心を最初の点としている。そこから最も距離が近い辺を探し、その方向とは逆向きのベクトルを足す。足すことによって点が円の外に出てしまうならその長さを足すことを諦めて、足す長さを短くする。これを答えに求められる精度が出る回数だけ繰り返す。 SpaghettiSourceのライブラリを使えば多角形の内外判定がlogの時間でできるのでだいたい {O(n \log n)} となるが、これにかかる定数で精度が決まるのでそこを調節する必要がある。

最初の点の選び方によって失敗することがあるようで、少しランダム要素を加えて3回に2回以上はACされるように調整した。

ソースコード

double const eps=1e-8;
double const inf = 1e10;
double const pi = acos(-1);

typedef complex<double> P;
inline double cross(P const&a, P const&b){return imag(conj(a)*b);}
inline double dot(P const&a, P const&b){return real(conj(a)*b);}
struct L : public vector<P> {
    L(const P &a, const P &b){push_back(a); push_back(b);}
    L(){}
};
P projection(L const&l, P const&p){double t = dot(p-l[0],l[0]-l[1])/norm(l[0]-l[1]);return l[0]+t*(l[0]-l[1]);}
inline double distanceLP(L const&l, P const&p){return abs(p-projection(l, p));}

P innerCenter(P const&a, P const&b, P const&c){
    double la=abs(b-c), lb=abs(c-a), lc=abs(a-b);
    return (la*a+lb*b+lc*c)/(la+lb+lc);
}

int n;
P ps[128];
L es[128];

enum { OUT, ON, IN };
int convex_contains(P const&p) {
    P g=(ps[0]+ps[n/3]+ps[2*n/3])/3.0;
    int a=0,b=n;
    while (a+1 < b) {
        int c=(a+b)/2;
        if (cross(ps[a]-g, ps[c]-g) > 0) {
            if (cross(ps[a]-g, p-g) > 0 && cross(ps[c]-g, p-g) < 0) b = c;
            else                                                    a = c;
        } else {
            if (cross(ps[a]-g, p-g) < 0 && cross(ps[c]-g, p-g) > 0) a = c;
            else                                                    b = c;
        }
    }
    b %= n;
    if (cross(ps[a] - p, ps[b] - p) < 0) return 0;
    if (cross(ps[a] - p, ps[b] - p) > 0) return 2;
    return 1;
}

double solve(){
    rotate(ps,ps+rand()%n,ps+n);
    ps[n]=ps[0];
    rep(i,n){
        es[i]={ps[i],ps[i+1]};
    }
    P p=innerCenter(ps[0],ps[n/3],ps[n/3*2]);

    if(n==3)return distanceLP(es[0],p);

    double const r[]={100,10,1,1e-1,1e-2,1e-3,1e-4,1e-5,1e-6,1e-7,1e-8};
    double static d[128];
    int near=0;
    rep(t,11){
        rep(u,3000){
            rep(i,n)d[i]=distanceLP(es[i],p);
            near=0;
            rep(i,n)
                if(d[i]<d[near]){near=i;
            }
            P h=projection(es[near],p);
            P np=p-(h-p)/d[near]*r[t];
            if(convex_contains(np)==IN){
                swap(p,np);
            } else {
                break;
            }
        }
    }
    return d[near];
}

int main(){
    srand(time(0));
    while(cin>>n && n){
        rep(i,n){
            double x,y;
            scanf("%lf%lf",&x,&y);
            ps[i]=P(x,y);
        }
        printf("%lf\n",solve());
    }
}

幾何の問題は完全にSpagettiSourceに頼り切っているので自力でライブラリ書かないといけないと思った。