Codeforces Round #194 Div1B Chips

問題

N*Nのセルがあります。
その上にM個の落とし穴があります。

隅以外の端のセルにいくつかチップを置いて、チップを逆サイドの端まで（つまり、上下または左右に）、１ターンに１マスずつ動かします。このとき、どこかのターンであるチップが

・落とし穴のセルに止まる。
・縦から来たやつと横から来たやつとかで、同じセルに止まる。
・逆サイドから来たチップとすれちがう。

のどれかになるとダメです。
このルールを守りながら、最大何個のチップを端から端まで動かすことができるでしょう？

制約
2 ≤ n ≤ 1000, 0 ≤ m ≤ 10^5

解法
ある列（行）に落とし穴があるかどうかは、落とし穴入力を読みながらダメな列・行を増やしていく感じで簡単に割り出せそうなので、
（落とし穴がない行・列の数）-（全部通しちゃうとどうしてもどこかで同じセルに止まってしまう組み合わせ）
が答えになりそうです。
しかし、この「どうしても同じセルに止まっちゃう」というやつ、実はチップのスタート地点をどっちサイドにするかをうまく決めればそうそう簡単には起こりません。

下の図をご覧ください。

たとえ落とし穴ゼロと仮定して全部の行と列にチップを走らせるとしても、
このように半分のところでどっちサイドから動いていくかを変えることで、実は（Nが奇数の時の真ん中以外）誰も重なることはありません。

というわけで、落とし穴がないところを求めて、あとはNが奇数の場合だけ真ん中の条件を気を付ければOKです。
コーディング自体はDiv2B問題レベルですね。

プログラム

#include<iostream>
#include <fstream>
#include <stdio.h>
#include <stdlib.h>
#define _USE_MATH_DEFINES
#include <math.h>
#include<string>
#include<vector>
#include<cmath>
#include<stack>
#include<queue>
#include<sstream>
#include<algorithm>
#include<map>
#include<complex>
using namespace std;


#define li			long long int
#define rep(i,to)	for(int i=0;i<((int)(to));i++)
#define repp(i,start,to)	for(int i=(int)(start);i<((int)(to));i++)
#define pb			push_back
#define sz(v)		((li)(v).size())
#define bgn(v)		((v).begin())
#define eend(v)		((v).end())
#define allof(v)	(v).begin(), (v).end()
#define dodp(v,n)		memset(v,(li)n,sizeof(v))
#define bit(n)		(1ll<<(li)(n))
#define mp(a,b)		make_pair(a,b)
#define rin	rep(i,n)
#define EPS 1e-10
#define ETOL 1e-8
#define MOD 1000000007
#define p2(a,b)		cout<<a<<"\t"<<b<<endl
#define p3(a,b,c)		cout<<a<<"\t"<<b<<"\t"<<c<<endl


int main(){
	li n,m;
	cin>>n>>m;
	
	bool ok[1000][2];
	rep(i,1000)rep(j,2)ok[i][j]=true;
	rep(i,2){
		ok[0][i]=false;
		ok[n-1][i]=false;
	}
	
	li x,y;
	rep(i,m){
		cin>>x>>y;
		ok[x-1][0]=false;
		ok[y-1][1]=false;
	}
	
	li res=0;
	rin{
		if(ok[i][0])res++;
		if(ok[i][1])res++;
	}
	if(n%2==1 && ok[n/2][0] && ok[n/2][1])res--;
	cout<<res<<endl;
	
	return 0;
}