JOI 予選模擬(2012-2013) 解説

ずっと書こうと思っていたのですが, 中途半端にしかスライドが出来ていなかったので, ブログに解説を載せます.
たぶん今年も模擬予選します. 誰か一緒にwriter しましょう～.

問題はコチラ からみれます.

[1] 漫画 (Comics)
毎年の1 問目と同じ傾向です.
直前の日に読んだ続きから読むため, 読んだページ数はあらかじめ足しておいていいです.

最後まで読み切った冊数は, (1週間で読んだ総ページ数 / 200) の整数部分となります.

コード :

#include <cstdio>

using namespace std;

int main()
{
	int n;
	int s;
	
	s = 0;
	for (int i = 0; i < 7; i++){
		scanf("%d", &n);
		s += n;
	}
	
	printf("%d\n", 10 - (s / 200));
	
	return (0);
}

[2] 採点 (Grading)
入力の終わりが分からないので, 式に現れる記号をうまく活用しましょう.
最初には必ず数字がくるので足してしまいます. その後は,

'+' -> 次の項を足す.
'-' -> 次の項を引く.
'=' -> 次の項と今の和を比較する.

でうまく判定できます.

コード :

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

using namespace std;

int main()
{
	int n, k;
	
	scanf("%d %d", &n, &k);
	
	for (int i = 0; i < n; i++){
		int res = 0;
		for (int j = 0; j < k; j++){
			int sum = 0;
			int sign = 0;
			int tval;
			char top[4];
			while (scanf("%d %s", &tval, top) && top[0] != '='){
				sum += sign ? -tval : tval;
				sign = top[0] == '-';
			}
			sum += sign ? -tval : tval;
			scanf("%d", &tval);
			res += sum == tval;
		}
		printf("%d\n", res);
	}
	
	return (0);
}

[3] 家庭菜園 2 (Garden 2)
どこかの問題と最初の1 文は一緒だったりします. 想定していたよりも解かれていました.
さて, どの雑草も必ず1 cm ずつ伸びるので,草の長さは最初の長さのままで考えてよい事が分かります.
最初のままで切るのであれば, もっとも短いもの以外には合わせようが無いので(短いものより短くすると, N cm だけ無駄が生じるので), すべてを短いものに揃えるのが草を切る量の総和を最小にします.
もっとも短いものをO(N) 時間で見つけると O(N) 時間でこの問題が解けますが, ソートをしてO(N^2), O(N log N) としてもまったく問題ありません.

コード

#include <cstdio>
#include <algorithm>

using namespace std;

int main()
{
	int N;
	int a[10000];  //当初のN の予定
	int time, cost;
	
	scanf("%d", &N);
	
	for (int i = 0; i < N; i++){
		scanf("%d", a + i);
	}
	
	sort(a, a + N);
	
	time = 0;
	cost = 0;
	for (int i = 1; i < N; i++){
		time += (a[0] != a[i]);
		cost += a[i] - a[0];
	}
	
	printf("%d %d\n", cost, time);
	
	return (0);
}

[4] 人権 (Human Rights)
毎年, 問4 ではDP(動的計画法) を用いる問題が出ていて, ある程度応用が効かないと対処出来ないようになっています. 問4 が解ければ予選は容易に通過できる(本選もDP 次第だったり)ので, 予選の人権ラインなんですネ.

さて, この問題ももちろんDP で解きます.具体的には,
dp[i][j] : i 番目の席まででj 匹のミズゴロウが座る方法.

とすると,
dp[0][0] = 1;
dp[i][j] = dp[i - 1][j] + dp[i - 2][j - 1];

のような形で求まります. 席が壊れている状態などは慎重に処理しましょう.

解答例ではメモ化再帰をしていますが, DP も同じように書き直せます.

コード :

#include <stdio.h>
#include <string.h>

int ng[3003];
int memo[3003][3003];
int n, m, k;

int getNum(int pos, int rem)
{
    if (memo[pos][rem] >= 0){
        return (memo[pos][rem]);
    }
	
	if (rem == 0){
		return (1);
	}
	
	if (pos >= m){
		return (0);
	}
    
    return (memo[pos][rem] = (getNum(pos + 1, rem) + (ng[pos] ? 0 : getNum(pos + 2, rem - 1))) % 100000);
}

int main(void)
{
	int i;
	
    scanf("%d %d %d", &n, &m, &k);
    
	for (i = 0; i < k; i++){
		int in;
		scanf("%d", &in);
		ng[--in] = 1;
	}
	
    memset(memo, -1, sizeof(memo));
    
    printf("%d\n", getNum(0, n));
    
    return (0);
}

[5] カウンター (Counter)
問題の設定は昨年度の高専プロコンからです. 大変でした.
この問題では, 幅優先探索をM 回行います. やや特殊な状態遷移が出きるかを確かめる問題のつもりでしたが, O(M*10^N) はなかなか遅いですね...
もっと早い解があると思っていたのですが, 見つけられませんでした.

コード :

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

using namespace std;

int base;
bool vis[1000000];

int gen(int no)
{
	int ch = no * 10 / base;
	int ret = 0;
	
	for (int i = base / 10; i > 0; i /= 10){
		int digit = (no / i) % 10;
		if (digit == ch) digit = (digit + 1) % 10;
		ret = ret * 10 + digit;
	}
	
	return (ret);
}

int query(int s, int t)
{
	queue<pair<int, int> > q;
	memset(vis, 0, sizeof(vis));
	
	q.push(make_pair(s, 0));
	
	while (!q.empty()){
		pair<int, int> now = q.front(); q.pop();
		
		if (now.first == t){
			return (now.second);
		}
		
		pair<int, int> next = now;
		next.second++;
		
		next.first = (now.first + 1) % base;
		if (!vis[next.first]){
			vis[next.first] = true;
			q.push(next);
		}
		
		next.first = gen(now.first);
		if (!vis[next.first]){
			vis[next.first] = true;
			q.push(next);
		}
	}
	
	return (-1);
}

int main()
{
	int n, m;
	
	scanf("%d %d", &n, &m);
	getchar();
	base = 1;
	
	for (int i = 0; i < n; i++) base *= 10;
	
	for (int i = 0; i < m; i++){
		int a, b;
		scanf("%d %d", &a, &b);
		printf("%d\n", query(a, b));
		getchar();
	}
	
	return (0);
}

[6] シャッフル 2012 (Shuffle 2012)
もともとはセットの概念が無く, 繰り返している途中で終わったらそれを出力する問題でした(入力例2 なら答えは2 になります.)
さて, セットを1 回繰り返した結果, カード列{1,2,...,n}が{a1,a2,...,an} になっていたとします.
これは, a1 番目のカードが1 番目に, a2 番目のカードが2 番目に, ..., an 番目のカードがn 番目に来た, ということを表します.
ここで, a_a1 番目のカード, a_a_a1 番目のカード, と言う風にたどっていくと, いつかは必ず1 に戻ることが示せます. (背理法なりなんなり)
したがって, いくつかのカードのグループができ, それらはその枚数で循環して入れ替わることが分かります(入力例のそれぞれのセットについて, 最後のシャッフルのだけ眺めてみましょう).
ゆえに, 答えは1 回シャッフルをしたあとに, グループの大きさの最小公倍数をとることで求めることができ, 計算量はO(MN) となります.

コード

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

#define MAX_N (10000)

typedef long long lint;

using namespace std;

lint gcd(lint a, lint b)
{
	return (!b ? a : gcd(b, a % b));
}

lint lcm(lint a, lint b)
{
	if (a < b) swap(a, b);
	return (a / gcd(a, b) * b);
}

int main()
{
	int n, m;
	int t;
	static int dat[MAX_N], next[MAX_N];
	static bool vis[MAX_N];
	
	scanf("%d %d", &n, &m);
	
	for (int i = 0; i < n; i++){
		dat[i] = i;
	}
	
	t = 0;
	for (int r = 1; r <= m; r++){
		int q;
		scanf("%d", &q);
		if (q == 1){
			for (int i = 0; i < n / 2; i++){
				next[i * 2] = dat[i + (n / 2)];
				next[i * 2 + 1] = dat[i];
			}
			memcpy(dat, next, sizeof(next));
		}
		else if (q == 2){
			reverse(dat, dat + n);
		}
		else {
			int k;
			scanf("%d", &k);
			for (int i = 0; i < k; i++){
				next[i + n - k] = dat[i];
			}
			for (int i = 0; i < n - k; i++){
				next[i] = dat[k + i];
			}
			memcpy(dat, next, sizeof(next));
		}
		bool flag = true;
	}
	
	lint ans = 1;
	
	for (int i = 0; i < n; i++){
		lint ct = 0;
		int idx = i;
		while (!vis[idx]){
			vis[idx] = true;
			idx = dat[idx];
			ct++;
		}
		if (ct) ans = lcm(ans, ct);
	}
	
	printf("%lld\n", ans);
	
	return (0);
}