KUPC2013 A - 旧総合研究７号館｜AtCoder

A: 旧総合研究７号館 - 京都大学プログラミングコンテスト2013 | AtCoderを解きました。

題意：
・N個の改名後の校舎名と改名年度と、資料が作成された年度Qが与えられるので、
　Q年度の校舎の名前を出力する。
・平成元年度の校舎名は "kogakubu10gokan"
・1 ≤ N < 50
・1 ≤ Q ≤ 50
・2 ≤ year 1 < year 2 < … < year n ≤ 50
　( その他細かい制約は問題文参照で )

解法：
年度は高々50年までしかないので、50 + 1 の配列を 平成元年度の校舎名 "kogakubu10gokan" で埋めて、その後改名された年度の校舎名で配列を上書きしてQ年度を出力する。
計算量はO( N )

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0; i<(n); i++)
#define REP2(i,x,n) for(int i=x; i<(n); i++)
struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;
int main()
{
	int N, Q;
	cin >> N >> Q;
	vector<int> year( 50 + 1 );
	vector<string> name( N );
	REP( i, N )
	{
		cin >> year[ i ] >> name[ i ];
	}
	vector<string> res( 50 + 1 );
	string tmp = "kogakubu10gokan";
	REP( i, 50 + 1 )
	{
		REP( j, N )
		{
			if( i == year[ j ] )
			{
				tmp = name[ j ];
			}
			res[ i ] = tmp;
		}
	}
	cout << res[ Q ] << endl;
	return 0;
}

応用・発展：
例えば、Q の制約が 1 ≤ Q ≤ 10^9 だったらどう解く？と云う発展課題！
上記コードでは別配列を用意して 50 + 1 年分をわざわざ全て埋めたけれど、実はその必要は無く、指定されたQ年度の校舎名をそのまま返してあげれば良いだけ、という解法に至りました。
(なので上記コードは無駄な事をしている事が判った...)

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0; i<(n); i++)
#define REP2(i,x,n) for(int i=x; i<(n); i++)
struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;
int main()
{
	int N, Q;
	cin >> N >> Q;
	vector<int> year( N );
	vector<string> name( N );
	REP( i, N )
	{
		cin >> year[ i ] >> name[ i ];
	}
	year.emplace_back( 51 );
	string res = "kogakubu10gokan";
	REP( i, N + 1 )
	{
		if( year[ i ] <= Q && year[ i + 1 ] > Q )
		{
			res = name[ i ];
		}
		if( Q > year[ N - 1 ] )
		{
			res = name[ N - 1 ];
		}
	}
	cout << res << endl;
	return 0;
}

loop 1個減ったのですが、こちらも計算量はO( N )。
2つのコードを比較する為に書き示すとしたらO( year* N )。

計算量(ステップ数)とO記法は別の概念というのをなんとなく覚えました。

※記事中の計算量にご指摘がある場合はご連絡ください...