AtCoder Regular Contest #027

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倍、数字が含まれず の先頭の文字を含むなら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

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

番目までの品物でSチケットを 枚、普通のチケットを 枚残すように取ったときの嬉しさの最大値
とし、残っているチケットの使い方を考えながら更新していく。 使うときの価値はどちらのチケットも同じなので、なくなると困る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;
    }
}