夢追い人

"It takes a dreamer to make a dream come true."―Vincent Willem van Gogh

参加〜

二完で22位だった。ICPC練習コンテスト系はこの順位安定する。

G

よく考えたらただの順列だった。
回文恐怖症克服したい

#include <cstdio>
#include <iostream>
#include <map>
#include <algorithm>
using namespace std;
typedef long long ll;
ll C(int c) {
    ll r=1;
    for (int i=2; i<=c; i++) r*=i;
    return r;
}
int main() {
    string s; cin>>s;
    map<char, int> cnt;
    for (int i=0; i<s.length(); i++) {
        if (cnt.find(s[i])!=cnt.end()) {
            cnt[s[i]]++;
        } else {
            cnt[s[i]]=1;
        }
    }
    int c=0, odd=0;
    for (map<char, int>::iterator it=cnt.begin(); it!=cnt.end(); it++) {
        if ((*it).second%2!=0) {
            odd++;
        }
    }
    if (odd>1) {
        puts("0");
    } else {
        ll res=C(s.length()/2);
        for (map<char, int>::iterator it=cnt.begin(); it!=cnt.end(); it++) {
            res/=C((*it).second/2);
        }
        printf("%lld\n",res);
    }
}

A

気づくのにおそろしく時間かかった。
よく考えてみるとただの全探索・・・って昨日のMedとおんなじや(T_T)

#include <cstdio>
#include <iostream>
#include <queue>
#include <map>
#include <algorithm>
using namespace std;
typedef pair<int, int> P;
typedef pair<P, pair<int,string> > PP;
string a, b, c;
int k;
int br[1000];
int main() {
    cin>>a>>b;
    scanf("%d",&k);
    c="";
    int n=a.length();
    for (int i=0; i<n; i++) c+='0';
    while (b.length()<n) b="0"+b;
    reverse(a.begin(), a.end()); reverse(b.begin(), b.end());
    queue<PP> que;
    que.push(make_pair(P(0,k),make_pair(0,"")));
    while (!que.empty()) {
        PP p=que.front(); que.pop();
        int i=p.first.first;
        int x=p.first.second;
        int br=p.second.first;
        string s=p.second.second;
        if (s.length()==n) {
            if (c<s) c=s;
            continue;
        }
        if (a[i]-br>=b[i]) {
            string temp="";
            temp+=a[i]-br-b[i]+'0';
            que.push(make_pair(P(i+1,x),make_pair(0,(temp+s))));
        } else {
            string temp="";
            temp+=a[i]-br+10-b[i]+'0';
            if (x>0) que.push(make_pair(P(i+1,x-1),make_pair(0,(temp+s))));
            que.push(make_pair(P(i+1,x),make_pair(1,(temp+s))));
        }
    }
    bool flag=false;
    for (int i=0; i<c.length(); i++) {
        if (c[i]!='0') {
            flag=true;
            putchar(c[i]);
        } else if (flag) {
            putchar(c[i]);
        }
    }
    puts("");
}

D

鬼畜問で通せてませんが僕の検討をちょこっと。
最初単純に書いてWAくらってもれてるのかなとおもいこんな感じに書いて見ました

#include <cstdio>
typedef long long ll;
ll gcd(ll a, ll b) { return b?gcd(b,a%b):a; }
int main() {
    ll mx=0, bunbo=1;
    int n; scanf("%d",&n);
    for (int i=0; i<n; i++) {
        int o, y; scanf("%d%d",&o,&y);
        if (o==1) mx+=y*bunbo;
        if (o==2) mx-=y*bunbo;
        if (o==3) mx*=y;
        if (o==4) bunbo*=y;
        ll x=gcd(mx,bunbo);
        mx/=x;
        bunbo/=x;
    }
    printf("%lld\n",mx/bunbo);
}

ただしこれでもWA。もれですかね?
BigIntegerとか非道を使ってみると・・・

import java.util.*;
import java.math.*;
public class Main {
    public static void main(String[] args) {
        Scanner stdIn=new Scanner(System.in);
        int n=stdIn.nextInt();
        BigInteger x=BigInteger.valueOf(0);
        BigInteger bunbo=BigInteger.valueOf(1);
        for (int i=0; i<n; i++) {
            int o=stdIn.nextInt(), y=stdIn.nextInt();
            BigInteger j=BigInteger.valueOf(y);
            if (o==1) x=x.add(j.multiply(bunbo));
            if (o==2) x=x.subtract(j.multiply(bunbo));
            if (o==3) x=x.multiply(j);
            if (o==4) bunbo=bunbo.multiply(j);
        }
//        System.out.println(x);
//        System.out.println(bunbo);
        System.out.println(x.divide(bunbo));
    }
};

TLEしました。
まぁなんでこんな無駄なことに紙面さいたかというと・・・・

解法教えてorz

広告を非表示にする