JOI前哨戦

JOI前哨戦といいつつまぁJOIerほとんど出てなかったんですがｗ

はい。やってきました。
超好成績でした

236.82 0.00 510.45 0.00 Room 1位 Division 14位
861 -> 1043 (+182)

うほ☆

Easy

ただ1を数えるだけｗｗｗ

class P8XMatrixTransformation {
public:
   string solve( vector <string> original, vector <string> target ) {
    int onum = 0, tnum = 0;
    for (int i=0; i<original.size(); i++) for (int j=0; j<original[i].length(); j++) if (original[i][j]=='1') onum++;
    for (int i=0; i<target.size(); i++) for (int j=0; j<target[i].length(); j++) if (target[i][j]=='1') tnum++;
    if (onum==tnum) return "YES";
    else return "NO";
   }
};

Medium

グラフ構築問題。
無理〜

Hard

とりあえずコインの価値が大きいほうから貪欲でとっていき、
最後に枚数調整。

辞書順最小とかあった気がしてやばいな〜とおもってたけどなんだかんだで通りました^^;

class P8XCoinChangeAnother {
public:
   vector<long long> solve( int N, long long coins_sum, long long coins_count ) {
    vector<ll> score(N), res(N, 0), nul;
    score[0]=1;
    for (int i=1; i<score.size(); i++) score[i] = score[i-1]*2;
    ll rim = coins_count, t = coins_sum;
    for (int i=N-1; i>=0; i--) {
        if (score[i]<=t) {
            ll temp = t / score[i];
            res[i] = min(temp, rim);
            rim -= res[i];
            t -= res[i]*score[i];
        }
    }
    if (rim!=0) {
        for (int i=N-1; i>0; i--) if (res[i]!=0) {
            ll x = min(rim, res[i]);
            res[i] -= x;
            res[i-1] += x*2;
            rim -= x;
            if (rim==0) break;
        }
        if (rim!=0) return nul;
        else return res;
    }
    else if (t!=0) return nul;
    else return res;
   }
};

感想

Hardで貪欲はさすがになにか間違えてる気がしたｗ

こっから過去問

PlayGame

class PlayGame {
public:
   int saveCreatures( vector <int> you, vector <int> computer ) {
    sort(you.begin(), you.end(), greater<int>());
    sort(computer.begin(), computer.end(), greater<int>());
    int t=0, res=0;
    for (int i=0; i<you.size(); i++) {
        for (;t<computer.size();t++) {
            if (computer[t]<you[i]) {
                res += you[i];
                t++;
                break;
            }
        }
        if (t==computer.size()) break;
    }
    return res;
   }
};

StandInLine

class StandInLine {
public:
   vector <int> reconstruct( vector <int> left ) {
    vector<P> sold(left.size());
    vi res(left.size());
    for (int i=0; i<left.size(); i++) {
        sold[i].first=left[i];
        sold[i].second=i+1;
    }
    sort(sold.begin(), sold.end());
    for (int i=0; i<left.size(); i++) {
        int cnt=0;
        for (int j=i; j>=0; j--) if (sold[i].second<sold[j].second) cnt++;
        if (sold[i].first > cnt) {
            swap(sold[i], sold[i+1]);
            i--;
        } else if (sold[i].first < cnt) {
            swap(sold[i], sold[i-1]);
            i-=2;
        }
    }
    for (int i=0; i<left.size(); i++) res[i]=sold[i].second;
    return res;
   }
};