PKU 1014

JOI予選が近づいてきて，JOI予選の過去問解いてない後輩を煽るためPKUのDP問題解いてます（意味不明）

問題概要

価値が1から6まであるビー玉がある．入力には各々の価値のビー玉の個数が与えられている．二人はビー玉を任意の個数選び，ビー玉の価値を二等分できるかどうか判定する．

 

続きを読む

AOJ 0271: Izua Dictionary

解説

文字列をsとして愚直にシミュレーションしていくと、sを適当に入れ替えたときのi番目(1 <= i <= n)の文字の位置を求めるのに、i番目までに使った文字が影響される。よって最初にBITで[1, n]に1を加えておき、s[i]の場所ごとにiを0にしていくことで、sum(i)でi番目の文字の位置を求めることができる。（日本語難しすぎ）
割とゴリ押しな感じあふれてる。

ソースコード

めっちゃ汚い…

typedef long long i64;
const i64 MOD = 1000000007;
const int MAX_N = 100002;

struct BinaryIndexedTree {
	int data[MAX_N];

	BinaryIndexedTree() {
		memset(data, 0, sizeof data);
	}

	// [1, n]
	i64 sum(i64 i) {
		i64 ret = 0;
		for(; i > 0; i -= i & -i) {
			ret += data[i];
		}
		return ret;
	}

	void add(i64 i, i64 x) {
		for(; i < MAX_N; i += i & -i) {
			data[i] += x;
		}
	}
};

int main() {
	int pair[MAX_N];
	i64 ans;
	i64 fact[MAX_N];
	
	fact[0] = 1;
	for(int i = 1; i < MAX_N; i++) {
		fact[i] = i * fact[i - 1];
		fact[i] %= MOD;
	}

	int n, r;
	while(cin >> n, n) {
		cin >> r;

		ans = 0;
		BinaryIndexedTree b;

		for(int i = 0; i < MAX_N; i++) {
			b.add(i + 1, 1);
			pair[i] = i;
		}

		for(int i = 0, a, b; i < r; i++) {
			cin >> a >> b;
			swap(pair[a-1], pair[b-1]);
		}

		for(int i = 0; i < n; i++) {
			i64 x = b.sum(pair[i] + 1) - 1;
			b.add(pair[i] + 1, -1);
			ans += x * fact[n - i - 1];
			ans %= MOD;
		}

		cout << ans << endl;
	}
}

AOJ 0231 Dangerous Bridge

解法

高々100人の情報しかないので、座標圧縮すると最大でも200回ループ回せば終わる。

ソースコード

struct P {
    int m;
    long long a, b;
};

int n, from[128], to[128], sum[128];
P p[128];

int main() {
    while(scanf("%d", &n) && n) {
        string ans = "OK";
        memset(sum, 0, sizeof sum);
        vector<long long> x;

        for(int i = 0; i < n; i++) {
            scanf("%d%lld%lld", &(p[i].m), &(p[i].a), &(p[i].b));
            x.push_back(p[i].a); x.push_back(p[i].b);
        }

        sort(x.begin(), x.end());
        x.erase(unique(x.begin(), x.end()), x.end());

        for(int i = 0; i < n; i++) {
            from[i] = lower_bound(x.begin(), x.end(), p[i].a) - x.begin();
            to[i] = lower_bound(x.begin(), x.end(), p[i].b) - x.begin();
        }

        for(int i = 0; i < n; i++) {
            for(int j = from[i]; j < to[i]; j++) {
                sum[j] += p[i].m;
            }
        }

        for(int i = 0; i < x.size(); i++) {
            if(sum[i] > 150) {
                ans = "NG";
                break;
            }
        }

        cout << ans << endl;
    }
}

やっと300問…。部活に忙しい毎日…

AOJ 0261 Mayan Crucial Prediction

other

訳

日本語なので省略

解説

  • マヤ暦→西暦

最大でも2016000日を処理するので愚直にループを回せばいける。
あと((((b*20+ka)*20+t)*18+w)*20+ki)とかで求めようとするとバグ埋め込む原因になった（自分の場合は）

  • 西暦→マヤ暦

先に閏年を求めるのでy-2013回ループを回すことになるが、その後は年月日を日数に変換するのにO(1)だしだいたい後の処理も定数がついたO(1)なので大丈夫。
ただオーバーフローに気をつけないと自分みたいにかなり時間を取られる…(糞雑魚)

コード

char s[16];
int month[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

bool leapYear(int y) {
    return (!(y % 4) && (y % 100)) || !(y % 400);
}

char ret[32];

string MayanToAD(void) {
    long long b, ka, t, w, ki, y, m, d;

    sscanf(s, "%lld.%lld.%lld.%lld.%lld", &b, &ka, &t, &w, &ki);

    long long dki = b * 144000 + ka * 7200 + t * 360 + w * 20 + ki;
    if(dki <= 10) y = 2012, m = 12, d = 21 + dki;
    else {
        dki -= 10;
        for(int yy = 2013; ; yy++) {
            for(int mm = 1; mm <= 12; mm++) {
                int tmp = (leapYear(yy) && mm == 2);
                for(int dd = 1; dd <= (month[mm] + tmp); dd++) {
                    dki--;
                    if(dki == 0) {
                        y = yy; m = mm; d = dd;
                        goto end;
                    }
                }
            }
        }
    }

end:;

    sprintf(ret, "%lld.%lld.%lld", y, m, d);
    return ret;
}

string ADToMayan(void) {
    long long y, m, d, b, ka, t, w, ki;
    int leap = 0;

    sscanf(s, "%lld.%lld.%lld", &y, &m, &d);
    for(int i = 2013; i < y; i++) if(leapYear(i)) leap++;

    if(leapYear(y) && m > 2) leap++;

    long long dy = 365 * (y - 2013 <= 0 ? 0 : y - 2013) + leap;

    if(y > 2012) {
        dy += 10;
        for(int i = 1; i <= m; i++)
            if(i == m) dy += d;
            else dy += month[i];
    } else dy = d - 21;

    dy %= 1872000;
    b = dy / 144000; dy %= 144000;
    ka = dy / 7200; dy %= 7200;
    t = dy / 360; dy %= 360;
    w = dy / 20; dy %= 20;
    ki = dy;

    sprintf(ret, "%lld.%lld.%lld.%lld.%lld", b, ka, t, w, ki);
    return ret;
}

int main()
{
    string ans;
    while(cin >> s) {
        if(s[0] == '#')
            break;
        int dn = 0;
        for(int i = 0; i < strlen(s); i++) if(s[i] == '.') dn++;

        if(dn == 2) ans = ADToMayan();
        else ans = MayanToAD();

        cout << ans << endl;
    }
}

閏年もO(1)で求めれるらしい…
経過日数の計算 (アルゴリズムとデータ構造)

Codeforces Round #168 (Div. 2) B. Convex Shape

訳

n*mのグリッドが与えられ、1マスごとに黒色か白色の情報が与えられる。以下の条件を満たすとき凸の図形である。

  • 黒色のマスから隣接する黒色のマスに移動することができ、移動する向きを2回以上変えずに全ての黒色のマスに辿り着くことができる。

与えられたグリッドが凸の図形であればYES、違うのであればNOを出力する。

int n, m;
char panel[64][64];
int check[64][64];
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};
// 0:down 1:right 2:up 3:left

bool isPanel(int y, int x) {
    return 0 <= x && 0 <= y && x < m && y < n;
}

void dfs(int y, int x, int dir, bool c) {
    if(dir == -1) {
        for(int i = 0; i < 4; i++) {
            int nx = x + dx[i], ny = y + dy[i];
            if(isPanel(ny, nx) && panel[ny][nx] == 'B') {
                check[ny][nx] = check[y][x] + 1;
                dfs(ny, nx, i, c);
            }
        }
    } else {
        int nx = x + dx[dir];
        int ny = y + dy[dir];

        if(isPanel(ny, nx) && panel[ny][nx] == 'B' && (check[ny][nx] == 0 || check[y][x] < check[ny][nx])) {
            check[ny][nx] = check[y][x] + 1;
            dfs(ny, nx, dir, c);
        }

        if(c) {

            int othdir = (dir + 1) % 4;
            nx = x + dx[othdir], ny = y + dy[othdir];
            if(isPanel(ny, nx) && panel[ny][nx] == 'B' && (check[ny][nx] == 0 || check[y][x] < check[ny][nx])) {
                check[ny][nx] = check[y][x] + 1;
                dfs(ny, nx, othdir, false);
            }

            othdir = (dir + 3) % 4;
            nx = x + dx[othdir], ny = y + dy[othdir];
            if(isPanel(ny, nx) && panel[ny][nx] == 'B' && (check[ny][nx] == 0 || check[y][x] < check[ny][nx])) {
                check[ny][nx] = check[y][x] + 1;
                dfs(ny, nx, othdir, false);
            }
        }
    }

    return;
}

int main()
{
    cin >> n >> m;
    int sx = 0, sy = 0;
    for(int i = 0; i < n; i++) {
        cin >> panel[i];
    }

    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            if(panel[i][j] == 'B') {
                memset(check, 0, sizeof check);
                check[i][j] = 1;
                dfs(i, j, -1, 1);

                for(int k = 0; k < n; k++) {
                    for(int l = 0; l < m; l++) {
                        if(panel[k][l] == 'B' && !check[k][l]) {
                            puts("NO");
                            return 0;
                        }
                    }
                }
            }
        }
    }

    puts("YES");
}

冷えた。最近ひどいなぁ…

AOJ 0263 Beat Panel

解法

パネルの状態を持ってメモ化再帰。
dp[i][S] := 今譜面iを見てパネルの状態Sのときの最大の獲得得点
勝手に前回使った運指は使わない(SRM?か何かでそんな感じの問題があったような…)という条件を付け足したことで冷え。
パネルの状態はbitとかvectorとかでもてばいける。

int n, c;
int score[30][16], fingering[30][16];
int memo[30][1 << 16];

// p : 現在の譜面 S : 今まで押してないパネルを含めた譜面の状態
int dfs(int p, int S) {
    if(p == n) {
        return 0;
    }

    if(memo[p][S] >= 0)
        return memo[p][S];

    int res = 0;

    for(int i = 0; i < c; i++) {
        int count = 0, next = 0;
        for(int bits = S, j = 0; j < 16; bits >>= 1, j++) {
            if(((bits & 1) || score[p][j]) && fingering[i][j]) {
                count++;
            } else if((bits & 1) || score[p][j]) {
                next += (1 << j);
            }
        }
        res = max(res, dfs(p + 1, next) + count);
    }

    return memo[p][S] = res;
}

int main()
{
    while(scanf("%d%d", &n, &c) && n && c) {

        memset(memo, -1, sizeof memo);

        for(int i = 0; i < n; i++) {
            for(int j = 0; j < 16; j++) {
                scanf("%d", &score[i][j]);
            }
        }

        for(int i = 0; i < c; i++) {
            for(int j = 0; j < 16; j++) {
                scanf("%d", &fingering[i][j]);
            }
        }

        cout << dfs(0, 0) << endl;
    }
}

AOJ 0069 Drawing Lots II

other

方針

制約から全通りシミュレーションしても余裕.
左か右に横線がある場合は置けないので注意する（このコードはテストケースが弱いから通ってしまったが）

ソースコード

#define FOR(i, a, b) for (int i = (a);i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)

int n, m, answer, d;
char maze[32][16];

bool judge()
{
    int point = m - 1;

    for(int i = 0; i < d; i++)
    {
        if(point == 0)
        {
            if(maze[i][point] == '1')
            {
                point += 1;
            }
        }
        else if(point == n - 1)
        {
            if(maze[i][point - 1] == '1')
                point -= 1;
        }
        else
        {
            if(maze[i][point - 1] == '1')
                point -= 1;
            else if(maze[i][point] == '1')
                point += 1;
        }
    }

    if(point == answer)
        return true;

    return false;
}

int main()
{
    while(cin >> n, n)
    {
        scanf("%d%d%d", &m, &answer, &d);
        answer -= 1;

        REP(i, d)
            scanf("%s ", maze[i]);

        if(judge())
            puts("0");
        else
        {
            int x, y;
            bool f = false;
            for(int i = 0; i < d && !f; i++)
                for(int j = 0; j < n - 1 && !f; j++)
                {
                    if(maze[i][j] == '0' && !(maze[i][j - 1] == '1' || maze[i][j + 1] == '1'))
                    {
                        maze[i][j] = '1';
                        if(judge())
                        {
                            f = true;
                            x = j; y = i;
                            break;
                        }
                        maze[i][j] = '0';
                    }
                }
            if(f)
                printf("%d %d\n", y + 1, x + 1);
            else
                puts("1");
        }
    }
}.