#1198287 (C++23(gcc16)) No.3221 Count Turns

• 問題: No.3221 Count Turns
• ユーザー: C
• 提出日時: 2026-11-12 01:14:20
• 言語: C++23(gcc16) (gcc 16.2.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 18 ms / 2,000 ms
• コード長: 3,522 bytes
• コンパイル時間: 7,348 ms
• コンパイル使用メモリ: 395,384 KB
• 実行使用メモリ: 12,460 KB
• 最終ジャッジ日時: 2026-11-12 01:14:34
• 合計ジャッジ時間: 11,281 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge5_0

ファイルパターン	結果
sample	AC * 1
other	AC * 38

ソースコード

#include <bits/stdc++.h>
#include <atcoder/all>
#include <boost/polygon/point_data.hpp>
#include <boost/polygon/voronoi.hpp>
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(x) begin(x),end(x)
#define sz(x) (int)(x).size()
using namespace std;
using namespace atcoder;
using ll=long long;
using ull=unsigned long long;
using ld=long double;
using vll=vector<ll>;
using vvll=vector<vll>;
using vi=vector<int>;
using vvi=vector<vi>;
using pll=pair<ll,ll>;
using pi=pair<int,int>;

// using mint=modint998244353;
using mint=modint1000000007;
// using mint2=static_modint<2>;

// using BoostPoint=boost::polygon::point_data<int>;
// using Voronoi=boost::polygon::voronoi_diagram<double>;

// using mint=LazyMontgomeryModInt<998244353>;
using vm=vector<mint>;
using vvm=vector<vm>;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

	/**
	 * O(N) (H,T<=1e18でも解ける)
	 * 1. 周期イベント化
	 * 時刻 t を、全 B_i に A_i を加算した累計回数とする
	 * d_i=ceil(H/A_i), w_i=d_i*A_i とおく
	 * 添字 i は時刻 d_i,2d_i,3d_i,... に必ず選ばれ
	 * その k 回目のイベントのキーは (k*d_i,-w_i,i) となる
	 * よって、求めるのは全イベントをキー順に並べた先頭のT個です。
	 * 
	 * F(t)　= \sum_i floor(t/d_i) を時刻 t までのイベント数とする（実数 t>=0）
	 * F(t) は O(N) で計算できるので、二分探索で T 番目の
	 * イベントの時刻を求め、同時刻のイベントを処理すれば解ける　(でもlog付き)
	 * 
	 * 2. 2 段階の近似による高速化
	 * S = \sum_i 1/d_i を考えます（floorを無視したもの）
	 * 
	 * 第 1 の近似：F(t) \approx t*S
	 * t*S-N < F(t) <= t*S
	 * 誤差は時刻 t に依存せず N 未満なので
	 * T 番目のイベントを含む O(N) 個の候補に絞れる。
	 * 
	 * 第 2 の近似：S \approx P/K
	 * S は有理数なので、正確な計算は重いため、適当な K に対して P=F(K) とする
	 * 第 1 の近似から　P/K <= S < (P+N)/K が成り立つ
	 * つまり、O(N)時間でSを近似できる。
	 * 
	 * D=T+N, dmin=min_i d_i, K=D*dmin と選べば P>=D
	 * 2 つの近似の誤差を合成して逆算すると
	 * l=floor(T*K/(P+N)), u=floor(D*K/P)
	 * について次が保証される
	 * 	F(l)　<　T　<　F(u)
	 * 	F(u)-F(l)　<　2N　+　D*N/P　<=　3N
	 * 
	 * つまり、正確な時刻を二分探索する代わりに
	 * T 番目を含む 3N 個未満の候補を一度に特定できる。
	 *
	 * 3. 確定部分を一括計数し、残りだけ線形選択
	 * C_i=floor(l/d_i) は添字 i の確定済みイベント数
	 * R=T-\sum_i C_i 個を追加で選べば良い
	 *
	 * 候補は C_i<k<=floor(u/d_i) を満たす全 (k*d_i,-w_i,i)
	 * 候補総数は 3N 未満なので、すべて O(N) 時間で列挙できる
	 * nth_elementを使えばO(N)で答えを求める
	 */

	int N;
	ll H,T;
	cin>>N>>H>>T;
	vll d(N+1),w(N+1),C(N+1);
	ll dmin=LLONG_MAX;
	rep(i,1,N+1){
		ll A;
		cin>>A;
		d[i]=(H+A-1)/A;
		w[i]=d[i]*A;
		dmin=min(dmin,d[i]);
	}

	ll D=T+N,K=D*dmin,P=0;
	rep(i,1,N+1)P+=K/d[i];
	ll l=T*K/(P+N),u=D*K/P;

	ll R=T;
	vector<tuple<ll,ll,int>>events;
	rep(i,1,N+1){
		C[i]=l/d[i];
		R-=C[i];
		rep(k,C[i]+1,u/d[i]+1)events.emplace_back(k*d[i],-w[i],i);
	}

	nth_element(events.begin(),events.begin()+R-1,events.end());
	rep(j,0,R)C[get<2>(events[j])]++;
	
	cout<<C[1];
	rep(i,2,N+1)cout<<' '<<C[i];
	cout<<'\n';
}