あったこといろいろ

ほぼ自分用備忘録です。

AOJ 2282: Problem B

Problem B | Aizu Online Judge
問題が長くてややこしいけれど、考察すると意外と簡単

考察・解法

問題文を素直に読むと自分より前の申請を考慮した場合分けが必要に見えるが、考えると実は不要であることがわかる。

  • 申請の時点で自分が担当者にならない申請ができる場合、"B問題の担当者"から外れられることが確定する。"B問題の担当者"になり得ない人の作業時間は結果に影響しないので、Mを超えない最大の"難易度の倍数"の値を申請すると考えて良い。
  • 申請の時点で自分が担当者にならない申請ができない場合、問題文通りMを超えない最大の"難易度の倍数"の値を申請する。

つまり、全ての人は前の人の状態にかかわらず、Mを超えない最大の"難易度の倍数"の値を申請すると考えることができる。

なお、申請が嘘かどうかの判定をする必要はない。
なぜならば、すべての人は作業時間を0と申請することが可能なので必ず嘘とバレない申請をできるからである。


あとは考察によって簡単になったシミュレーションを行い、pairの比較演算の特性を利用してソートすると意外とスッキリ解ける。

#include "bits/stdc++.h"
using namespace std;
typedef pair<int,int> pii;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define all(a)  (a).begin(),(a).end()

int under(int v,int m){
	int ret=0;
	while(ret+v<=m)ret+=v;
	return ret;
}

int main(){
	int n,m;
	while(cin>>n>>m&&(n||m)){
		vector<pair<pii,int>> vec;	//各人の 作業時間、問題難易度、識別番号を持つ
		vector<int> v(n);
		rep(i,n)cin>>v[i];
		
		rep(i,n){
			int time=under(v[i],m);	//i番目の人が申請する作業時間
			int diffi=v[i];		//i番目の人が担当した問題の難易度
			vec.push_back( make_pair(pii(time,diffi),i) );
		}
		sort(all(vec));
		if(vec[0].first==vec[1].first)cout<<n<<endl;	//time,difficultが最小の人が複数居た場合
		else cout<<vec[0].second+1<<endl;		//time,difficultが最小の人が一意に決まる場合
	}
}