情報オリンピック参加記

Programming JOI
  • 開始早々サーバーが激重で問題を開くのに15分以上かかった。結局18時までに延長となった。
    • SSLを使うようになってた他、内部システムをいろいろ変更しているようなので、まあいろいろあったんだろう。
    • 見たかんじ、ブラウザから定期的にサーバーにアクセスがあるようだ(デジタル時計画像のせいか)。これが原因なんじゃないかと。どうせ一台Apacheが走ってるだけみたいなあまり強くないサーバーなんだから無理しなけりゃいいのに。
    • こういうこと(短期的に大量のアクセスがある)こそクラウドでやるべきだという話を聞いた。確かに。
  • 問題ダイジェスト
    • 1:やるだけ
    • 2:やるだけ
    • 3:DFS/BFSでもよいが、普通に2重ループ。
    • 4:nPk個を列挙して配列に流しこんだあとsortして数える。
    • 5:2×W×HでDP。めんどい。
    • 6:DFSだと部分点。2^N×N(訪問済みの頂点パターンと、現在の頂点)でDPする。めんどい。
    • というわけで今年はDPが2問である。DPは作問の題材として美味しすぎるのだろう。
    • そんなわけで、DPが出来ると出来ないでは雲泥天地ツンデレの差である。DeredereProgramming。
  • 自分的には満点なのだが、いつも通りケアレスミスが心配でドキドキハァハァしている。
    • 今回はC++を使ったが、STLを極力使わないようにしてみた。結局、使ったSTLはalgorithm(sort)を一回のみ、他のライブラリとしてはcstdio(printf,scanf)とcstring(memset)、それからstdlib(malloc)を一度使っただけで済んだ。さすが、よくできている。
  • 僕的にJOIやSuperConが好きな理由の一つは、問題がよく考えられていて有り難みがあるというか、解いてて幸せな気分になれる。

以下C++ソース。

/*
 * joi2010yo
 * NAME: Masaki Hara
 * LANG: C++
 * PROB: t1
 */

#include <cstdio>

using namespace std;

int main(int argc, char **argv)
{
    int s = 0;
    for(int i = 0; i < 10; ++i) {
        int n;
        scanf("%d", &n);
        i == 0 ? (s+=n) : (s-=n);
    }
    printf("%d\n", s);
    return 0;
}

/*
 * joi2010yo
 * NAME: Masaki Hara
 * LANG: C++
 * PROB: t2
 */

#include <cstdio>

using namespace std;

int tbl[1010];
int main(int argc, char **argv)
{
    int n,m;
    scanf("%d%d", &n, &m);
    for(int i = 0; i < n; ++i) {
        scanf("%d", &tbl[i]);
    }
    int cur = 0;
    for(int i = 0; i < m; ++i) {
        int t;
        scanf("%d", &t);
        cur += t;
        if(cur >= n-1) {
            printf("%d\n", i+1);
            return 0;
        }
        cur += tbl[cur];
        if(cur >= n-1) {
            printf("%d\n", i+1);
            return 0;
        }
    }
    return 0;
}

/*
 * joi2010yo
 * NAME: Masaki Hara
 * LANG: C++
 * PROB: t3
 */

#include <cstdio>
#include <cstring>

/* "He's my friend, but I'm not his friend." always happens. */

using namespace std;

bool mat[500][500];
bool flags[500];

int main(int argc, char **argv)
{
    memset(mat, 0, sizeof(mat));
    memset(flags, 0, sizeof(flags));
    int n,m;
    scanf("%d%d", &n, &m);
    for(int i = 0; i < m; ++i) {
        int a,b;
        scanf("%d%d", &a, &b);
        mat[a-1][b-1]=mat[b-1][a-1]=true;
    }
    for(int i = 0; i < n; ++i) {
        if(mat[0][i]) {
            flags[i] = true;
            for(int j = 0; j < n; ++j) {
                if(mat[i][j]) {
                    flags[j] = true;
                }
            }
        }
    }
    flags[0] = false;
    int cnt = 0;
    for(int i = 0; i < n; ++i) {
        if(flags[i])cnt++;
    }
    printf("%d\n", cnt);
    return 0;
}

/*
 * joi2010yo
 * NAME: Masaki Hara
 * LANG: C++
 * PROB: t4
 */

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

int n,k;
int a[10000];
int i;
int cards[10];
bool cuse[10];

void search(int num, int d) {
    if(d == k) {
        a[i++] = num;
        return;
    }
    for(int j = 0; j < n; ++j) {
        if(!cuse[j]) {
            cuse[j]=true;
            search(
                    cards[j]<10 ? (num*10+cards[j]) : (num*100+cards[j])
                    , d+1);
            cuse[j]=false;
        }
    }
}

int main(int argc, char **argv)
{
    scanf("%d%d", &n, &k);
    for(int j = 0; j < n; ++j) {
        scanf("%d", &cards[j]);
    }
    i = 0;
    memset(cuse, 0, sizeof(cuse));
    search(0, 0);
    sort(&a[0], &a[i]);
    int prev = -1;
    int cnt = 0;
    for(int j = 0; j < i; ++j) {
        if(prev != a[j]) cnt++;
        prev = a[j];
    }
    printf("%d\n", cnt);
    return 0;
}

/*
 * joi2010yo
 * NAME: Masaki Hara
 * LANG: C++
 * PROB: t5
 */

#include <cstdio>

using namespace std;

template<int m>
class mint
{
private:
    int i;
public:
    mint() : i(0){}
    mint(int i): i((i%m+m)%m){}
    mint operator+(const mint& o){return o.i+i;}
    mint operator*(const mint& o){return o.i*i;}
    mint operator-(){return -i;}
    operator int() {return i;}
};

typedef mint<100000> mmint;

mmint tbl[100][100][2];

int main(int argc, char **argv)
{
    int w,h;
    scanf("%d%d", &w, &h);
    for(int x = 0; x < w; ++x) {
        for(int y = 0;y < h; ++y) {
            mmint a = x-1>=0 ? tbl[x-1][y][0] : (mmint)0;
            mmint b = x-2>=0 ? tbl[x-2][y][1] : (mmint)0;
            mmint c = y-1>=0 ? tbl[x][y-1][1] : (mmint)0;
            mmint d = y-2>=0 ? tbl[x][y-2][0] : (mmint)0;
            tbl[x][y][0] = a+b;
            tbl[x][y][1] = c+d;
            if(x==1 && y==0) {
                tbl[x][y][0] = 1;
                tbl[x][y][1] = 0;
            } else if(x==0 && y==1) {
                tbl[x][y][0] = 0;
                tbl[x][y][1] = 1;
            }
        }
    }
    mmint sum = tbl[w-1][h-1][0] + tbl[w-1][h-1][1] +
        tbl[w-1][h-2][0] + tbl[w-2][h-1][1];
    printf("%d\n", (int)sum);
    return 0;
}

/*
 * joi2010yo
 * NAME: Masaki Hara
 * LANG: C++
 * PROB: t6
 */

/* There's no christmas! */

#include <cstdio>
#include <cstring>
#include <cstdlib>

using namespace std;

int w,h;
int tbl[10][10];
int htbl[10][10];
/* int dp[1<<24][24];*/
int (*dp)[24];
int hxs[24];
int hys[24];
int main(int argc, char **argv)
{
    scanf("%d%d", &w, &h);
    /* memset(dp, 0, sizeof(dp)); */
    int hcnt = 1;
    for(int y = 0; y < h; ++y) {
        for(int x = 0; x < w; ++x) {
            scanf("%d", &tbl[x][y]);
            htbl[x][y] = -1;
            if(tbl[x][y] == 1) {
                htbl[x][y] = hcnt++;
                hxs[htbl[x][y]]=x;
                hys[htbl[x][y]]=y;
            } else if(tbl[x][y] == 2) {
                htbl[x][y] = 0;
                hxs[htbl[x][y]]=x;
                hys[htbl[x][y]]=y;
            }
        }
    }
    dp = (int(*)[24])malloc(sizeof(*dp)*(1<<hcnt));
    memset(dp, 0, sizeof(*dp)*(1<<hcnt));
    dp[0][0] = 1;
    for(int state = 0; state < (1<<hcnt); ++state) {
        for(int cur = 0; cur < hcnt; ++cur) {
            if(!(state==0 && cur==0) && (state&(1<<cur)) == 0)continue;
            int x=hxs[cur];
            int y=hys[cur];
            for(int i = 1; x+i<w ; ++i) {
                int htcur=htbl[x+i][y];
                if(htcur>=0 && state&(1<<htcur))break;
                if(htcur>=0)dp[state|(1<<htcur)][htcur] += dp[state][cur];
            }
            for(int i = 1; x-i>=0 ; ++i) {
                int htcur=htbl[x-i][y];
                if(htcur>=0 && state&(1<<htcur))break;
                if(htcur>=0)dp[state|(1<<htcur)][htcur] += dp[state][cur];
            }
            for(int i = 1; y+i<h ; ++i) {
                int htcur=htbl[x][y+i];
                if(htcur>=0 && state&(1<<htcur))break;
                if(htcur>=0)dp[state|(1<<htcur)][htcur] += dp[state][cur];
            }
            for(int i = 1; y-i>=0 ; ++i) {
                int htcur=htbl[x][y-i];
                if(htcur>=0 && state&(1<<htcur))break;
                if(htcur>=0)dp[state|(1<<htcur)][htcur] += dp[state][cur];
            }
        }
    }
    printf("%d\n",dp[(1<<hcnt)-1][0]);
    free(dp);
    return 0;
}