純粋培養競技プログラマが基本情報技術者試験を解いてみた話

こんにちは。たまには有機的な投稿をします、DEGwerです。

twitter基本情報技術者試験、というものが話題に上がっていたので、過去問を解いてみることにしました。

  • 筆者紹介

大学3年。中学3年のときに競技プログラミングを始める。開発経験なし、開発意思なし。競技プログラミング以外の用途でプログラムを書かない。
パソコンの中のことやネットワークのことについて勉強したことはなし。離散最適化に興味あり。

  • 使用した問題

http://www.fe-siken.com/kakomon/29_haru/
ここに上がっている、平成29年度春の午前試験を解きました。

  • 結果

50問正解/80問 です。ボーダーが6割らしいので、ぎりぎり合格です。

  • 感想

問題のpdfを開くと、そこはセンター試験であった。(「雪国」風に)

センター試験ももう二年半も前なので、この選択肢の文章の雰囲気に懐かしさを覚える。というか80問もあるやんけ!制限時間2時間半なのか、思ったより長い。
どんな問題が出るかも全く知らないので、わくわくしながら進む。Excelの使い方、とか出るのかなぁ。

センター試験のノウハウが残っているので、とりあえず5つずつに回答欄を区切っていく。序盤。問題文に答えが書いてある系の問題がたくさんと意味不明な単語が並んでいる問題が少しある。
ここでマークがずれる。キレました。

マークミスを直して続ける。意味不明な単語が増えてくる。アルファベット略語やめろ、頼むから漢字で書いてくれ。英語ネイティブもさすがに頭文字の情報だけじゃ何のことかさっぱりだと思うんだけど、よくあんなに大量の3文字略語が覚えられるなぁ。

カタカナ語も増えてくる。意識高い系意味不明文章の雰囲気に目がやられる。俺は日本人だ、頼むから日本語で書いてくれ、カタカナが10文字くらい連続するとお経の送り仮名か何かにしか見えない。カタカナを作った人もまさかこんな十何文字にもわたる送り仮名の延々と続く文章に使われるようになるとは露にも思わなかっただろうに。というかせめて英単語をそのまま書いてくれればまだ読む気がするんだよね。あのカタカナとかいう平べったい文字が横に延々と間抜けに伸びていくの、端的に言って、ダサい。

余談はさておき、英語力がなんとも微妙なのでわかるような分からんような。ベンチマーキングって、どこかの犬が公園のベンチで縄張り主張とかしてるんだろうか。そうはいってもセンター試験と一緒で語感で解ける問題も結構多いので、英語力があると点数が上がりそう。

またマークがずれる。センターでは二回もずらしたことなんてなかったぞ!キレました。

もう算数パート以外は何も知らないので、語感だけで全部やる。文章が頭に入ってこないのと戦いながら、なんとか解き終える。

採点する。なんか最初の方で間違ってるやんけ!あっこれ、誤読してますね...。まあ、この手の試験ではありがちである。

  • 面白かった問題

問19: FIFOとLRUという理解させる気皆無な略語が現れる。しかし競プロで培った(?)直感により、FIFOがFirst In First Out の略であろうとあたりをつけることに成功する!多分合っていたようで、FIFOの方は正しい選択肢を選べていたが、LRUは何のことなのか全く分からず、二択を外し、あえなく撃沈(チーン)。ルービックキューブでも回してそうな名前してるよね。

問29: データウェアハウスがデータウェハースに見えた。おいしそう。でもデータってなんか層状に積まれてるイメージあるしあながち間違ってないのかもしれない(いいえ)。

問64: Bring Your Own Device ってお前そのままやんけ!英語力の勝利(は?)である。

問70: 納期に間に合わせるために製造時間短縮っていう選択肢、twitterの人たちが呪詛を吐いてそう(偏見)

  • 結論

一般常識 + 最低限の英語力 + 競プロ風味の算数 で通ります。競プロやってないと落ちたかという話ですが、多分落ちたと思う。

競技プログラミングは基本情報の役に立つ。

  • 回答

筆者の回答をあげておきます。採点ミスとかあったら言ってください。

エエイアウ イウエアエ エイアアウ ウエアアア ウアアイア イエウウウ アアアアウ イイアアウ
ウウウエウ イエエエイ ウエエイイ エアウイア エウウエイ ウアウイイ ウウイエエ ウウアエウ

Codeforces 553E Kyoya and Train

解説を読んで実装した。FFTの練習。

  • 問題概要

愚直DPを高速化してください

  • 解法

DPの遷移の係数を求める式を見ると、DP列とある列との畳み込みになっている。FFTして一件落着!と行きたいところだが、DP[i]を求めないとDP[i+1]が求まらないので、オンラインでFFTを求める必要がある。

解説のように、うまいこと領域を分割するとlog T回FFTをすればいいことがわかる。
配列サイズ足りると思ったのに足りなかった。なんでだろう。doubleは遅いのでfloatにしてやっとAC。segtreeと書いてあるものがsegtreeじゃないのはご愛敬。(実装方針が途中で変わった)

#include<stdio.h>
#include<vector>
#include<algorithm>
#include<math.h>
#include<stdlib.h>
using namespace std;
class cd
{
public:
	float x, y;
	cd() { x = 0, y = 0; }
	cd(double x, double y) :x(x), y(y) {}//&#65533;&#65533;&#65533;&#1794;&#65533;&#65533;&#514;&#65533;
	cd operator + (cd p)
	{
		return cd(x + p.x, y + p.y);
	}
	cd operator - (cd p)
	{
		return cd(x - p.x, y - p.y);
	}
	cd operator * (cd p)
	{
		return cd(x*p.x - y*p.y, x*p.y + y*p.x);
	}
};
typedef pair<vector<cd>, vector<cd> >pvcd;
double pi = 3.1415926535897932384626433;
#define LOG 16
class FFT
{
public:
	cd dat[2][1 << LOG];
	cd omega[1 << LOG], romega[1 << LOG];
	int seg[1 << LOG];
	void init(int lg)
	{
		for (int i = 0; i < (1 << lg); i++)omega[i] = cd(cos(pi*i * 2 / double(1 << lg)), sin(pi*i * 2 / double(1 << lg)));
		for (int i = 0; i < (1 << lg); i++)romega[i] = cd(cos(pi*i * 2 / double(1 << lg)), -sin(pi*i * 2 / double(1 << lg)));
		for (int i = 0; i < (1 << lg); i++)
		{
			int t = 0;
			for (int j = 0; j < lg; j++)if (i&(1 << j))t += 1 << (lg - j - 1);
			seg[i] = t;
		}
	}
	vector<cd>transform(vector<cd>v, int lg, bool pal)//&#65533;T&#65533;C&#65533;Y2^lg, pal&#65533;&#847;&#65533;&#65533;&#970;&#65533;&#65533;&#770;&#386;&#65533;true, &#65533;t&#65533;&#970;&#65533;&#65533;&#770;&#386;&#65533;false
	{
		int cur = 0;
		v.resize(1 << lg);
		for (int i = 0; i < (1 << lg); i++)dat[0][seg[i]] = v[i];
		for (int i = lg - 1; i >= 0; i--)
		{
			for (int j = 0; j < (1 << lg); j += (1 << (lg - i)))
			{
				int s = 1 << (lg - i - 1);
				if (pal)
				{
					for (int k = 0; k < s; k++)dat[1 - cur][j + k] = dat[cur][j + k] + dat[cur][j + s + k] * omega[k << i];
					for (int k = 0; k < s; k++)dat[1 - cur][j + s + k] = dat[cur][j + k] - dat[cur][j + s + k] * omega[k << i];
				}
				else
				{
					for (int k = 0; k < s; k++)dat[1 - cur][j + k] = dat[cur][j + k] + dat[cur][j + s + k] * romega[k << i];
					for (int k = 0; k < s; k++)dat[1 - cur][j + s + k] = dat[cur][j + k] - dat[cur][j + s + k] * romega[k << i];
				}
			}
			cur = 1 - cur;
		}
		vector<cd>ret;
		for (int i = 0; i < (1 << lg); i++)ret.push_back(dat[cur][i]);
		return ret;
	}
	pvcd transform_2(vector<double>va, vector<double>vb, int lg, bool pal)//2&#65533;&#136;&#65533;C&#65533;&#65533;transform &#65533;&#65533;&#65533;&#65533;&#65533;&#65533;&#770;&#65533;
	{
		va.resize(1 << lg);
		vb.resize(1 << lg);
		vector<cd>r;
		r.resize(1 << lg);
		for (int i = 0; i < (1 << lg); i++)r[i] = cd(va[i], vb[i]);
		r = transform(r, lg, pal);
		vector<cd>ra, rb;
		ra.resize(1 << lg);
		rb.resize(1 << lg);
		for (int i = 0; i < (1 << lg); i++)
		{
			int j = ((1 << lg) - i)&((1 << lg) - 1);
			ra[i] = cd((r[i] + r[j]).x, (r[i] - r[j]).y) * cd(0.5, 0);
			rb[i] = cd((r[i] + r[j]).y, -(r[i] - r[j]).x) * cd(0.5, 0);
			//printf("%d %lf %lf    %lf %lf  %lf %lf\n", i, r[i].x, r[i].y, ra[i].x, ra[i].y, rb[i].x, rb[i].y);
		}
		return make_pair(ra, rb);
	}
};
#define SIZE 32768
FFT fft[17];
class segtree
{
public:
	double seg[1 << LOG];
	vector<cd>tim[20];
	double now[1 << LOG];
	void init(vector<double>t,int lg)
	{
		int pt = 0;
		for (int d = 0; d <= lg; d++)
		{
			vector<cd>z;
			for (int i = pt; i < (1 << d); i++)z.push_back(cd(t[i], 0));
			pt = 1 << d;
			tim[d] = fft[d].transform(z, d, true);
			//for (int i = 0; i < tim[d].size(); i++)if(fabs(tim[d][i].x)>1e15||fabs(tim[d][i].y)>1e15)printf("%d %d  %d %d  %lf %lf\n", d,i,z.size(),1<<d,tim[d][i].x,tim[d][i].y);
		}
	}
	double add(int a, double t)
	{
		now[a] += t*tim[0][0].x;
		seg[a] = t;
		int s = 1;
		for (int d = 0;; d++)
		{
			vector<cd>z;
			for (int i = a - s + 1; i <= a; i++)z.push_back(cd(seg[i],0));
			//printf("\n\n\n\n");
			//for (int i = 0; i < z.size(); i++)printf("%lf ", z[i]); printf("\n");
			z = fft[d + 1].transform(z, d + 1, true);
			//for (int i = 0; i < z.size(); i++)printf("%lf ", z[i]); printf("\n");
			for (int i = 0; i < z.size(); i++)z[i] = z[i] * tim[d + 1][i];
			//for (int i = 0; i < z.size(); i++)printf("%lf ", z[i]); printf("\n");
			z = fft[d + 1].transform(z, d + 1, false);
			//for (int i = 0; i < z.size(); i++)printf("%lf ", z[i]); printf("\n");
			for (int i = 0; i < z.size(); i++)now[i + a + 1] += z[i].x / double(1 << (d + 1));
			if ((a&(1 << d)) == 0)break;
			s <<= 1;
		}
		return now[a];
	}
};
segtree tree[100];
int dist[50][50];
double cst[100][20001];
double rui[100][20001];
int frm[100], to[100], len[100];
double dp[20001][50];
int main()
{
	/*int num;
	scanf("%d", &num);
	vector<double>va, vb;
	va.push_back(0);
	vb.push_back(0);
	for (int i = 0; i < num; i++)
	{
		int za, zb;
		scanf("%d%d", &za, &zb);
		va.push_back(za);
		vb.push_back(zb);
	}
	fft[0].init(18);
	pvcd r = fft[0].transform_2(va, vb, 18, true);
	for (int i = 0; i < r.first.size(); i++)r.first[i] = r.first[i] * r.second[i];
	r.first = fft[0].transform(r.first, 18, false);
	for (int i = 1; i <= num + num; i++)printf("%d\n", int(floor(r.first[i].x / (1 << 18) + 0.5)));*/
	int num, way, gen, pen;
	scanf("%d%d%d%d", &num, &way, &gen, &pen);
	for (int i = 0; i < num; i++)for (int j = 0; j < num; j++)dist[i][j] = 1000000000;
	for (int i = 0; i < num; i++)dist[i][i] = 0;
	for (int i = 0; i < 17; i++)fft[i].init(i);
	for (int i = 0; i < way; i++)
	{
		int za, zb, zc;
		scanf("%d%d%d", &za, &zb, &zc);
		za--, zb--;
		dist[za][zb] = min(dist[za][zb], zc);
		frm[i] = za, to[i] = zb, len[i] = zc;
		for (int j = 1; j <= gen; j++)scanf("%lf", &cst[i][j]), cst[i][j] /= 100000, rui[i][j] = rui[i][j - 1] + cst[i][j];
		vector<double>z;
		z.resize(1 << 16);
		for (int j = 0; j < gen; j++)z[j] = cst[i][j + 1];
		tree[i].init(z, 16);
	}
	for (int i = 0; i < num; i++)for (int j = 0; j < num; j++)for (int k = 0; k < num; k++)dist[j][k] = min(dist[j][k], dist[j][i] + dist[i][k]);
	for (int i = 0; i < num; i++)dp[0][i] = (double)dist[i][num - 1] + double(pen);
	dp[0][num - 1] = 0;
	for (int x = 0; x < gen; x++)
	{
		for (int i = 0; i < num; i++)dp[x + 1][i] = (double)dist[i][num - 1] + double(pen);
		dp[x + 1][num - 1] = 0;
		for (int i = 0; i < way; i++)
		{
			double z = tree[i].add(x, dp[x][to[i]]);
			dp[x + 1][frm[i]] = min(dp[x + 1][frm[i]], (double)len[i] + z + (double)(rui[i][gen] - rui[i][x + 1])*(dist[to[i]][num - 1] + pen));
		}
		//for (int i = 0; i < num; i++)printf("%lf ", dp[x + 1][i]); printf("\n");///
	}
	printf("%.10lf\n", dp[gen][0]);
}

SRM710 Div1 hard Hyperboxes

  • 問題概要

{1,2,...,N}^K の点を頂点とした K 次元超直方体を重ならないように M 個置く方法は何通りあるか。

  • 解法

超直方体同士が重ならない <-> どこかの次元でその超直方体が占める区間がdisjoint なので、1次元の場合に区間がどういう重なり方(M <= 6 個の区間のそれぞれのペアに対し重なるか重ならないかの高々 2^15 通り)をするものが何通りあるかを前計算した後、例の A and B に足す convolution で二分累乗する。
後半パートは 2^15 * 15 * log 10^9 となる。

後半パートが本質だと思ってなめてかかったら前半パートが計算量のよくわからないいくつかの方針の中で正しいものを選ばないといけないゲームで、そっちに手間取った。
迷走した痕跡を敢えて残してコードを貼っておきます。

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
ll mod=998244353;
#define LOG 15
class Andadd
{
public:
	ll a[LOG+1][1<<LOG],b[LOG+1][1<<LOG],ret[LOG+1][1<<LOG];
	vector<ll>conv(vector<ll>va,vector<ll>vb)
	{
		for(int i=0;i<va.size();i++)a[0][i]=va[i];
		for(int i=0;i<vb.size();i++)b[0][i]=vb[i];
		for(int i=0;i<LOG;i++)
		{
			for(int j=0;j<(1<<LOG);j+=(1<<(LOG-i)))
			{
				int s=1<<(LOG-i-1);
				for(int k=0;k<s;k++)a[i+1][j+k]=(a[i][j+k]+a[i][j+s+k])%mod,a[i+1][j+s+k]=a[i][j+s+k];
				for(int k=0;k<s;k++)b[i+1][j+k]=(b[i][j+k]+b[i][j+s+k])%mod,b[i+1][j+s+k]=b[i][j+s+k];
			}
		}
		for(int i=0;i<(1<<LOG);i++)ret[LOG][i]=a[LOG][i]*b[LOG][i]%mod;
		for(int i=LOG-1;i>=0;i--)
		{
			for(int j=0;j<(1<<LOG);j+=(1<<(LOG-i)))
			{
				int s=1<<(LOG-i-1);
				for(int k=0;k<s;k++)ret[i][j+k]=(ret[i+1][j+k]+mod-ret[i+1][j+s+k])%mod;
				for(int k=0;k<s;k++)ret[i][j+s+k]=ret[i+1][j+s+k];
			}
		}
		vector<ll>r;
		for(int i=0;i<(1<<LOG);i++)r.push_back(ret[0][i]);
		return r;
	}
};
ll po(ll a, ll b)
{
	if (b == 0)return 1;
	ll z = po(a, b / 2);
	z = z*z%mod;
	if (b & 1)z = z*a%mod;
	return z;
}
ll iiiinv(ll a)
{
	return po(a, mod - 2);
}
ll inv[100];
ll com(ll a,ll b)
{
	if(b<0||b>a)return 0;
	ll r=1;
	for(int i=1;i<=b;i++)r=r*(a-i+1)%mod*inv[i]%mod;
	return r;
}
ll dat[1<<15];
Andadd ad;
vector<ll>ppooww(vector<ll>a,ll b)
{
	if(b==1)return a;
	vector<ll>z=ppooww(a,b/2);
	z=ad.conv(z,z);
	if(b%2==1)z=ad.conv(z,a);
	return z;
}
#include<map>
map<ll,ll>dp[13];
typedef pair<ll,ll>pii;
int dig[6][6];
class Hyperboxes
{
public:
	int findCount(int len,int num,int dim)
	{
		for(int i=1;i<100;i++)inv[i]=iiiinv(i);
		/*vector<int>v;
		for(int i=0;i<num;i++)v.push_back(i+1),v.push_back(i+1);
		for(;;)
		{
			int now=0;
			bool fff=true;
			for(int i=0;i<v.size();i++)
			{
				if(now+1<v[i])fff=false;
				now=max(now,v[i]);
			}
		//	if(fff)
			{
				int d[10];
				fill(d,d+10,0);
				int st[10],go[10];
				vector<int>x;
				for(int i=0;i<v.size();i++)
				{
					if(d[v[i]]==0)d[v[i]]=1,x.push_back(v[i]),st[v[i]]=i;
					else x.push_back(-v[i]),go[v[i]]=i;
				}
				ll dp[13][13][13];
				for(int i=0;i<13;i++)for(int j=0;j<13;j++)for(int k=0;k<13;k++)dp[i][j][k]=0;
				dp[0][0][1]=1;
				for(int i=1;i<x.size();i++)
				{
					int t=0;
					if(x[i-1]<0&&x[i]>0)t=1;
					else if(x[i-1]>0&&x[i]>0&&v[i-1]<v[i])t=1;
					else if(x[i-1]<0&&x[i]<0&&v[i-1]<v[i])t=1;
					if(t==0)
					{
						for(int k=0;k<=num+num;k++)
						{
							for(int j=i-1;j>=0;j--)
							{
								if(v[i]==v[j])break;
								dp[i][j][k]+=dp[i-1][j][k];
							}
						}
					}
					for(int k=0;k<num+num;k++)
					{
						for(int j=0;j<i;j++)
						{
							dp[i][i][k+1]+=dp[i-1][j][k];
						}
					}
				}
				ll sum=0;
				for(int k=0;k<=num+num;k++)
				{
					ll ss=0;
					for(int j=0;j<=num+num;j++)ss+=dp[num+num-1][j][k];
					//printf(" %lld\n",ss);
					sum+=ss*com(len,k);
					sum%=mod;
				}
				int mask=0;
				int pt=0;
				for(int i=1;i<=num;i++)
				{
					for(int j=i+1;j<=num;j++)
					{
						if(!(go[i]<st[j]||go[j]<st[i]))mask+=(1<<pt);
						pt++;
					}
				}
				dat[mask]=(dat[mask]+sum)%mod;
				//printf("%d %lld\n",mask,sum);
			}
			if(!next_permutation(v.begin(),v.end()))break;
		}
	//	for(int i=0;i<2;i++)printf("%lld\n",dat[i]);*/
		int pppt=0;
		for(int i=0;i<num;i++)
		{
			for(int j=i+1;j<num;j++)
			{
				dig[i][j]=dig[j][i]=pppt;
				pppt++;
			}
		}
		dp[0][0]=1;
		for(int i=0;i<=num+num;i++)
		{
			map<ll,ll>::iterator it=dp[i].begin();
			for(;;)
			{
				if(it==dp[i].end())break;
				pii zz=*it;
				it++;
			//	printf("%d %lld %lld %lld\n",i,zz.first>>15,zz.first%(1<<15),zz.second);
				int x[6],mask=zz.first%(1<<15);
				zz.first/=(1<<15);
				for(int j=0;j<num;j++)x[j]=zz.first%3,zz.first/=3;
				vector<int>v0,v1;
				for(int j=0;j<num;j++)
				{
					if(x[j]==0)v0.push_back(j);
					else if(x[j]==1)v1.push_back(j);
				}
				if(v0.size()+v1.size()==0)
				{
					dat[mask]+=zz.second*com(len,i);
					dat[mask]%=mod;
					continue;
				}
				for(int p=0;p<(1<<v0.size());p++)
				{
					int y[6];
					int m=mask;
					for(int j=0;j<num;j++)y[j]=x[j];
					for(int j=0;j<v0.size();j++)
					{
						if(p&(1<<j))
						{
							for(int k=0;k<num;k++)if(y[k]==1)m|=1<<dig[v0[j]][k];
							y[v0[j]]=1;
						}
					}
					for(int q=0;q<(1<<v1.size());q++)
					{
						if(p==0&&q==0)continue;
						int z[6];
						for(int j=0;j<num;j++)z[j]=y[j];
						for(int j=0;j<v1.size();j++)if(q&(1<<j))z[v1[j]]=2;
						ll t=0;
						for(int j=num-1;j>=0;j--)t*=3,t+=z[j];
						t=(t<<15)+m;
						dp[i+1][t]=(dp[i+1][t]+zz.second)%mod;
					}
				}
			}
		}
		vector<ll>ans;
	//	for(int i=0;i<4;i++)printf("%lld\n",dat[i]);
		for(int i=0;i<(1<<15);i++)ans.push_back(dat[i]);
		vector<ll>r=ppooww(ans,dim);
		ll aaa=r[0];
	//	for(int i=1;i<=num;i++)aaa=aaa*i%mod;
		return int(aaa);
	}
};

Codeforces 329E Evil

見た目が解けるものに見えないが、実は解ける。見た目とのギャップがすごい。

  • 問題概要

平面上にN点与えられるので、N点全てを一回ずつ使うサイクルを作って、隣り合う2点間のマンハッタン距離の総和を最大化せよ。

  • 解法

x座標の中央値とy座標の中央値で切って領域を4つに分ける。全部の辺がこの対角線の領域同士を結んでいれば、無条件で最大。

それができない場合、まずNの偶奇で場合分けする。

  • Nが偶数のとき

左側同士を結ぶ辺と右側同士を結ぶ辺を1本ずつ、あるいは上側同士を結ぶ辺と下側同士を結ぶ辺を1本ずつはる必要がある。両方の場合について試してminをとる。「この2点を結ぶとどれくらい損するか」みたいなのを考えると、どこに辺をはればいいかは割と簡単にわかる。

  • Nが奇数で、(x座標の中央値,y座標の中央値)という点がある場合

上と大体同様だが、左側 or 右側 or 上側 or 下側同士を結ぶ辺のうちひとつをはればいい。

  • Nが奇数で、(x座標の中央値,y座標の中央値)という点がない場合

上記の上界を達成するサイクルが構成できる。

以上の場合分けをすると通る。面白い。

#include<stdio.h>
#include<vector>
#include<algorithm>
#include<math.h>
#include<stdlib.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll>pii;
#define INF 1000000000000000000LL
int main()
{
	int num;
	scanf("%d", &num);
	vector<pii>vx, vy;
	for (int i = 0; i < num; i++)
	{
		int za, zb;
		scanf("%d%d", &za, &zb);
		vx.push_back(make_pair(za, zb));
		vy.push_back(make_pair(zb, za));
	}
	sort(vx.begin(), vx.end());
	sort(vy.begin(), vy.end());
	ll mx = vx[vx.size() / 2].first, my = vy[vy.size() / 2].first;
	ll sx = 0, sy = 0;
	for (int i = 0; i < vx.size(); i++)sx += abs(vx[i].first - mx);
	for (int i = 0; i < vy.size(); i++)sy += abs(vy[i].first - my);
	if (num % 2 == 0)
	{
		int cnt = 0;
		for (int i = 0; i < num / 2; i++)if (make_pair(vx[i].second, vx[i].first) < vy[num / 2])cnt++;
		if (cnt == 0 || cnt == num / 2)
		{
			printf("%I64d\n", (sx + sy) * 2);
		}
		else
		{
			ll m1 = INF, m2 = INF, m3 = INF, m4 = INF;
			for (int i = 0; i < num / 2; i++)m1 = min(m1, mx - vx[i].first);
			for (int i = num / 2; i < num; i++)m2 = min(m2, vx[i].first - mx);
			for (int i = 0; i < num / 2; i++)m3 = min(m3, my - vy[i].first);
			for (int i = num / 2; i < num; i++)m4 = min(m4, vy[i].first - my);
			printf("%I64d\n", (sx + sy) * 2 - min(m1 + m2, m3 + m4) * 2);
		}
	}
	else
	{
		if (make_pair(vx[num / 2].second, vx[num / 2].first) != vy[num / 2])
		{
			printf("%I64d\n", (sx + sy) * 2);
		}
		else
		{
			int cnt = 0;
			for (int i = 0; i < num / 2; i++)if (make_pair(vx[i].second, vx[i].first) < vy[num / 2])cnt++;
			if (cnt == 0 || cnt == num / 2)
			{
				printf("%I64d\n", (sx + sy) * 2);
			}
			else
			{
				ll m1 = INF, m2 = INF, m3 = INF, m4 = INF;
				for (int i = 0; i < num / 2; i++)m1 = min(m1, mx - vx[i].first);
				for (int i = num / 2 + 1; i < num; i++)m2 = min(m2, vx[i].first - mx);
				for (int i = 0; i < num / 2; i++)m3 = min(m3, my - vy[i].first);
				for (int i = num / 2 + 1; i < num; i++)m4 = min(m4, vy[i].first - my);
				printf("%I64d\n", (sx + sy) * 2 - min(min(m1, m2), min(m3, m4)) * 2);
			}
		}
	}
}

Codeforces 429E Points and Segments

前4問は何だったのかという感じの良問。

問題概要: 区間がN個与えられる。この区間たちに 1 or -1 を割り当てて、どの座標でもそれを含む区間の値の和の絶対値が 1 以下になるようなものを構成せよ。

解法: まず全座標がdistinctなときにできるなら適当に順番を決めればdistinctじゃなくてもできる。

全座標がdistinctなとき、条件は区間が偶数個重なっているところ全てで和が 0 であることと同値。座標を前から見て、区間が消えたり現れたりするのを 2 つごとに見ると、

であることが必要十分なことがわかる。

これを満たす割り当てがあるかどうかだが、関係があるところにそれっぽく辺をはると(区間の始点/終点のどちらを見てはられた辺かを考えると)これは偶サイクルっぽい感じ(性格には、「違うパリティ」の辺が偶数本)なことがわかるので、必ず割り当てがある。解けた。

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
#define SIZE 200000
class unionfind
{
public:
	int par[SIZE];
	int ran[SIZE];
	int ren[SIZE];
	void init()
	{
		for (int i = 0; i<SIZE; i++)
		{
			par[i] = i;
			ran[i] = 0;
			ren[i] = 1;
		}
	}
	int find(int a)
	{
		if (a == par[a])return a;
		else return par[a] = find(par[a]);
	}
	void unite(int a, int b)
	{
		a = find(a);
		b = find(b);
		if (a == b)return;
		if (ran[a]>ran[b])
		{
			par[b] = a;
			ren[a] += ren[b];
		}
		else
		{
			par[a] = b;
			ren[b] += ren[a];
		}
		if (ran[a] == ran[b])ran[b]++;
	}
};
unionfind uf;
typedef pair<int, int>pii;
typedef pair<pii, int>pi3;
bool flag[200000];
int main()
{
	int num;
	scanf("%d", &num);
	vector<pi3>vec;
	for (int i = 0; i < num; i++)
	{
		int za, zb;
		scanf("%d%d", &za, &zb);
		vec.push_back(make_pair(make_pair(za, 0), i));
		vec.push_back(make_pair(make_pair(zb, 1), i));
	}
	sort(vec.begin(), vec.end());
	uf.init();
	for (int i = 0; i < num; i++)
	{
		if (vec[i * 2].first.second == vec[i * 2 + 1].first.second)
		{
			uf.unite(vec[i * 2].second * 2, vec[i * 2 + 1].second * 2 + 1);
			uf.unite(vec[i * 2].second * 2 + 1, vec[i * 2 + 1].second * 2);
		}
		else
		{
			uf.unite(vec[i * 2].second * 2, vec[i * 2 + 1].second * 2);
			uf.unite(vec[i * 2].second * 2 + 1, vec[i * 2 + 1].second * 2 + 1);
		}
	}
	for (int i = 0; i < num; i++)
	{
		if (i * 2 == uf.find(i * 2))
		{
			if (!flag[uf.find(i * 2 + 1)])
			{
				flag[i * 2] = true;
			}
		}
		if (i * 2 + 1 == uf.find(i * 2 + 1))
		{
			if (!flag[uf.find(i * 2)])
			{
				flag[i * 2 + 1] = true;
			}
		}
		//printf("%d %d\n", uf.find(i * 2), uf.find(i * 2 + 1));
	}
	for (int i = 0; i < num; i++)
	{
		if (flag[uf.find(i * 2)])printf("0 ");
		else printf("1 ");
	}
	printf("\n");
}

真っ白な、幻の世界

最近、おかしな夢をよく見る。居眠りをしているときに、よく見る夢だ。

 

その夢は、それを見たのかどうかすらも分からないほどに抽象的で、一切の物理的な動きを、五感の働きを、焦りを、緊迫を含まない。一切の具体的な印象は、残らない。ふと目が覚めると、異世界の冒険から記憶を消して戻ってくることを選択したファンタジーの主人公が、日常の再開の瞬間に一瞬覚えるような、何か強く大きな世界がそのまま消滅したかのような違和感と、そこに大切な何かを置き忘れたかのような虚無感のみが、そこに残されている。

 

人はそれを思い出そうと、記憶にとどめようと懸命になる。しかしそう決意するほどの理性が復活した頃には、それはすでに記憶の彼方に飛んで行っており、些細な手がかりすらも、最早残されてはいない。確実に先ほどまでは存在したであろう「答え」を探したくて、それを言葉にしたくて、でもそう思ったころにはすでにどこを探せばいいのかすら分からなくて。そして、あまりのどうしようもなさから、「答え」など始めからそんなところにはなかったのだと、すべては気のせいで、そんなことは時間の無駄なのだと、決めつけて考えるのをやめてしまうことが、一切の矛盾をはらまなくて。

 

そして矛盾するようだが、今日はその「夢」の中身を、少しだけこちら側へ持ち帰ることができたので、それを紹介しようと思う。

 

背景が真っ白な世界に、どこまでも平行に、決して交わらずにまっすぐに伸びる、鉄道の路線が走っている。ちょうど人間の身体と同じサイズの電車が、望んだときに、望んだ場所に現れる。夢の中の僕は、そのとても速い電車に、好きなところで乗って、好きなだけ進んで、好きなところで降りる。道中も、降りた先も、ただどこまでも壁紙のように真っ白な、無音の世界で、幸せというどこまでも抽象的なものでさえ、具体的な形を帯びているようで。その様子をはるか上から俯瞰する僕が、感覚を同じくする存在として、一切の引いた目線を持たずに、存在していて。

 

夢の中で僕は、なんだってできて。電車はすぐに、目的地に到着して。でもその世界は真っ白だから、具体的な何かをすることは絶対になくて。その世界には具体的なものは何一つ存在しないのだから、矛盾をはらむことすらあり得なくて。ただまっすぐに電車を乗り継いで、その抽象的な、そしておそらく、感情そのものが実体をもって現れたようなその背景を、幸せが手でつかめるかのようなその世界を、ただ無条件に味わって。

 

夢とは所詮、自らの脳の見せる錯覚である。自らの頭の中にないものは、決して現れない。しかし我々は、その夢の中の我々の想像力にしばしば感心する。はっきりした頭では決して考えられないような、支離滅裂で、前提もめちゃくちゃで、しかし面白い世界を、夢は見せてくれる。まるでそこには自分をはるかに超越した存在がいて、昼間の我々が必死で探し求める「答え」を持っており、その片鱗を見せて、それに必死で触れようとする我々を、からかって遊んでいるかのように。

 

それゆえ人は、夢を思い出そうと躍起になる。根拠はないし、おそらくはただ寝ぼけているだけなのに、そこに存在したような気がする「答え」を、取り返そうとする。取り返すこと、それは往々にして言葉にすることだ。そして言葉にしようと準備をすることすら、その脆い世界を粉々にして、跡形もなく消滅させるのに、十分すぎる衝撃となる。

 

人は、正当化を行う生き物だ。そして、人は正当化が上手だ。人を殺すことすらも、納得のできる形に昇華させてしまうほどに。

 

それゆえ人は、答えなどそこには存在しなかったのだ、すべてはただの錯覚だと、納得することにする。そもそも答えが、自分の頭の中にすでに存在したなんて、そんなことはあるわけがないと。そして後には、この居眠りは、そして期待は、何の役にも立たなかったのだという虚無感のみが残る。それでも夢は同じように、人に答えの片割れを、変わらず見せ続けてくる。

 

今日の僕は、その答えの片鱗を、夢から奪ってくることができた。それは答えと呼べるほどはっきりとしたものではなくて。そこで見えたものは、現実の僕の行動を変えるような教えを、何一つ含まなくて。しかし少なくとも、普段の虚無感を、味わわずに済んだ。言葉にできない、記憶の中にすらも存在できないように思えたその世界を堪能した自分を、そこで覚えた、どこまでも強くて、そしてどこまでも脆い感情の欠片を、持って帰ってくることができた。

 

夢とは不確実なものだ。古今東西、あらゆる人が夢の強さに惹かれ、夢を操ろうとした。所詮自分の頭の中で起こっていることなのだ。頭の中で、完結する世界なのだ。意のままに操れても、何らおかしくはないと。それでもその試みには、まだ誰も成功していない。

 

だから僕が、この幾度となく見て、そして初めて持って帰ってくることのできたこの夢を、もう一度見ることがあるのかどうかはわからない。だが少なくとも、これだけは確実に言える。夢の片割れを、一度、ほんの少しでも心に残しておくことができた僕には、もうあの正当化を行う必要も、権利も、残されていないということだ。

 

僕は加藤和也にはなれない

何かに熱心になること、そのことしか考えられないほど熱中すること、そして、純粋に好きという気持ちだけでそれを続けられること。

 

それは素晴らしいことだと思うし、皆そう思っている。寝るのも忘れてバットを振る野球選手は美しいし、ただひたすらに作品を作り続ける伝統工芸の職人は尊敬される。

 

そのあまりにも明確で、強い気持ちは、人を魅了する。そして純粋な羨望の対象となる。それゆえ人はこう言う。「本当に好きな何かを見つけなさい」と。一切の悪意を含まず、純粋に、本当に楽しい人生を送るためのアドバイスとして。それを見つけた自分の覚えるであろう真の楽しさを、究極の喜びを夢想して。

 

もちろん僕もその一人である。僕は、周りより数学ができた。数学オリンピックの日本代表にもなった。今でも、大学の細分化された学問体系の、僕が専攻したいと思っているとある分野では、少なくとも国内の自分と同学年の学生の中では、誰にも負けていないと思っている。

 

そして、僕は数学が好きだ。人が10分で考えるのをやめるところを、3時間考えていられる程度には。そして悲しいことに、普通の人から見ると、それはいつまででも考え続けられることと、区別がつかないのだ。

 

熱心になれること、好きでいられること、それは究極の喜びを夢想する人間にとっての規範である。究極の喜びを得るために、人はそれを好きでなければならない。本の証明が理解できなくても、疲れていたとしても、それをやり続けなければならない。朝から晩まで、そのことばかり考えていなければならない。好きなのだから。好きだと決めたのだから。

 

好きでいるかどうか、熱心でいられるかどうか。それは気持ちの問題だ。それゆえ人は熱心になれない自分を責める。起きてから寝るまで16時間、どこかで必ず気が抜ける自分を責める。休み休みに6時間しか考えられない自分を、たとえ6時間考えられること自体が一般には特別なことであったとしても、心が弱いと責める。16時間、考えられる人は確実に存在するのだから。そういう人についての話を聞くのだから。そして、自分は、本当に好きであるはずのことについて、才能なんかではなくて、気持ちで負けているのだから。

 

加藤和也という数学者がいる。数学に熱中するあまり駅を半裸で歩いて補導されたとか、そういうエピソードのある数学者だ。我々はそのエピソードを聞いて、とりあえず変な人だと笑う。しかし確実に、それを格好いいと感じる。そうなりたいと望む。補導されたいとは思わないにせよ、自分が半裸で外を歩いているという明らかな異常性にすら気付かないほどに、何かに熱中してみたいと思う。そして、自分がそれができる人間であることを示すような、武勇伝を欲しがる。人はその武勇伝のために、自分の姿を見ようと開きかけている目を、強制的に塞ぐことさえする。

 

人は自分を見る目を塞いでまで、熱心になろうともがく。好きでないことは不誠実だ。その対象に、そして自分自身に誠実であるために、現実の自分の姿に目をつぶる。自分をその理想像に投影し、そしてその理想を省みることをしない。理想と現実の乖離を、頑なに認めない。

 

スクリーンには、屈託のない笑顔を浮かべた未来の自分が、何かすごそうな賞を受賞しているのが映っている。その映画館の座席では、作り笑いを浮かべた青年が、ただポップコーンをつまんでいる。本当はポップコーンなどつまんでいる暇はないはずなのに。本当にスクリーンに映っているべきは、すごそうな賞を受賞している自分などではなく、その好きなことを、普段通りに楽しんでいる、普段の自分であるべきなのに。