codeforces 241 div2

A,B,C略(https://github.com/keroro520/ACM/tree/master/cf/cf%23241)
D.
/*構想問題多if題意:正の整数数列を与えるA.この数列を少なくとも何個の等差数列に分解できるかを聞く.取り外すときは連続しなければならない.(8,𔁛6,𔁛4,𔁛2, 1, 4, 7, 10,𔁛2)を分解すれば、(8, 6, 4, 2),(1,𔁛4,𔁛7,𔁛10),(2)この数列の中に-1が現れ、この位置の数が未知であることを示し、任意の正整数で置き換えることができる.したがって、要求出力-1が置換後、この数列は少なくとも何個の等差数列に分解することができる.分析:難点はai>0が最初に誤った貪欲さを考え、まず一緒にいた-1を合計しなければならない.例えば-1-1は-3を合成する.さらに欲張りは現在のai(ai>0)に対して、できるだけ前の等差数列に属させる.次のステップは、まだ等差数列に分類されていない-xを既知の正の整数からなる等差数列に分類することです.分類できないのはans++ですが、このような貪欲さは次のデータに遭遇するとひざまずいてしまいます:-11 5-17このような貪欲さが間違っていることを意識するとやりやすいので、貪欲に変えましょう.欲張り現在-1ができるだけ前の等差数列に属するように変更するのは簡単で、左から右にスキャンし、pre表の前の数、d公差を記録し、tmp 1/tmp 2はそれぞれpreの前に何個-1があったか、preの後から現在aiまで何個-1があったかを表す.ai>0の場合、(pre,d,tmp 1,tmp 2)に基づいて、現在のaiが前の等差数列に帰すことができるかどうかを見る.ai==1の場合、dが既知であれば、(pre,d)に基づいて、現在の−1がpre+d NAに置き換えられて未知を表すべきであることを決定することができ、例えば、新たに等差数列を開いた場合、dは当然未知である.スキャンを開始したばかりのときと-1で新しい等差数列を開始したときのpreも未知のピットで、intを超えます...*/

#include 
#define		NA	1000000009LL
typedef long long ll;
int n; 
ll a[200005];
int main()
{
	scanf("%d", &n);
	for(int i = 1; i <= n; i++) scanf("%I64d", &a[i]);
	ll pre = NA, d = NA, tmp1 = 0, tmp2 = 0;
	int ans = 1;
	for(int i = 1; i <= n; i++) {
		if(a[i] == -1) {
			if(d == NA) tmp2++;			//d  ，      -1      
			else {
				if(pre + d <= 0) {		//          ，    ，       -1  ，  pre = NA
					pre = d = NA, tmp2 = 1, tmp1 = 0, ans++;
				} else pre += d;		//  -1           ，-1   pre+d
			}
		} else {
			if(pre == NA) pre = a[i]; tmp1 = tmp2, tmp2 = 0;		//     ai>0，   tmp1 = tmp2
			else {
				if(d == NA) {
					if((a[i] - pre) % (tmp2 + 1) == 0) {
						d = (a[i] - pre) / (tmp2 + 1);
						if(1 + tmp1 * d <= pre) tmp1 = tmp2 = 0, pre = a[i];
						else d = NA, pre = a[i], tmp1 = tmp2 = 0, ans ++;
					} else {
						d = NA, pre = a[i], tmp1 = tmp2 = 0, ans ++;
					}
				} else {
					if(pre + d == a[i]) pre = a[i];
					else d = NA, pre = a[i], tmp1 = tmp2 = 0, ans ++;
				}
			}
		}
	}
	printf("%d
", ans);
	return 0;
}

E.
/*図論最短題意:帯辺権図がなく、任意の2点の間に最大1つの辺がある.すべての点対s->tの最も多重化されたすべての辺数を出力することが要求される.この問題の解き方はすばらしいと思います.n*n*mのTLEを書いて、長い間できないことを考えて、大牛のコードを見て、自分で理解しました.[*]まずFloydはすべての(s,t)の最短ルートを求めます//私は当初n*dijstraがどれだけの死をしたかを書いて、確かにFloydより複雑度が低下しているとはいえ[*]計算cnt[i][j]はi->jの最短路にiの隣接辺が何本あるかを示している[*]最後のi->jの最短路を通過する辺数ans[i][j]はi->jの最短路のすべての点kのcnt[k][j]の和に等しく、cnt[i][j]のような表現をどのように考えているのだろうか.教えて下さい!*/

#include 
#include 
#include 
using namespace std;
#define		MAXN		505
int e[MAXN][MAXN], dist[MAXN][MAXN], cnt[MAXN][MAXN];
int n, m;

int main()
{
	scanf("%d %d", &n, &m);

	memset(dist, 0x3F, sizeof dist);
	for(int i = 1; i <= n; i++) dist[i][i] = 0;
	for(int i = 0; i < m; i++) {
		int u, v, w;
		scanf("%d %d %d", &u, &v, &w);
		e[u][v] = e[v][u] = dist[u][v] = dist[v][u] = w;
	}

	for(int k = 1; k <= n; k++)
		for(int i = 1; i <= n; i++)
			for(int j = 1; j <= n; j++)
				dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);

	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= n; j++) if(e[i][j]) {
			for(int k = 1; k <= n; k++)
				if(e[i][j] + dist[j][k] == dist[i][k]) cnt[i][k]++;
		}

	for(int i = 1; i <= n; i++)
		for(int j = i+1; j <= n; j++) {
			int ans = 0;
			for(int k = 1; k <= n; k++)
				if(dist[i][k] + dist[k][j] == dist[i][j])
					ans += cnt[k][j];
			printf("%d ", ans);
		}
	puts("");
	return 0;
}