Codeforces Beta Round #90 C: Education Reform

Codeforces

問題概要

長さM(<50)の配列A, B, C(A[i]

考えたこと

  • B[i] - A[i] <= 100がどう見ても怪しい。
  • Cが単調増加ということは最初にCでソートしておけばOK。
  • 復元は直前の状態を覚えておけばよいから、総和を値としたDPか。
  • 最小必要な状態は(いくつ目、何番目に選んだか、今のXの値)。もちろん今のXの値はa[i]からの差分で覚えておく。
    • 今にして思えばmapでよかったような気もするが、map使ってTLEしていた人もいたので微妙。
  • で、後ろの方全部に配る。状態数がO(M*N*DIFF)で遷移にO(M)なので全体としてはO(N*DIFF*M^2)。いちおう間に合いそう。
  • というか本当に何の工夫もない問題だなあ。
  • あとはひたすらガリガリ書く。
  • 長さNのDPって、0番目に番兵っぽいのを置いてdp[N]みたいなのを最後の値にするのが大抵綺麗なんだけど、今回は基底の設定が面倒なのでdp[N-1]が最終的な答えとなって自分の中の美意識に反する。
  • 無事通ってた。unratedでみんなやる気が無かったとはいえ20位という自分にしてはよくできた結果だった。

本番で通ったコード

#include <iostream>
#include <vector>
#include <cstdio>
#include <algorithm>
using namespace std;

typedef long long int64;

const int MAX_M = 100;
const int MAX_DIFF = 100;

int N, M, K;
int64 as[MAX_M], bs[MAX_M];
int cs[MAX_M];
int64 dp[MAX_M][MAX_M][MAX_DIFF + 1]; //(幾つ目、何教科目、a[i] + いくつ)
bool visited[MAX_M][MAX_M][MAX_DIFF + 1];
pair<int,int> prev[MAX_M][MAX_M][MAX_DIFF + 1]; //(何教科目、a[prev] + いくつ)

struct subject{
	int64 a, b, c, orig;
};

subject subs[MAX_M];

bool operator<(const subject& lhs, const subject& rhs){
	return lhs.c < rhs.c;
}

void solve(){

	for(int i=0; i<M; i++){
		for(int j=0; j<=subs[i].b - subs[i].a; j++){
			dp[i][0][j] = subs[i].a + j;
			visited[i][0][j] = true;
		}
	}

	for(int i=0; i<M-1; i++){
		for(int j=0; j<N-1; j++){
			for(int k=0; k<=subs[i].b - subs[i].a; k++)if(visited[i][j][k]){
				int64 cur = subs[i].a + k;
				int64 add_next = cur + K;
				int64 multy_next = cur * K;

				for(int l=i+1; l<M; l++)if(subs[i].c < subs[l].c){
					//加算
					if(subs[l].a <= add_next && add_next <= subs[l].b){
						if( (!visited[l][j+1][add_next - subs[l].a]) || dp[l][j+1][add_next - subs[l].a] < add_next + dp[i][j][k]){
							dp[l][j+1][add_next - subs[l].a] = add_next + dp[i][j][k];
							visited[l][j+1][add_next - subs[l].a] = true;
							prev[l][j+1][add_next - subs[l].a] = make_pair(i, k);
						}
					}
					//積算
					if(subs[l].a <= multy_next && multy_next <= subs[l].b){
						if( (!visited[l][j+1][multy_next - subs[l].a]) || dp[l][j+1][multy_next - subs[l].a] < multy_next + dp[i][j][k]){
							dp[l][j+1][multy_next - subs[l].a] = multy_next + dp[i][j][k];
							visited[l][j+1][multy_next - subs[l].a] = true;
							prev[l][j+1][multy_next - subs[l].a] = make_pair(i, k);
						}
					}
				}
			}
		}
	}

	int64 best = -1;
	int key_id = -1, key_diff = -1;
	for(int i=0; i<M; i++){
		for(int j=0; j<=MAX_DIFF; j++)if(visited[i][N-1][j]){
			if(best < dp[i][N-1][j]){
				best = dp[i][N-1][j];
				key_id = i;
				key_diff = j;
			}
		}
	}

	if(best == -1){
		puts("NO");
		return ;
	}
	puts("YES");
	vector<pair<int,int64> > path;
	for(int i=N-1; i>=0; i--){
		pair<int,int> cur = prev[key_id][i][key_diff];
		path.push_back( make_pair(subs[key_id].orig, subs[key_id].a + key_diff) );
		key_id = cur.first;
		key_diff = cur.second;
	}

	for(int i=N-1; i>=0; i--){
		cout << path[i].first << " " << path[i].second << endl;
	}
}

int main(){
	cin >> N >> M >> K;
	for(int i=0; i<M; i++){
		cin >> as[i] >> bs[i] >> cs[i];
		subs[i] = (subject){as[i], bs[i], cs[i], i+1};
	}
	sort(subs, subs+M);

	solve();

	return 0;
}