Codeforces #116(Div 2 only)

Div1がないとかいう糞仕様だったのでunofficialで出場。

コンテスト開始。
Aを読む。
Div2のAがこんなに難しいわけがないと思い、standingsを見る。
CとFしか解かれていない。難易度順じゃないみたいだ。
とりあえずCを解く。やるだけ。

#include<stdio.h>
#include<string>
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int han(char a)
{
	if(a>='a'&&a<='z')
	{
		return 0;
	}
	else
	{
		return 1;
	}
}
int main()
{
	string str;
	cin>>str;
	vector<int>vec;
	int now=0;
	for(int i=0;i<str.size();i++)
	{
		vec.push_back(now);
		if(han(str[i])==0)
		{
			now++;
		}
	}
	vec.push_back(now);
	reverse(str.begin(),str.end());
	int now2=0;
	int mini=10000000;
	for(int j=0;j<str.size();j++)
	{
		mini=min(mini,now2+vec[str.size()-j]);
		if(han(str[j])==1)
		{
			now2++;
		}
	}
	mini=min(mini,now2+vec[0]);
	printf("%d\n",mini);
}

Fをとく。もっとやるだけ。

#include<stdio.h>
#include<vector>
using namespace std;
int main()
{
	int num;
	scanf("%d",&num);
	vector<int>from;
	vector<int>to;
	for(int i=0;i<num;i++)
	{
		int zan;
		scanf("%d",&zan);
		from.push_back(zan);
	}
	for(int j=0;j<num;j++)
	{
		int zan;
		scanf("%d",&zan);
		to.push_back(zan);
	}
	vector<int>vec;
	vector<int>ans;
	for(int k=0;k<num;k++)
	{
		vec.push_back(0);
		ans.push_back(0);
	}
	for(int l=0;l<num;l++)
	{
		vec[to[l]-1]=from[l]-1;
	}
	for(int m=0;m<num;m++)
	{
		if(m!=0)
		{
			printf(" ");
		}
		printf("%d",vec[from[m]-1]+1);
	}
	printf("\n");
}

まあAは問題文読んでいたし、Aをとく。とりあえず出力の制約がゆるすぎなので、適当に考えたアルゴリズムで解く。

#include<stdio.h>
#include<vector>
#include<algorithm>
#include<stack>
using namespace std;
int main()
{
	int num,hoge;
	scanf("%d%d",&num,&hoge);
	vector<pair<int,int> >ans;
	vector<int>vec;
	for(int i=0;i<num;i++)
	{
		vec.push_back(0);
	}
	int now=0;
	for(int j=0;j<hoge;j++)
	{
		int fuga;
		scanf("%d",&fuga);
		for(int k=0;k<fuga;k++)
		{
			int zan;
			scanf("%d",&zan);
			zan--;
			vec[zan]=now;
			now++;
		}
	}
	if(vec[now]!=0)
	{
		for(int l=0;l<now;l++)
		{
			if(vec[l]==0)
			{
				vec[l]=vec[now];
				vec[now]=0;
				ans.push_back(make_pair(now,l));
				break;
			}
		}
	}
	for(int m=0;m<now;m++)
	{
		if(vec[m]!=m)
		{
			int str=m;
			stack<int>sta;
			for(;;)
			{
				sta.push(str);
				str=vec[str];
				if(str==m)
				{
					int piyo=now;
					for(;;)
					{
						if(sta.empty())
						{
							break;
						}
						ans.push_back(make_pair(sta.top(),piyo));
						vec[piyo]=vec[sta.top()];
						piyo=sta.top();
						sta.pop();
					}
					ans.push_back(make_pair(now,piyo));
					vec[piyo]=vec[now];
					break;
				}
			}
		}
	}
	printf("%d\n",ans.size());
	for(int n=0;n<ans.size();n++)
	{
		printf("%d %d\n",ans[n].first+1,ans[n].second+1);
	}
}

はいWA!
どうやら最初に0で初期化しているせいでいろいろとまずいことが起こってるらしい。
デバッグ。40分くらいかけてしまう。

#include<stdio.h>
#include<vector>
#include<algorithm>
#include<stack>
using namespace std;
int main()
{
	int num,hoge;
	scanf("%d%d",&num,&hoge);
	vector<pair<int,int> >ans;
	vector<int>vec;
	for(int i=0;i<num;i++)
	{
		vec.push_back(-1);
	}
	int now=0;
	for(int j=0;j<hoge;j++)
	{
		int fuga;
		scanf("%d",&fuga);
		for(int k=0;k<fuga;k++)
		{
			int zan;
			scanf("%d",&zan);
			zan--;
			vec[zan]=now;
			now++;
		}
	}
	if(vec[now]!=-1)
	{
		for(int l=0;l<now;l++)
		{
			if(vec[l]==-1)
			{
				vec[l]=vec[now];
				vec[now]=-1;
				ans.push_back(make_pair(now,l));
				break;
			}
		}
	}
	for(int m=0;m<num;m++)
	{
		if(vec[m]!=m&&vec[m]!=-1)
		{
			int str=m;
			stack<int>sta;
			for(;;)
			{
				sta.push(str);
				str=vec[str];
				if(str==m||str==-1)
				{
					int piyo=now;
					for(;;)
					{
						if(sta.empty())
						{
							break;
						}
						ans.push_back(make_pair(sta.top(),piyo));
						vec[piyo]=vec[sta.top()];
						piyo=sta.top();
						sta.pop();
					}
					ans.push_back(make_pair(now,piyo));
					vec[piyo]=vec[now];
					vec[now]=-1;
					break;
				}
			}
		}
	}
	printf("%d\n",ans.size());
	for(int n=0;n<ans.size();n++)
	{
		printf("%d %d\n",ans[n].first+1,ans[n].second+1);
	}
}

一応これで通る。

残り20分だし、やることないよね→ぼーっと問題文読んだり→終了

3完とか悲惨すぎ・・・