Language: C++

#define SUBMISSION

// 提出時は標準入力から読み込み。練習中はファイルから読み込み
#ifdef SUBMISSION
#define	INPUT(a) cin >> (a);
#define	OUTPUT(a) cout << (a) << endl;
#else
#define	INPUT(a) fin >> (a);
#define	OUTPUT(a) fout << (a) << endl; // cerr << (a) << endl;
#endif

#include <string>
#include <iomanip>
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <unordered_map>
#include <set>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <numeric>
#include <list>
#include <time.h>
#include <math.h>
#include <assert.h>
#include <random>
#include <bitset>
#include <fstream>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
template<class T> bool INRANGE(T x, T a, T b) { return a <= x && x <= b; }
template<class T> void amin(T &a, T v) { if (a > v) a = v; }
template<class T> void amax(T &a, T v) { if (a < v) a = v; }
template<class T> T CLAMP(T x, T a, T b) { return min(max(x, a), b); }
#define NG (-1)
#define BIG (static_cast<int>(1e9))
#define SZ(a) ((int)a.size()) 
#define SQ(a) ((a)*(a))
#define SAFE_DELETE(a) { if (a!=NULL) { delete a; a = NULL; }}
#define PI (acos(-1))

inline double RAD2DEG(double rad) { return rad * 180.0 / PI; }

static const double EPS = 1e-9;
inline int ROUND(double x) { return (int)(x + 0.5); }
inline bool ISINT(double x) { return fabs(ROUND(x) - x) <= EPS; }
inline bool ISEQUAL(double x, double y) { return fabs(x - y) <= EPS * max(1.0, max(fabs(x), fabs(y))); }
inline double SQSUM(double x, double y) { return x * x + y * y; }

#include <chrono>
inline ll getTime()
{
	return std::chrono::duration_cast<std::chrono::milliseconds>(std::chrono::system_clock::now().time_since_epoch()).count();
}

class RandXor
{
public:
	RandXor()
	{
		init();
	}

	void init()
	{
		x = 123456789;
		y = 362436069;
		z = 521288629;
		w = 88675123;
	}

	void init(ll seed)
	{
		x = 123456789;
		y = static_cast<unsigned int>(362436069 + seed * 674890201);
		z = static_cast<unsigned int>(521288629 - seed * seed * 164907679);
		w = static_cast<unsigned int>(88675123 * seed);
	}


	inline unsigned int rand()
	{
		unsigned int t;
		t = (x ^ (x << 11)); x = y; y = z; z = w; return(w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)));
	}

	unsigned int next() {
		return rand();
	}

	int nextInt(int num) {
		return rand() % num;
	}

	// [a,b)
	int next(int a, int b) {
		return a + (rand() % (b - a));
	}

	// [-d,d]
	int nextDelta(int d) {
		return next(-d, d + 1);
	}

	double nextDouble() {
		return (rand() + 0.5) * (1.0 / 4294967296.0);
	}

	template <class T>
	void randomShuffle(vector <T> &a)
	{
		const int n = SZ(a);
		for (int i = n - 1; i > 0; --i) {
			swap(a[i], a[nextInt(i + 1)]);
		}
	}

private:
	unsigned int x;
	unsigned int y;
	unsigned int z;
	unsigned int w;
};

#define SA_DEBUG
// #define SA_SCORE_CHECKER
// #define SA_PROGRESS
// #define SA_STATS

enum AlgorithmMode
{
	SA,
	HillClimb,
};

// 焼きなまし法の状態をIStateを実装する必要がある（ポリモーフィズムは使ってない。テンプレートのかわり）
class IState
{
public:
	virtual	void	saInit() = 0;
	virtual	double	saScore() = 0;			// ペナルティなども含んだ、焼きなまし用のスコア。
	virtual	double	saMove() = 0;
	virtual	void	saForward() = 0;
	virtual	void	saResume() = 0;
	virtual void	saSetProgressRatio(double progressRatio, double temp) = 0;
#ifdef SA_STATS
	virtual int 	saGetNeighborID() = 0;
#endif // SA_STATS
};

template <class STATE>
class SimulatedAnnealing
{
public:
	const STATE& getBestState() const { return mBestState; }
	const STATE& getCurrentState() const { return mCurrentState; }
	const double getBestScore() const { return mBestScore; }
	const ll getLoopCount() const { return mLoopCount; }

	void init(
		const STATE&	state,			// STATEに、mProbのthisポインタを渡すなどの自由度を持たす狙い。こうしないとTemplateにもう１つクラスを足すしかない。
		AlgorithmMode	algorithmMode,
		ll				numSubLoops,
		ll				numTimerCheckLoops,
		double			maxStartTemp = 1.0,
		double			maxEndTemp = 1.0,
		double			minTemp = 0.001,
		double			tempExponential = 0.5,
		int				numMultiStart = 1,
		int				randomSeed = 1)
	{
		mCurrentState = state;
		mCurrentState.saInit();
		mCurrentScore = mCurrentState.saScore();

		mStartState = mBestState = mCurrentState;
		mStartScore = mBestScore = mCurrentScore;

		mAlgorithmMode = algorithmMode;

		mNumSubLoops = numSubLoops;
		mNumTimerCheckLoops = numTimerCheckLoops;

		mBestTime = 0;
		mLoopCount = 0;

		// For SA
		mRandXor.init(randomSeed);
		mMaxStartTemp = maxStartTemp;
		mMaxEndTemp = maxEndTemp;
		mMinTemp = minTemp;
		mTempExponential = tempExponential;
		mNumMultiStart = numMultiStart;

#ifdef SA_STATS
		mPhases.clear();
#endif // SA_STATS
	}

	void runByClock(const ll durationMillSecond)
	{
		mStartTime = getTime();

		updateParameters(0.0);
		mSubLoopDownCount = mNumSubLoops;
		mTimeCheckDownCount = mNumTimerCheckLoops;

		ll ellapsedTime = 0;
		while (1)
		{
			runOnce();
			if (mSubLoopDownCount <= 0)
			{
				updateParameters(static_cast<double>(ellapsedTime) / durationMillSecond);
				mSubLoopDownCount = mNumSubLoops;
			}

			if (mTimeCheckDownCount <= 0)
			{
				if ((ellapsedTime = getTime() - mStartTime) < durationMillSecond)
				{
					mTimeCheckDownCount = mNumTimerCheckLoops;
				}
				else
				{
					break;
				}
			}
		}

		showCompleteInfo();
	}

	void runByNumLoops(const ll numLoops)
	{
		mStartTime = getTime();

		updateParameters(0.0);
		mSubLoopDownCount = mNumSubLoops;

		while (mLoopCount < numLoops)
		{
			runOnce();
			if (mSubLoopDownCount <= 0)
			{
				updateParameters(static_cast<double>(mLoopCount) / numLoops);
				mSubLoopDownCount = mNumSubLoops;
			}
		}

		showCompleteInfo();
	}

	void showCompleteInfo() const
	{
#ifdef SA_DEBUG
		fprintf(stderr, "Start Score   = %12.2f\n", mStartScore);
		fprintf(stderr, "Best  Score   = %12.2f\n", mBestScore);
		fprintf(stderr, "Loop Count    = %12lld\n", mLoopCount);
		fprintf(stderr, "Time          = %12d ms\n", getTime() - mStartTime);
#endif // SA_DEBUG
	}

	double computeTemp(double progressRatio) const
	{
		const double x = progressRatio;
		const double xp = pow(mNumMultiStart * x - floor(mNumMultiStart * x), mTempExponential);	// [0,1]
		const double stepped_max = (mMaxEndTemp - mMaxStartTemp) * floor(mNumMultiStart * x) / mNumMultiStart + mMaxStartTemp; // 最大値の階段関数
		const double y = mMinTemp * xp + stepped_max * (1.0 - xp);
		return y;
	}

	// 時刻・進行割合・温度の更新
	void updateParameters(double progressRatio)
	{
		mProgressRatio = progressRatio;
		// mTemp = mStartTemp + (mEndTemp - mStartTemp) * sqrt(mProgressRatio);	// TODO : 等差等比mixなど、ありうる。
		mTemp = computeTemp(mProgressRatio);
		mInvTemp = 1.0 / mTemp;
		mCurrentState.saSetProgressRatio(mProgressRatio, mTemp);
		mCurrentScore = mCurrentState.saScore();

#ifdef SA_STATS
		PHASE	phase;
		phase.neighbors.resize(STATE::NUM_NEIGHBORS); // これだと複数のSAをやるとき、まずいので、新しいneighborがでてきたとき初期化resizeという手もある。
		mPhases.push_back(phase);
#endif // SA_STATS

	}

	void runOnce()
	{
#ifdef SA_SCORE_CHECKER
		const double beforeScore = mCurrentState.saScore();
		//		if (mLoopCount==13)
		//		{
		//			fprintf(stderr, "For breakpoint.\n");
		//		}
#endif // SA_SCORE_CHECKER

		const double deltaScore = mCurrentState.saMove();

#ifdef SA_SCORE_CHECKER
		const double afterScore = mCurrentState.saScore();
		const double realDeltaScore = afterScore - beforeScore;
		if (!ISEQUAL(realDeltaScore, deltaScore))
		{
			fprintf(stderr, "Error! Loop Count=%lld realDeltaScore=%8.2f deltaScore=%8.2f\n", mLoopCount, realDeltaScore, deltaScore);
			exit(0);
		}
#endif // SA_SCORE_CHECKER



		bool isAccepted = deltaScore > 0;	// スコアが良くなった

#ifdef SA_STATS
		const int	neighborID = mCurrentState.saGetNeighborID();
		PHASE&		phase = mPhases.back();
		NEIGHBOR&	neighbor = phase.neighbors[neighborID];
		phase.countTurns++;
#endif // SA_STATS

		// 焼きなましのときはスコアが悪くなっても
		// 最初progressRatio=0.0のときは、スコアが良くなろうが悪くなろうが、常にnextを使用
		// 最後progressRatio=1.0のときは、スコアが改善したときのみ、nextを使用
		if (mAlgorithmMode == SA && !isAccepted)
		{
			const double expCut = -6;
			double left;
			double v = deltaScore * mInvTemp;
			if (v < expCut)
			{
				isAccepted = false;
				left = 0.0;
			}
			else
			{
				left = exp(v);
				const double r = mRandXor.nextDouble();
				isAccepted = left > r;	// スコアが悪くなっても強制遷移
			}


#ifdef SA_STATS
			if (isAccepted)
			{
				neighbor.countAcceptedMinus++;
			}
			else
			{
				if (left > 0.0001)
				{
					neighbor.countRejectedMinus++;
				}
				else
				{
					neighbor.countImpossible++;
				}
			}
#endif // SA_STATS
			//			fprintf(stderr, "temp=%f deltaScore=%f left=%f ac=%d\n", mTemp, deltaScore, left, (int)isAccepted);
		}
		else
		{
#ifdef SA_STATS
			neighbor.countAcceptedPlus++;
#endif // SA_STATS
		}

		if (isAccepted)
		{
			mCurrentScore += deltaScore;
			mCurrentState.saForward();
		}
		else
		{
			mCurrentState.saResume();
		}

		// ベストスコアは
		if (mCurrentScore > mBestScore)
		{
			mBestScore = mCurrentScore;
			mBestState = mCurrentState;
			mBestTime = mLoopCount;
//			fprintf(stderr, "New best Score=%8.2f time=%9lld (%.3f)\n", mBestScore, mLoopCount, mProgressRatio);
		}

		mLoopCount++;
		mSubLoopDownCount--;
		mTimeCheckDownCount--;

#ifdef SA_STATS
		phase.totalCurrentScore += mCurrentScore;
		phase.totalBestScore += mBestScore;
#endif // SA_STATS
	}

#ifdef SA_STATS
	struct NEIGHBOR
	{
		ll getCountAll() const
		{
			return countAcceptedPlus + countAcceptedMinus + countRejectedMinus + countImpossible;
		}

		double getRatioAcceptedPlus() const
		{
			return static_cast<double>(countAcceptedPlus) / getCountAll();
		}

		double getRatioAcceptedMinus() const
		{
			return static_cast<double>(countAcceptedMinus) / getCountAll();
		}

		double getRatioRejectedMinus() const
		{
			return static_cast<double>(countRejectedMinus) / getCountAll();
		}

		double getRatioImpossible() const
		{
			return static_cast<double>(countImpossible) / getCountAll();
		}

		ll countAcceptedPlus = 0;	// deltaScoreプラスでaccepted
		ll countAcceptedMinus = 0;	// deltaScoreマイナスでaccepted
		ll countRejectedMinus = 0;	// deltaScroreマイナスでrejected
		ll countImpossible = 0;	// deltaScoreが低すぎてrejected
	};

	struct PHASE
	{
		ll countTurns = 0;
		double totalCurrentScore = 0;
		double totalBestScore = 0;
		vector <NEIGHBOR> neighbors;
		double getAverageCurrentScore() const
		{
			return totalCurrentScore / countTurns;
		}
		double getAverageBestScore() const
		{
			return totalBestScore / countTurns;
		}
	};

	vector <PHASE>	mPhases;

	void	showStats() const
	{
		for (int phaseID = 0; phaseID < SZ(mPhases); phaseID++)
		{
			const PHASE& phase = mPhases[phaseID];
			fprintf(stderr, "%5d %lld current=%8.2f best=%8.2f"
				, phaseID
				, phase.countTurns
				, phase.getAverageCurrentScore()
				, phase.getAverageBestScore()
			);

			for (int neighborID = 0; neighborID < SZ(phase.neighbors); ++neighborID)
			{
				const NEIGHBOR& neighbor = phase.neighbors[neighborID];

				fprintf(stderr, "[%1d]=%5lld(%4lld/%4lld/%4lld/%4lld)"
					, neighborID
					, neighbor.getCountAll()
					, neighbor.countAcceptedPlus
					, neighbor.countAcceptedMinus
					, neighbor.countRejectedMinus
					, neighbor.countImpossible
				);

			}

			fprintf(stderr, "\n");
		}
		fprintf(stderr, "LoopCount = %lld\n", mLoopCount);
	}
#endif // SA_STATS

	double	mCurrentScore = 0.0;
	double	mBestScore = 0.0;
	double	mStartScore = 0.0;

private:
	AlgorithmMode	mAlgorithmMode = SA;

	RandXor	mRandXor;

	double	mMaxStartTemp = 2.0;
	double	mMaxEndTemp = 0.001;
	double	mMinTemp = 0.001;
	double  mTempExponential = 1.0;
	int		mNumMultiStart = 1;

	double	mProgressRatio = 0.0;
	double	mTemp = 0.0;
	double  mInvTemp = 0.0;

	STATE	mCurrentState;
	STATE	mBestState;
	STATE	mStartState;

	ll		mLoopCount = 0;
	ll		mSubLoopDownCount = 0;
	ll		mNumSubLoops = 0;
	ll		mNumTimerCheckLoops = 0;
	ll		mTimeCheckDownCount = 0;
	ll		mBestTime = 0;
	ll		mStartTime;
};

class Problem
{
public:
	int Main(int caseID, const vector <double>& coefs);


	int D;
	vector <ll> c;
	vector < vector <ll> > s;
	vector <double> mCoefs;
};

const static int NUM_TYPE = 26;

int Gx;

class State : public IState
{
public:
	State()
	{
	}

	State(Problem* pr)
	{
		this->pr = pr;
	}

	void	saInit() override
	{
		D = pr->D;
		ctype.resize(D);
		for (int d=0;d<D;d++)
		{
			ctype[d] = d%NUM_TYPE;
		}
	}

	double	saScore() override
	{
		ll sat = 0;

		vector <ll> last(NUM_TYPE, 0);

		for (int d = 0; d < D; d++)
		{
			const int j = ctype[d];
			last[j] = d + 1;
			for (int i = 0; i < NUM_TYPE; i++)
			{
				sat -= (d + 1 - last[i]) * pr->c[i];
			}
			sat += pr->s[d][j];
		}

		return sat;
	}

	int sum(int a, int b)
	{
		int diff = abs(b - a) - 1;

		return diff * (diff + 1) / 2;
	}

	int deltaScore(int day)
	{
		int ret = 0;

		ret += pr->s[day][ctype[day]];

		int prev = day;
		for (prev = day - 1; prev >= 0; prev--)
		{
			if (ctype[prev] == ctype[day])
			{
				break;
			}
		}

		int next = day;
		for (next = day + 1; next < D; next++)
		{
			if (ctype[next] == ctype[day])
			{
				break;
			}
		}

		ret -= sum(prev, day) * pr->c[ctype[day]];
		ret -= sum(day, next) * pr->c[ctype[day]];
		ret += sum(prev, next) * pr->c[ctype[day]];

		return ret;
	}

	double	saMove() override
	{
		if (rnd.nextInt(100) < 71) // pr->mCoefs[0])
		{
			neighborType = 0;
		}
		else
		{
			neighborType = 1;
		}

		ll realDeltaScore = 0;

		if (neighborType == 0)
		{
			// Move
			day = rnd.nextInt(D);
			backupType = ctype[day];

			realDeltaScore -= deltaScore(day);

			ctype[day] = rnd.nextInt(NUM_TYPE);
			realDeltaScore += deltaScore(day);
		}
		else if (neighborType == 1)
		{
			// Swap
			int DIFFDAY = 35pr->mCoefs[1] * (1.0-mProgressRatio) + 1; // pr->mCoefs[1]
			int deltaDay = rnd.nextInt(DIFFDAY)+1;

			dayX = rnd.nextInt(D - DIFFDAY);
			dayY = dayX + deltaDay;

			realDeltaScore -= deltaScore(dayX);
			realDeltaScore -= deltaScore(dayY);

			swap(ctype[dayX], ctype[dayY]);

			realDeltaScore += deltaScore(dayX);
			realDeltaScore += deltaScore(dayY);
		}

		return realDeltaScore;
	}

	void	saForward() override
	{
	}

	void	saResume() override
	{
		if (neighborType == 0)
		{
			ctype[day] = backupType;
		}
		else if (neighborType == 1)
		{
			swap(ctype[dayX], ctype[dayY]);
		}
	}

	void	saSetProgressRatio(double progressRatio, double temp) override
	{
		mProgressRatio = progressRatio;
	}

#ifdef SA_STATS
	int 	saGetNeighborID() override
	{
		return 0;
	}

#endif // SA_STATS

	int neighborType;
	int day;

	int dayX;
	int dayY;

	double mProgressRatio;

	int backupType;
	RandXor rnd;
	Problem* pr;
	vector <int> ctype;
	int D;
};



int Problem::Main(int caseID, const vector <double>& coefs)
{
#ifndef SUBMISSION
	char input_path[256];
	char output_path[256];

	sprintf(input_path,  "../data/input%d.txt", caseID);
	sprintf(output_path, "../data/output%d.txt", caseID);
	ifstream fin(input_path);
	ofstream fout(output_path);
#endif

	INPUT(D);

	c.resize(NUM_TYPE);
	for (int i = 0; i < NUM_TYPE; ++i)
	{
		INPUT(c[i]);
	}

	s.resize(D);
	for (int d = 0; d < D; d++)
	{
		s[d].resize(NUM_TYPE);
		for (int i = 0; i < NUM_TYPE; ++i)
		{
			INPUT(s[d][i]);
		}
	}

	mCoefs = coefs;
	cerr << " mCoefs[0]=" << mCoefs[0] << " mCoefs[1]=" << mCoefs[1] << endl;


	State state(this);
	SimulatedAnnealing<State> sa;

	double          maxTemp = 1279.4769503029124; // , coefs[0];
	double          minTemp = 0.001;
	double          tempExponential = 1.7683454429921237; // coefs[1];
	int             numMultiStart = 1;

	sa.init(state, SA, 5000, 1000, maxTemp, maxTemp, minTemp, tempExponential, numMultiStart);

#if 0
	ll startTime = getTime();
	sa.runByNumLoops(static_cast<ll>(3e6));
	cerr << "Duration= " << getTime() - startTime << endl;
#else
	ll startTime = getTime();
	ll endTime = startTime + 1900;
	sa.runByClock(endTime - getTime());
#endif

#ifdef SA_STATS
	sa.showStats();
#endif // SA_STATS

	auto s = sa.getBestState();

	for (int d = 0; d < D; d++)
	{
		OUTPUT(s.ctype[d]+1);
	}

	return max(0LL, (1000000 + (ll) sa.getBestScore()));
}

int main(int argc, char *argv[])
{
	vector <double> coefs(argc - 1);
	for (int i = 0; i < SZ(coefs); ++i)
	{
		coefs[i] = atof(argv[i + 1]);
	}

	cerr << " coefs[0]=" << coefs[0] << " coefs[1]=" << coefs[1] << endl;


	int totalScore = 0;
	for (int caseID = 1; caseID <= 1; caseID++)
	{
		Problem* problem = new Problem();

		const int score = problem->Main(caseID, coefs);
//		cerr << "*** caseID=" << caseID << " score=" << score << endl;
		
		totalScore += score;

		delete problem;
	}

//	cout << totalScore << endl;

	return 0;
}


Compiler output:
a.cc: In member function 'virtual double State::saMove()':
a.cc:658:39: error: unable to find numeric literal operator 'operator""pr'
  658 |                         int DIFFDAY = 35pr->mCoefs[1] * (1.0-mProgressRatio) + 1; // pr->mCoefs[1]
      |                                       ^~~~