2019-08-11

情報オリンピック2011年本選

情報オリンピック2011年本選の公式解説がないから作ろうとしている。
全体的にかなり怪しいため、仮公開にとどめる（第5問の二分探索解って単調性示せなきゃ無理だよな）
final2011.pdf - Google ドライブ
 final2011.tex - Google ドライブ

2019-04-27

Project Euler 301 Nim

Problem 301 - Project Euler

個人的に面白かった。競技プログラミングのいろいろなカテゴリの基本ができていますか、っていう問題でした。
TeXの復習がてら解説を書いてみました。
(2019/5/1追記)式(3)を出すときにギャップがあるように見えるので注意

https://drive.google.com/open?id=1KDRBT4T72HYgTL7hmwiADhyS-GzwKvZY

2019-04-21

Project Euler Problem 323 Bitwise-OR operations on random integers

Problem 323 - Project Euler

たぶんこいつ期待値とかあんまりわかってないんだよなー
f:id:utsumi_p:20190421215345j:plain
こういうことだとおもう

2018-12-16

AGC029-A irreversible operation

解法はみんな書いてるので、最も答えの値が大きくなるのはどんな場合か考えてみましょう。

まず白い石の個数Xを固定したときに、白い石と黒い石を交換できる回数が最も多くなるような石の配置を考えます。
これは白い石がすべて右詰めで置かれている場合です。

次に、Xの値と|S|の値がどのような関係にあると、答えの値が最大になるかを考えます。
白い石がすべて右詰めに置かれているとき、交換回数の最大値は (黒い石の個数)×(白い石の個数)=(|S| - X) × X で表されます。
あとは二次関数とか相加相乗平均とかを使えば、答えの値が最大になるのは X = |S| / 2 のときであることが分かります。
(|S|が奇数のときは X = (|S| + 1) / 2 または (|S| - 1) / 2)

今回の問題では |S| ≦ 200000という制約があったので、最も答えの値が大きくなるのは|S| = 200000、 ('W'の個数) = 100000、 ('B'の個数) = 100000 で、すべての'W'がすべての'B'より右側に置かれている場合であり、答えは(200000 - 100000) * 100000 = 10^10となります。

C++のint型では2^32 ≅ 10^9までしか表せないので、オーバーフローの要因となります。この問題では long int などを用いましょう。
(12/18訂正)2^32 ではなく 2^32 - 1までです

2018-10-16

Aizu Online Judge 2200 Mr. Rito Post Office

へーあんたも離島っていうんだー（バカかお前）
陸路のみと海路のみのそれぞれのグラフにワーシャルフロイドかけてから、memo[i][j]:=島jに船を置いた状態でi番目の島を訪れたときの最短距離でdp（拡張ダイクストラ法も時間があればまた）

#include<cstdio>
#include<algorithm>
using namespace std;
static const int MAX_N = 200;
static const int MAX_R = 1000;
static const int INF = 1 << 20;
 
int N, M;
int x, y, t; char sl;
int R;
int z[MAX_R];
 
int dist1[MAX_N][MAX_N], dist2[MAX_N][MAX_N];
int memo[MAX_R][MAX_N];
 
int main(){
    for(;;){
        scanf("%d %d", &N, &M);
        if(N == 0 && M == 0) break;
        for(int i = 0; i < N; i++){
            for(int j = 0; j < N; j++){
                if(i == j){
                    dist1[i][j] = 0;
                    dist2[i][j] = 0;
                }else{
                    dist1[i][j] = INF;
                    dist2[i][j] = INF;
                }
            }
        }
        for(int i = 0; i < M; i++){
            scanf("%d %d %d %c", &x, &y, &t, &sl);
            x--; y--;
            if(sl == 'L'){
                dist1[x][y] = min(dist1[x][y], t);
                dist1[y][x] = min(dist1[y][x], t);
            }else if(sl == 'S'){
                dist2[x][y] = min(dist2[x][y], t);
                dist2[y][x] = min(dist2[y][x], t);
            }
        }
        for(int k = 0; k < N; k++){
            for(int i = 0; i < N; i++){
                for(int j = 0; j < N; j++){
                    if(dist1[i][j] > dist1[i][k] + dist1[k][j]) dist1[i][j] = dist1[i][k] + dist1[k][j];
                    if(dist2[i][j] > dist2[i][k] + dist2[k][j]) dist2[i][j] = dist2[i][k] + dist2[k][j];
                }
            }
        }
        scanf("%d", &R);
        for(int i = 0; i < R; i++){
            scanf("%d", &z[i]);
            z[i]--;
        }
        fill(memo[0], memo[R], INF);
        for(int i = 0; i < R; i++){
            for(int j = 0; j < N; j++){
                if(i == 0){
                    if(j == z[i]) memo[i][j] = 0;
                }else{
                    memo[i][j] = min(memo[i][j], min(memo[i - 1][j] + dist1[z[i - 1]][z[i]], INF));
                    for(int k = 0; k < N; k++){
                        memo[i][k] = min(memo[i][k], min(memo[i - 1][j] + dist1[z[i - 1]][j] + dist2[j][k] + dist1[k][z[i]], INF));
                    }
                }
            }
        }
        int res = INF;
        for(int i = 0; i < N; i++) res = min(res, memo[R - 1][i]);
        printf("%d\n", res);
    }
    return 0;
}

2018-10-13

Codeforces Round #515(div.3)

結果は2完。まあ収穫はあったと思って諦めるしかない
追記：A問題は下のリンク先のように実装した方が楽です。
http://codeforces.com/contest/1066/submission/44251054

A問題は僕がよく引っかかる区間の問題。no submitも考慮したが、それでもシンプルに書く方法だけは考える。半開区間の端点上にvの倍数があった場合の切り上げ、切り捨ての扱いに気をつけ、次のコードでAC

#include<cstdio>
using namespace std;
typedef long long int ll;

int t;

int main(){
	scanf("%d", &t);
	for(int i = 0; i < t; i++){
		int L, v, l, r;
		scanf("%d %d %d %d", &L, &v, &l, &r);
		int O = 1;
		L -= L % v;
		r -= r % v;
		l += (l % v == 0 ? 0 : v - (l % v));
		O += (O % v == 0 ? 0 : v - (O % v));
		printf("%d\n", (L - r) / v + (l - O) / v);
	}
	return 0;
}

B問題は貪欲。いろいろと実装ミスもあったが、一番痛いのは前にあるヒーターからチェックしていったこと。
これだと"5 2\n1 1 1 1 1"のようなケースで3などと出力するので、「暖まっていない部屋があったら、その部屋から(indexが増える方向に)なるべく遠くにあるヒーターを付ける」方針にすべき。

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long int ll;

int n, r;
int a[1100];
bool visited[1100];
bool need[1100];

int main(){
	scanf("%d %d", &n, &r);
	for(int i = 0; i < n; i++) scanf("%d", &a[i]);
	fill(visited, visited + n, false);
	fill(need, need + n, false);

	for(int i = 0; i < n; i++){
		if(!visited[i]){
			for(int j = min(n - 1, i + r - 1); j >= max(0, i - r + 1); j--){
				if(a[j] == 1){
					need[j] = true;
					for(int k = max(0, j - r + 1); k <= min(n - 1, j + r - 1); k++) visited[k] = true;
					break;
				}
			}
		}
	}
	int res = 0;
	for(int i = 0; i < n; i++){
		if(!visited[i]){
			printf("-1\n");
			return 0;
		}
		if(need[i]) res++;
	}
	printf("%d\n", res);
	return 0;
}

2018-10-07

Educational Codeforces Round 51 D Bicolorings

おもしろかった。情報オリンピックで出そう。
http://codeforces.com/contest/1051/problem/D
memo[i][j][k] : j 列目のタイルを形式iで塗ったときにコンポーネントがk個になる場合の数
ここで、形式iとは
形式0:1行目白, 2行目白
形式1:1行目白, 2行目黒
形式2:1行目黒, 2行目白
形式3:1行目黒, 2行目黒
これはビットをうまく使えば簡単に表現できるかも知れない

#include<cstdio>
using namespace std;
typedef long long int ll;
static const int MAX_N = 1000;
static const int MAX_K = 2 * MAX_N;
static const ll MOD = 998244353;

int n, k;
ll memo[4][MAX_N][MAX_K + 1];

int main(){
	scanf("%d %d", &n, &k);
	for(int i = 0; i < n; i++){
		if(i == 0){
			memo[0][i][1]++;
			memo[1][i][2]++;
			memo[2][i][2]++;
			memo[3][i][1]++;
		}else{
			for(int j = 1; j <= k; j++){
				if(j == 1){
					memo[0][i][j] += memo[0][i - 1][j];
					memo[3][i][j] += memo[3][i - 1][j];
				}else{
					memo[0][i][j] += memo[0][i - 1][j] + memo[1][i - 1][j] + memo[2][i - 1][j] + memo[3][i - 1][j - 1];
					memo[1][i][j] += memo[0][i - 1][j - 1] + memo[1][i - 1][j] + memo[2][i - 1][j - 2] + memo[3][i - 1][j - 1];
					memo[2][i][j] += memo[0][i - 1][j - 1] + memo[1][i - 1][j - 2] + memo[2][i - 1][j] + memo[3][i - 1][j - 1];
					memo[3][i][j] += memo[0][i - 1][j - 1] + memo[1][i - 1][j] + memo[2][i - 1][j] + memo[3][i - 1][j];
				}
				for(int l = 0; l < 4; l++) memo[l][i][j] %= MOD;
			}
		}
	}
	ll res = 0;
	for(int i = 0; i < 4; i++){
		res += memo[i][n - 1][k];
		res %= MOD;
	}
	printf("%lld\n", res);
	return 0;
}