JOI2006本選 一括＠C++

Programming TodaysJOI CPP

JOI2009本選にそなえて、JOI2006本選を3時間かけて実践演習。

JOI2007ではじめて本選にいったときにちょっと見たときは全然解ける気がしなかった。

1

pairは適切にfirst優先でsecondを次に比較する機能があるので、pairにいれてsortすればおわり。

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

using namespace std;

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 %d", &n, &m);
    vector<pair<int, int> > sums(m);
    for(int i=0;i<m;i++) {
        sums.at(i).first = 0;
        sums.at(i).second = i;
    }
    for(int i=0;i<n;i++) {
        for(int j=0;j<m;j++) {
            int ans;
            fscanf(in, "%d", &ans);
            sums.at(j).first -= ans;
        }
    }
    sort(sums.begin(), sums.end());
    for(int i=0;i<m;i++) {
        if(i+1 == m) {
            fprintf(out, "%d\n", sums.at(i).second+1);
        } else {
            fprintf(out, "%d ", sums.at(i).second+1);
        }
    }
    fclose(in);
    fclose(out);
    return 0;
}

2

キューで逐次処理にすることでメモリを抑えたつもりだけど、こんな凝ったことする必要があったのか甚だ疑問。いや普通に文字列で処理して全然問題なかったっぽい。損した。

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

using namespace std;

FILE *out;

void push_num(deque<int> &target, int num)
{
    if(num>=10) {
        push_num(target, num/10);
    }
    target.push_back(num%10);
}

void proc(vector<deque<int> > &lines, int depth)
{
    if(depth == lines.size()) {
        return;
    }
    deque<int> &line=lines.at(depth);
    bool repeat_flag = true;
    while(repeat_flag) {
        int cur = -1;
        int count = 0;
        repeat_flag = false;
        for(deque<int>::iterator i=line.begin();i!=line.end();i++) {
            if(cur == -1) {
                if(*i == -2) {
                    if(depth + 1 < lines.size()) {
                        lines.at(depth+1).push_back(-2);
                        proc(lines, depth+1);
                    }
                    repeat_flag = false;
                    return;
                }
                cur = *i;
            } else {
                if(cur == *i) {
                    cur = *i;
                } else {
                    //printf("depth %d: %d * %d(%d%d)\n", depth, cur, count, count, cur);
                    for(int j=0;j<count;j++) {
                        line.pop_front();
                    }
                    if(depth + 1 < lines.size()) {
                        push_num(lines.at(depth+1), count);
                        push_num(lines.at(depth+1), cur);
                        proc(lines, depth+1);
                    } else {
                        fprintf(out, "%d%d", count, cur);
                    }
                    repeat_flag = true;
                    break;
                }
            }
            count++;
        }
    }
}

int main(int argc, char *argv[], char *envp[])
{
    FILE *in = fopen("input.txt", "r");
    out = fopen("output.txt", "w");
    int n;
    char first_line[101];
    fscanf(in, "%d", &n);
    fscanf(in, "%s", first_line);
    vector<deque<int> > lines(n);
    for(int i=0;first_line[i]!='\0';i++) {
        lines.at(0).push_back(first_line[i]-'0');
        proc(lines, 0);
    }
    lines.at(0).push_back(-2);
    proc(lines, 0);
    fprintf(out, "\n");
    fclose(in);
    fclose(out);
    return 0;
}

3

普通の探索で全く問題ない。

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

using namespace std;

FILE *out;

int proc(vector<int> &stk, int imax, int rest)
{
    if(rest == 0) {
        for(vector<int>::iterator j=stk.begin();j!=stk.end();j++) {
            if(j+1==stk.end()) {
                fprintf(out, "%d\n", *j);
            } else {
                fprintf(out, "%d ", *j);
            }
        }
        return 0;
    }
    for(int i=imax;i>0;i--) {
        int srest = rest - i;
        if(srest >= 0) {
            stk.push_back(i);
            proc(stk, i, srest);
            stk.pop_back();
        }
    }
    return 0;
}

int main(int argc, char *argv[], char *envp[])
{
    FILE *in = fopen("input.txt", "r");
    out = fopen("output.txt", "w");
    int n;
    fscanf(in, "%d", &n);
    vector<int> stk;
    proc(stk,n,n);
    fclose(in);
    fclose(out);
    return 0;
}

4

ぱっと見、全部探索するパターンは膨れあがりそうに見えるけど、よく調べてみると、意外にだいじょうぶだということがわかる。

よってDFSで問題なし。ただしフラグを立てるのを忘れずに。

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

using namespace std;
struct point {
    vector<point*> nexts;
    bool flag;
    void scan(int depth, int &max_depth) {
        if(flag) return;
        max_depth = max(max_depth, depth);
        flag = true;
        for(vector<point*>::iterator i=nexts.begin();i!=nexts.end();i++) {
            (*i)->scan(depth + 1, max_depth);
        }
        flag = false;
    }
    point() : nexts(), flag(false) {}
};

int main(int argc, char *argv[], char *envp[])
{
    FILE *in = fopen("input.txt", "r");
    FILE *out = fopen("output.txt", "w");
    int n;
    fscanf(in, "%d", &n);
    vector<point> points(100);
    for(int i=0;i<n;i++) {
        int a;
        int b;
        fscanf(in, "%d %d", &a, &b);
        a--;b--;
        points.at(a).nexts.push_back(&points.at(b));
        points.at(b).nexts.push_back(&points.at(a));
    }
    int max_depth = -1;
    for(vector<point>::iterator i=points.begin();i!=points.end();i++) {
        (*i).scan(1, max_depth);
    }
    fprintf(out, "%d\n", max_depth);
    fclose(in);
    fclose(out);
    return 0;
}

5

以下は失敗した方法。

重なる長方形があるごとに重なりを求めて、係数に-1をかけて追加する。

最悪ケースだとO(2^n)というひどいアルゴリズム。沈没。

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

using namespace std;

struct rect
{
    int x1;
    int y1;
    int x2;
    int y2;
    int factor;
    rect() : factor(1) {}
    bool is_real() {
        return x1<=x2 && y1<=y2;
    }
    rect crossing(const rect &target)
    {
        rect ret;
        ret.factor = this->factor * target.factor;
        ret.x1 = max(this->x1, target.x1);
        ret.y1 = max(this->y1, target.y1);
        ret.x2 = min(this->x2, target.x2);
        ret.y2 = min(this->y2, target.y2);
        return ret;
    }
    void add_to(vector<rect> &rects)
    {
        int rcs = rects.size();
        for(int i=0;i<rcs;i++) {
            rect cr = this->crossing(rects.at(i));
            cr.factor *= -1;
            if(cr.is_real()) {
                rects.push_back(cr);
            }
        }
        rects.push_back(*this);
    }
    int circuit_with_factor()
    {
        return (x2+y2-x1-y1)*2*factor;
    }
    int area_with_factor()
    {
        return (x2-x1)*(y2-y1)*factor;
    }
};

int main(int argc, char *argv, char *envp[])
{
    FILE *in = fopen("input.txt", "r");
    FILE *out = fopen("output.txt", "w");
    int n;
    int r;
    fscanf(in, "%d %d", &n, &r);
    vector<rect> rects;
    for(int i=0;i<n;i++) {
        rect rc;
        fscanf(in, "%d %d %d %d", &rc.x1, &rc.y1, &rc.x2, &rc.y2);
        rc.add_to(rects);
    }
    signed long long int area = 0;
    signed long long int circuit = 0;
    for(vector<rect>::iterator i=rects.begin();i!=rects.end();i++) {
        area += i->area_with_factor();
        circuit += i->circuit_with_factor();
    }
    fprintf(out, "%lld\n", area);
    if(r == 2) {
        fprintf(out, "%lld\n", circuit);
    }
    fclose(in);
    fclose(out);
    return 0;
}

しかたないので解答みて書き直そうとしたが、境界条件まわりで3時間くらい悩んだ。僕の時間を返せ。

解説どおり、縦に分割して双方向連結リストを構築している。

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

using namespace std;

template <typename iter> iter next_iter(iter i){++i;return i;}

int main(int argc, char *argv, char *envp[])
{
    FILE *in = fopen("input.txt", "r");
    FILE *out = fopen("output.txt", "w");
    int n;
    int r;
    fscanf(in, "%d %d", &n, &r);
    list<int> initial_list;
    initial_list.push_back(INT_MIN);
    initial_list.push_back(INT_MAX);
    vector<list<int> > table(10002, initial_list);
    for(int i=0;i<n;i++) {
        int x1,y1,x2,y2;
        fscanf(in, "%d %d %d %d", &x1, &y1, &x2, &y2);
        x1++;x2++;
        for(int x=x1;x<x2;x++) {
            list<int> &line = table.at(x);
            bool cc = true;
            int cs = INT_MIN;
            bool erasing = false;
            for(list<int>::iterator j=line.begin();j!=line.end();j++) {
                if(cc && (cs < y1 && y1 <= *j)) {
                    erasing = true;
                }
                if(!cc && (cs < y1 && y1 <= *j)) {
                    line.insert(j, y1);
                    erasing = true;
                }
                if(cc && (cs <= y2 && y2 < *j)) {
                    erasing = false;
                }
                if(!cc && (cs <= y2 && y2 < *j)) {
                    line.insert(j, y2);
                    erasing = false;
                }
                cc = !cc;
                cs = *j;
                if(erasing) {
                    list<int>::iterator e=j;
                    j--;
                    line.erase(e);
                }
            }
        }
    }
    int area = 0;
    int circuit = 0;
    for(int x=0;x<10002;x++) {
        list<int> &line = table.at(x);
        bool cc = true;
        int cs = INT_MIN;
        for(list<int>::iterator j=line.begin();j!=line.end();j++) {
            if(cc) {
                area += *j - cs;
                if(*j != cs) {
                    circuit += 2;
                }
            }
            cc = !cc;
            cs = *j;
        }
        if(x+1<10002) {
            list<int> &nline = table.at(x+1);
            list<int>::iterator aj=line.begin();
            list<int>::iterator bj=nline.begin();
            while(true) {
                int next0;
                if(bj != nline.end() && (aj == line.end() || *aj >= *bj)) {
                    next0 = *bj;
                    ++bj;
                } else if(aj != line.end() && (bj == nline.end() || *bj > *aj)) {
                    next0 = *aj;
                    ++aj;
                } else {
                    break;
                }
                int next1;
                if(bj != nline.end() && (aj == line.end() || *aj >= *bj)) {
                    next1 = *bj;
                    ++bj;
                } else if(aj != line.end() && (bj == nline.end() || *bj > *aj)) {
                    next1 = *aj;
                    ++aj;
                } else {
                    break;
                }
                circuit += (next1 - next0);
            }
        }
    }
    fprintf(out, "%d\n", area);
    if(r==2) {
        fprintf(out, "%d\n", circuit);
    }
    fclose(in);
    fclose(out);
    return 0;
}

結果

時間：2時間40分くらい
得点：4完 20+20+20+20+4=84(100点中)


この年の本選はかなり簡単な気がするので、あまりよい成績ではないかも。