しぼんぬ

JOI前といい今回といい、簡単な問題で例外条件的なやつを忘れて落ちるパターンが多すぎる。。。
xo- 315.26pt 539th
1049->1031(-18)
というわけでやばーいやばーい。次は持ち直さなければならない。

PikachuEasy

まぁ一文字の時を忘れた。
誤コード

class PikachuEasy {
public:
    string check( string word ) {
        string key="";
        bool flag=true;
        for (int i=0; i<word.length(); i++) {
            key+=word[i];
            if (key.length()==2&&key!="pi"&&key!="ka"&&key!="ch") {
                flag=false;
                break;
            } else if (key=="pi"||key=="ka") key="";
            if (key.length()==3&&key!="chu") {
                flag=false;
                break;
            } else if (key=="chu") key="";
        }
        if (flag) return "YES";
        else return "NO";
    }
};

そして修正して　（プラクティスルーム：3回やりなおさなければならなかったorz)

class PikachuEasy {
public:
    string check( string word ) {
        string key="";
        bool flag=true;
        for (int i=0; i<word.length(); i++) {
            key+=word[i];
            if (key.length()==2&&key!="pi"&&key!="ka"&&key!="ch") {
                flag=false;
                break;
            } else if (key=="pi"||key=="ka") key="";
            if (key.length()==3&&key!="chu") {
                flag=false;
                break;
            } else if (key=="chu") key="";
        }
        if (key.length()!=0) return "NO";
        if (flag) return "YES";
        else return "NO";
    }
};

このループ最後まで行ったら全部keyが空の状態で出てくるよなとか競技中に勘違いしていたのが惜しいｗｗｗ

CasketOfStarEasy

ケースが小さいのでDFSでやります。
選び方をnext_permutationでやることもできますし、蟻本で紹介されている囚人解放の類題なので区間DPでやることも。

class CasketOfStarEasy {
public:
    int sz;
    bool used[10];
    vector<int> w;
    int dfs(int pos, int res) {
        used[pos]=true;
        int x=w.size()-1, y=0;
        for (int i=pos+1; i<sz; i++) if (!used[i]) {
            x=i;
            break;
        }
        for (int i=pos-1; i>=0; i--) if (!used[i]) {
            y=i;
            break;
        }
        res+=w[x]*w[y];
        //////////////
        bool end=true;
        for (int i=0; i<sz; i++) if (!used[i]) end=false;
        if (end) {
            used[pos]=false;
            return res;
        }
        //////////////
        int temp=res;
        for (int i=1; i<sz-1; i++) {
            if (!used[i]) res=max(res,dfs(i,temp));
        }
        used[pos]=false;
        return res;
    }
    int maxEnergy( vector <int> weight ) {
        sz=weight.size();
        w=weight;
        fill(used, used+sz, false);
        used[0]=used[sz-1]=true;
        int res=0;
        for (int i=1; i<sz-1; i++) {
            res=max(res, dfs(i,0));
        }
        return res;
    }
};

MagicalGirl

問題に反して全然魔法少女は降りて来ませんでした。
まぁ期待値求めるDP。
なんとなく漸化式たてかけたけど無理だったorz

class MagicalGirl {
public:
    double maxExpectation( int M, vector <int> day, vector <int> win, vector <int> gain ) {
        int N=day.size();
        pair<int, P> witch[N];
        for (int i=0; i<N; i++) {
            witch[i]=make_pair(day[i],P(win[i],gain[i]));
        }
        sort(witch, witch+N);
        double dp[N+1][2];
        for (int i=0; i<=N; i++) {
            dp[i][0]=dp[i][1]=0;
        }
        dp[0][0]=dp[0][1]=M;
        for (int i=1; i<=N; i++) {
            dp[i][0]=max(dp[i-1][0],dp[i-1][1]);
            // gonyo gonyo
            // pi pikachu
            // hoge hoge
        }
    }
};

そういえば過去問やってました。。。

GroupedWordChecker

割と問題把握に時間がかかった。

class GroupedWordChecker {
public:
    bool check(string s) {
        string temp="";
        temp+=s[0];
        char bef=s[0];
        for (int i=1; i<s.length(); i++) {
            if (bef!=s[i]) {
                temp+=s[i];
                bef=s[i];
            }
        }
        set<char> ocr;
        for (int i=0; i<temp.length(); i++) {
            if (ocr.find(temp[i])!=ocr.end()) return false;
            ocr.insert(temp[i]);
        }
        return true;
    }
    int howMany( vector <string> words ) {
        int sz=words.size();
        int cnt=0;
        for (int i=0; i<sz; i++) {
            if (check(words[i])) cnt++;
        }
        return cnt;
    }
};

LampsGrid

最初ヘタに全列挙やって間違えまくってました。
まぁただの探索だったりしました。

class LampsGrid {
public:
    int mostLit( vector <string> initial, int K ) {
        int len=initial[0].length(), sz=initial.size();
        int res=0;
        vector<int> on[50];
        for (int i=0; i<sz; i++) {
            for (int j=0; j<len; j++) {
                if (initial[i][j]=='0') on[i].push_back(j);
            }
        }
        for (int i=0; i<sz; i++) {
            if (on[i].size()>K||(K-on[i].size())%2!=0) continue;
            int cnt=0;
            for (int j=0; j<sz; j++) {
                if (on[i]==on[j]) cnt++;
            }
            res=max(res,cnt);
        }
        return res;
    }
};