情報オリンピック本選いってきました

Programming JOI

結果予想は・・・・・・・・

1 2 3 4 5
C++ C++ C++ C++ C++
模範解答 模範解答 模範解答 Wrong Answer? Time Limit Exceeded?
100%? 100%? 100%? 0%? 30%?

今年のボーダーは高くなるとの予想があるのでいやだなあ。

1

/I(OI)*/ごとに処理。てか普通に書けば通る。(あまりに普通に書いてO(nm)アルゴリズムはだめだけど)

解説したチューター「まさか、KMP SearchやSuffix Arrayを使ってといた人はいないですよね」

・・・いました。例のあのひと。

/*
TASKNO: 1
LANG: C++
NAME: Masaki Hara J090103VB
*/

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <utility>
#include <vector>

using namespace std;

const char *subseq = "IO";

char buf[1000003];

int main(int argc, char *argv[], char *envp[])
{
    FILE *in = fopen("input.txt", "r");
    FILE *out = fopen("output.txt", "w");
    int n;
    int m;
    fscanf(in, "%d\n", &n);
    fscanf(in, "%d\n", &m);
    fgets(buf, m, in);
    strcat(buf, "-");
    int cnt = 0;
    int sum = 0;
    for(int i=0;buf[i];i++) {
        if(subseq[cnt%2] == buf[i]){
            cnt++;
        } else {
            sum += max((cnt - 1) / 2 + 1 - n, 0);
            cnt = 0;
        }
        if(subseq[cnt%2] == buf[i]){
            cnt++;
        }
    }
    fprintf(out, "%d\n", sum);
    fclose(in);
    fclose(out);
    return 0;
}

2

店のほうをsortして普通にbinary search。

/*
TASKNO: 2
LANG: C++
NAME: Masaki Hara J090103VB
*/

#include <cstdio>
#include <algorithm>
#include <utility>
#include <vector>

using namespace std;

int main(int argc, char *argv[], char *envp[])
{
    FILE *in = fopen("input.txt", "r");
    FILE *out = fopen("output.txt", "w");
    int d;
    int n;
    int m;
    fscanf(in, "%d", &d);
    fscanf(in, "%d", &n);
    fscanf(in, "%d", &m);
    vector<int> shops(n+1);
    shops[0] = 0;
    for(int i=1;i<n;i++) {
        fscanf(in, "%d", &shops.at(i));
    }
    shops[n] = d;
    sort(shops.begin(), shops.end());
    int sum = 0;
    for(int i=0;i<m;i++) {
        int cur;
        fscanf(in, "%d", &cur);
        vector<int>::iterator lb = upper_bound(shops.begin(), shops.end(), cur);
        int nearA = *(lb-1);
        int nearB = *lb;
        sum += min(cur - nearA, nearB - cur);
    }
    fprintf(out, "%d\n", sum);
    fclose(in);
    fclose(out);
    return 0;
}

3

上からなめて、下からなめて、合計から最大値をひいておしまい。

/*
TASKNO: 3
LANG: C++
NAME: Masaki Hara J090103VB
*/

#include <algorithm>
#include <cstdio>
#include <utility>
#include <vector>

using namespace std;

class line : public pair<int, int>
{
public:
    int id;
    int stat0;
    int stat1;
    int point0;
    int point1;
};

int main(int argc, char *argv[], char *envp[])
{
    FILE *in = fopen("input.txt", "r");
    FILE *out = fopen("output.txt", "w");
    int n;
    int m;
    int h;
    int k;
    fscanf(in, "%d %d %d %d", &n, &m, &h, &k);
    vector<int> pts(n);
    for(int i=0;i<n;i++) {
        fscanf(in, "%d", &pts.at(i));
    }
    vector<line> lines(m);
    for(int i=0;i<m;i++) {
        lines.at(i).id=i;
        fscanf(in, "%d %d", &lines.at(i).second, &lines.at(i).first);
        lines.at(i).second--;
    }
    sort(lines.begin(), lines.end());
    vector<int> cache(n);
    for(int i=0;i<n;i++) {cache.at(i) = i<k;}
    for(vector<line>::iterator i=lines.begin();i!=lines.end();i++) {
        swap(cache.at(i->second),cache.at(i->second+1));
        i->stat0 = cache.at(i->second);
        i->stat1 = cache.at(i->second+1);
    }
    for(int i=0;i<n;i++) {cache.at(i) = pts.at(i);}
    int max_val = 0;
    for(vector<line>::reverse_iterator i=lines.rbegin();i!=lines.rend();i++) {
        i->point0 = cache.at(i->second);
        i->point1 = cache.at(i->second+1);
        swap(cache.at(i->second), cache.at(i->second+1));
        int val = (i->point0 - i->point1) * (i->stat0 - i->stat1);
        max_val = max(max_val, val);
    }
    int sum = 0;
    for(int i=0;i<k;i++) {sum += cache.at(i);}
    fprintf(out, "%d\n", sum - max_val);
    fclose(in);
    fclose(out);
    return 0;
}

4

どうみてもWrong Answerだがサンプルは通す。謎。

/*
TASKNO: 4
LANG: C++
NAME: Masaki Hara J090103VB
*/

#include <cstdio>
#include <algorithm>
#include <utility>
#include <vector>

using namespace std;

int main()
{
    FILE *in = fopen("input.txt", "r");
    FILE *out = fopen("output.txt", "w");
    int h,w,n;
    fscanf(in, "%d %d %d", &h, &w, &n);
    vector<vector<int> > amap(w, vector<int>(h));
    for(int y=0;y<h;y++) {
        for(int x=0;x<w;x++) {
            fscanf(in, "%d", &amap.at(x).at(y));
        }
    }
    int a=n-1;
    int x=0;int y=0;
    while(x<w && y<h) {
        //int c = (amap.at(x).at(y) ^ (a>>x) ^ (a>>y) ^ (a>>0)) & 1;
        int c = (amap.at(x).at(y) ^ (a>>(x+y))) & 1;
        if(c==0) {
            y++;
        } else {
            x++;
        }
    }
    fprintf(out, "%d %d\n", y+1, x+1);
    fclose(in);
    fclose(out);
    return 0;
}

4模範解答

ただのDP。

「解法がわからなければDP」神話があるらしい。

/*
TASKNO: 4
LANG: C++
NAME: Masaki Hara J090103VB
*/

#include <cstdio>
#include <algorithm>
#include <utility>
#include <vector>

using namespace std;

int main()
{
    FILE *in = fopen("input.txt", "r");
    FILE *out = fopen("output.txt", "w");
    int h,w,n;
    fscanf(in, "%d %d %d", &h, &w, &n);
    vector<vector<int> > amap(w, vector<int>(h));
    vector<vector<int> > cmap(w+1, vector<int>(h+1));
    cmap.at(0).at(0)=n-1;
    for(int y=0;y<h;y++) {
        for(int x=0;x<w;x++) {
            fscanf(in, "%d", &amap.at(x).at(y));
            cmap.at(x+1).at(y)+=(cmap.at(x).at(y)+amap.at(x).at(y))/2;
            cmap.at(x).at(y+1)+=(cmap.at(x).at(y)+1-amap.at(x).at(y))/2;
        }
    }
    int a=n-1;
    int x=0;int y=0;
    while(x<w && y<h) {
        int c = (amap.at(x).at(y) ^ cmap.at(x).at(y)) & 1;
        if(c==0) {
            y++;
        } else {
            x++;
        }
    }
    printf("%d %d\n", y+1, x+1);
    fclose(in);
    fclose(out);
    return 0;
}

5

いまいち速度がわからんがおそいほうらしい。間違いではないと思う。

/*
TASKNO: 5
LANG: C++
NAME: Masaki Hara J090103VB
*/

#include <cstdio>
#include <climits>
#include <algorithm>
#include <utility>
#include <vector>
#include <deque>

using namespace std;

class asearcher
{
public:
    deque<pair<int, int> > aque_val;
    deque<pair<int, int> > bque_val;
    deque<pair<int, int> >* aque;
    deque<pair<int, int> >* bque;
    int w,h;
    const vector<vector<int> >& amap;
    vector<vector<bool> > flags;
    int current;
    bool inrange(const pair<int, int>& pt) {
        return 0 <= pt.first && pt.first < w && 0 <= pt.second && pt.second < h;
    }
    void search(int lv) {
        swap(aque, bque);
        while(aque->size()>0) {
            pair<int, int> pt = aque->front();
            aque->pop_front();
            if(!inrange(pt))continue;
            if(flags.at(pt.first).at(pt.second))continue;
            if(amap.at(pt.first).at(pt.second) <= lv) {
                current++;
                flags.at(pt.first).at(pt.second) = true;
                //try_add(lv, pair<int, int>(pt.first+1,pt.second));
                //try_add(lv, pair<int, int>(pt.first-1,pt.second));
                //try_add(lv, pair<int, int>(pt.first,pt.second+1));
                //try_add(lv, pair<int, int>(pt.first,pt.second-1));
                aque->push_back(pair<int, int>(pt.first+1,pt.second));
                aque->push_back(pair<int, int>(pt.first-1,pt.second));
                aque->push_back(pair<int, int>(pt.first,pt.second+1));
                aque->push_back(pair<int, int>(pt.first,pt.second-1));
            } else {
                bque->push_back(pt);
            }
        }
    }
    void try_add(int lv, pair<int, int> pt) {
        if(!inrange(pt))return;
        if(flags.at(pt.first).at(pt.second))return;
        if(amap.at(pt.first).at(pt.second) <= lv) {
            aque->push_back(pt);
        } else {
            bque->push_back(pt);
        }
    }
    asearcher(int aw, int ah, const vector<vector<int> >& aamap) : w(aw), h(ah), amap(aamap), aque(&aque_val), bque(&bque_val), flags(aw, vector<bool>(ah)), current(0) {}
};

int main(int argc, char *argv[], char *envp[])
{
    FILE *in = fopen("input.txt", "r");
    FILE *out = fopen("output.txt", "w");
    int r;
    fscanf(in, "%d", &r);
    int aw;
    int ah;
    int aex;
    int aey;
    fscanf(in, "%d %d %d %d", &aw, &ah, &aex, &aey);
    aex--;aey--;
    vector<vector<int> > amap(aw, vector<int>(ah));
    vector<int> alvs_raw;
    for(int y=0;y<ah;y++) {
        for(int x=0;x<aw;x++) {
            fscanf(in, "%d", &amap.at(x).at(y));
            alvs_raw.push_back(amap.at(x).at(y));
        }
    }
    int bw;
    int bh;
    int bex;
    int bey;
    fscanf(in, "%d %d %d %d", &bw, &bh, &bex, &bey);
    bex--;bey--;
    vector<vector<int> > bmap(bw, vector<int>(bh));
    vector<int> blvs_raw;
    for(int y=0;y<bh;y++) {
        for(int x=0;x<bw;x++) {
            fscanf(in, "%d", &bmap.at(x).at(y));
            blvs_raw.push_back(bmap.at(x).at(y));
        }
    }
    alvs_raw.push_back(0);
    blvs_raw.push_back(0);
    sort(alvs_raw.begin(), alvs_raw.end());
    sort(blvs_raw.begin(), blvs_raw.end());
    vector<int> alvs;
    vector<int> blvs;
    unique_copy(alvs_raw.begin(), alvs_raw.end(), back_insert_iterator<vector<int> >(alvs));
    unique_copy(blvs_raw.begin(), blvs_raw.end(), back_insert_iterator<vector<int> >(blvs));
    alvs_raw.clear();
    blvs_raw.clear();
    asearcher searchera(aw, ah, amap);
    asearcher searcherb(bw, bh, bmap);
    searchera.bque->push_back(pair<int,int>(aex, aey));
    searcherb.bque->push_back(pair<int,int>(bex, bey));
    vector<pair<int, int> > atable;
    vector<pair<int, int> > btable;
    for(vector<int>::iterator i=alvs.begin();i!=alvs.end();i++) {
        searchera.search(*i);
        atable.push_back(pair<int, int>(searchera.current, *i));
    }
    for(vector<int>::iterator i=blvs.begin();i!=blvs.end();i++) {
        searcherb.search(*i);
        btable.push_back(pair<int, int>(searcherb.current, *i));
    }
    vector<pair<int, int> >::iterator fi=atable.begin();
    vector<pair<int, int> >::reverse_iterator bi=btable.rbegin();
    int min_sum = INT_MAX;
    while(fi != atable.end() && bi != btable.rend()) {
        int fsum=fi->first + bi->first;
        if(fsum>=r) {
            min_sum = min(min_sum, fi->second + bi->second);
            ++bi;
        } else {
            ++fi;
        }
    }
    fprintf(out, "%d\n", min_sum);
    fclose(in);
    fclose(out);
    return 0;
}

5模範解答

priority_queueをつかいつつ(0..r)をなめる。

確かにこれでいいやん。

あと、一部の人間のレベルを超越したりしてそうな参加者が、Union Findでいいやんとか言ってたけどそれは模範解答じゃないですよ。

あとで調べよう。

/*
TASKNO: 5
LANG: C++
NAME: Masaki Hara J090103VB
*/

#include <cstdio>
#include <climits>
#include <algorithm>
#include <utility>
#include <vector>
#include <queue>

using namespace std;


int main(int argc, char *argv[], char *envp[])
{
    FILE *in = fopen("input.txt", "r");
    FILE *out = fopen("output.txt", "w");
    int r;
    fscanf(in, "%d", &r);
    int aw;
    int ah;
    int aex;
    int aey;
    fscanf(in, "%d %d %d %d", &aw, &ah, &aex, &aey);
    aex--;aey--;
    vector<vector<int> > amap(aw, vector<int>(ah));
    for(int y=0;y<ah;y++) {
        for(int x=0;x<aw;x++) {
            fscanf(in, "%d", &amap.at(x).at(y));
        }
    }
    int bw;
    int bh;
    int bex;
    int bey;
    fscanf(in, "%d %d %d %d", &bw, &bh, &bex, &bey);
    bex--;bey--;
    vector<vector<int> > bmap(bw, vector<int>(bh));
    for(int y=0;y<bh;y++) {
        for(int x=0;x<bw;x++) {
            fscanf(in, "%d", &bmap.at(x).at(y));
        }
    }
    priority_queue<pair<int, pair<int, int> > > aque;
    priority_queue<pair<int, pair<int, int> > > bque;
    vector<int> adat(r+1);
    vector<int> bdat(r+1);
    aque.push(make_pair(-1, make_pair(aex, aey)));
    bque.push(make_pair(-1, make_pair(bex, bey)));
    int max_lv = 0;
    int acnt = 0;
    for(int i=0;i<=r;i++) {
        if(aque.empty())break;
        adat.at(i)=max_lv;
        acnt++;
        if(i==r)break;
        max_lv = max(max_lv, -aque.top().first);
        pair<int, pair<int, int> > cur = aque.top();
        aque.pop();
        int x=cur.second.first;
        int y=cur.second.second;
        amap.at(x).at(y)=-1;
        if(0<=x+1 && x+1<aw && 0<=y && y<ah && amap.at(x+1).at(y) != -1){aque.push(make_pair(-amap.at(x+1).at(y),make_pair(x+1,y)));}
        if(0<=x-1 && x-1<aw && 0<=y && y<ah && amap.at(x-1).at(y) != -1){aque.push(make_pair(-amap.at(x-1).at(y),make_pair(x-1,y)));}
        if(0<=x && x<aw && 0<=y+1 && y+1<ah && amap.at(x).at(y+1) != -1){aque.push(make_pair(-amap.at(x).at(y+1),make_pair(x,y+1)));}
        if(0<=x && x<aw && 0<=y-1 && y-1<ah && amap.at(x).at(y-1) != -1){aque.push(make_pair(-amap.at(x).at(y-1),make_pair(x,y-1)));}
    }
    max_lv = 0;
    int bcnt = 0;
    for(int i=0;i<=r;i++) {
        if(bque.empty())break;
        bdat.at(i)=max_lv;
        bcnt++;
        if(i==r)break;
        max_lv = max(max_lv, -bque.top().first);
        pair<int, pair<int, int> > cur = bque.top();
        bque.pop();
        int x=cur.second.first;
        int y=cur.second.second;
        bmap.at(x).at(y)=-1;
        if(0<=x+1 && x+1<bw && 0<=y && y<bh && bmap.at(x+1).at(y) != -1){bque.push(make_pair(-bmap.at(x+1).at(y),make_pair(x+1,y)));}
        if(0<=x-1 && x-1<bw && 0<=y && y<bh && bmap.at(x-1).at(y) != -1){bque.push(make_pair(-bmap.at(x-1).at(y),make_pair(x-1,y)));}
        if(0<=x && x<bw && 0<=y+1 && y+1<bh && bmap.at(x).at(y+1) != -1){bque.push(make_pair(-bmap.at(x).at(y+1),make_pair(x,y+1)));}
        if(0<=x && x<bw && 0<=y-1 && y-1<bh && bmap.at(x).at(y-1) != -1){bque.push(make_pair(-bmap.at(x).at(y-1),make_pair(x,y-1)));}
    }
    int min_sum = INT_MAX;
    for(int i=0;i<=r;i++) {
        if(i>=acnt || r-i>=bcnt)continue;
        min_sum = min(min_sum, adat.at(i) + bdat.at(r-i));
    }
    fprintf(out, "%d\n", min_sum);
    fclose(in);
    fclose(out);
    return 0;
}

反省

ぜんぜんだめだった。

必須アルゴリズムはだいたい覚えたので、応用の技術をみにつけないといけないっぽい。

アルゴリズム系のいろいろでもっと練習したいところだ。

これからにむけて

デキるやつの経歴を参考にすると、TopCoderに人生かけてたりするので、TopCoder SRMのpracticeするだけでもかなり違ってくる気がしてきたので、SRMの過去問にも手をつけたい。

あと、Project Eular、どう書く？org、PKUにも手をだしてみたい。

が、とりあえずまずは数学オリンピックのほうですね。