結果
| 問題 | No.5018 Let's Make a Best-seller Book |
| ユーザー |
 rhoo
|
| 提出日時 | 2023-10-01 15:30:30 |
| 言語 | Rust (1.77.0 + proconio) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 12,127 bytes |
| コンパイル時間 | 1,392 ms |
| コンパイル使用メモリ | 166,348 KB |
| 実行使用メモリ | 4,376 KB |
| スコア | 0 |
| 最終ジャッジ日時 | 2023-10-01 15:30:42 |
| 合計ジャッジ時間 | 4,767 ms |
|
ジャッジサーバーID （参考情報） |
judge11 / judge12 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | TLE | - |
| testcase_01 | -- | - |
| testcase_02 | -- | - |
| testcase_03 | -- | - |
| testcase_04 | -- | - |
| testcase_05 | -- | - |
| testcase_06 | -- | - |
| testcase_07 | -- | - |
| testcase_08 | -- | - |
| testcase_09 | -- | - |
| testcase_10 | -- | - |
| testcase_11 | -- | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
| testcase_26 | -- | - |
| testcase_27 | -- | - |
| testcase_28 | -- | - |
| testcase_29 | -- | - |
| testcase_30 | -- | - |
| testcase_31 | -- | - |
| testcase_32 | -- | - |
| testcase_33 | -- | - |
| testcase_34 | -- | - |
| testcase_35 | -- | - |
| testcase_36 | -- | - |
| testcase_37 | -- | - |
| testcase_38 | -- | - |
| testcase_39 | -- | - |
| testcase_40 | -- | - |
| testcase_41 | -- | - |
| testcase_42 | -- | - |
| testcase_43 | -- | - |
| testcase_44 | -- | - |
| testcase_45 | -- | - |
| testcase_46 | -- | - |
| testcase_47 | -- | - |
| testcase_48 | -- | - |
| testcase_49 | -- | - |
| testcase_50 | -- | - |
| testcase_51 | -- | - |
| testcase_52 | -- | - |
| testcase_53 | -- | - |
| testcase_54 | -- | - |
| testcase_55 | -- | - |
| testcase_56 | -- | - |
| testcase_57 | -- | - |
| testcase_58 | -- | - |
| testcase_59 | -- | - |
| testcase_60 | -- | - |
| testcase_61 | -- | - |
| testcase_62 | -- | - |
| testcase_63 | -- | - |
| testcase_64 | -- | - |
| testcase_65 | -- | - |
| testcase_66 | -- | - |
| testcase_67 | -- | - |
| testcase_68 | -- | - |
| testcase_69 | -- | - |
| testcase_70 | -- | - |
| testcase_71 | -- | - |
| testcase_72 | -- | - |
| testcase_73 | -- | - |
| testcase_74 | -- | - |
| testcase_75 | -- | - |
| testcase_76 | -- | - |
| testcase_77 | -- | - |
| testcase_78 | -- | - |
| testcase_79 | -- | - |
| testcase_80 | -- | - |
| testcase_81 | -- | - |
| testcase_82 | -- | - |
| testcase_83 | -- | - |
| testcase_84 | -- | - |
| testcase_85 | -- | - |
| testcase_86 | -- | - |
| testcase_87 | -- | - |
| testcase_88 | -- | - |
| testcase_89 | -- | - |
| testcase_90 | -- | - |
| testcase_91 | -- | - |
| testcase_92 | -- | - |
| testcase_93 | -- | - |
| testcase_94 | -- | - |
| testcase_95 | -- | - |
| testcase_96 | -- | - |
| testcase_97 | -- | - |
| testcase_98 | -- | - |
| testcase_99 | -- | - |
コンパイルメッセージ
warning: struct `IOLocal` is never constructed
--> Main.rs:212:8
|
212 | struct IOLocal{
| ^^^^^^^
|
= note: `#[warn(dead_code)]` on by default
warning: associated function `new` is never used
--> Main.rs:222:8
|
222 | fn new()->IOLocal{
| ^^^
warning: associated function `read` is never used
--> Main.rs:254:8
|
254 | fn read(&mut self){
| ^^^^
warning: associated function `write` is never used
--> Main.rs:307:8
|
307 | fn write(&mut self,ans:&[i64]){
| ^^^^^
warning: associated function `write_ad` is never used
--> Main.rs:316:8
|
316 | fn write_ad(&mut self,level:i64){
| ^^^^^^^^
warning: associated function `dump` is never used
--> Main.rs:324:8
|
324 | fn dump(&self){
| ^^^^
warning: 6 warnings emitted
ソースコード
#![allow(non_snake_case)]
#[cfg(local)]
type IO=IOLocal;
#[cfg(not(local))]
type IO=IOYuki;
fn main(){
get_time();
let mut IO=IO::new();
solve(&mut IO);
}
fn solve(IO:&mut IO){
let mut que=std::collections::BinaryHeap::new();
loop{
// todo
if IO.money>=(500000f64*2.).round() as i64 && 40>=IO.turn{
IO.write_ad(1);
IO.read();
continue;
}
let mut must=[0;N]; // R^0.5がこれより大きいとP-=1
let mut good=[0;N]; // R^0.5がこれ以下だとP+=1
let ratio=IO.turn as f64/(TURN-1) as f64;
// todo
let A=10.*lerp(0.7,0.7,ratio.powf(1.));
let B=10./3.*lerp(0.9,0.9,ratio.powf(1.));
for i in 0..N{
let w=IO.store[i].weight();
must[i]=(w*A) as i64;
good[i]=(w*B) as i64;
}
let rest=TURN-IO.turn;
let future_score=|n:usize,a:i64|->f64{
let P;
if a==0{
P=IO.store[n].P;
} else if a<=good[n]{
P=IO.store[n].P+1;
} else if a>must[n]{
P=IO.store[n].P-1;
} else{
P=IO.store[n].P;
};
let weight=1.05f64.powi(P as i32)*IO.store[n].D;
// todo
weight*rest as f64*0.15
};
let mut next=[0;N];
que.clear();
for i in 0..N{
let cur=IO.store[i].rest;
next[i]=cur;
let old=IO.store[i].predict(cur)+future_score(i,cur);
let new=IO.store[i].predict(cur+1)+future_score(i,cur+1);
que.push(O((new-old,i,cur+1)));
}
// たぶん、貪欲で最適になるとは限らないが、
let mut money=IO.money;
while let Some(O((diff,i,n)))=que.pop(){
// todo: diffの閾値
if diff<=0. || money<500{
break;
}
next[i]=n;
let old=IO.store[i].predict(n)+future_score(i,n);
let new=IO.store[i].predict(n+1)+future_score(i,n+1);
que.push(O((new-old,i,n+1)));
money-=500;
}
let mut ans=[0;N];
for i in 0..N{
ans[i]=next[i]-IO.store[i].rest;
}
IO.write(&ans);
IO.read();
}
}
#[derive(Clone,Copy,Default)]
struct Store{
P:i64, // 人気度
rest:i64, // 残り在庫数
D:f64, // 売れやすさの隠れパラメータ
}
impl Store{
fn weight(&self)->f64{
1.05f64.powi(self.P as i32)*self.D
}
// n冊入荷させたらどれくらい売れると予測されるのか
fn predict(&self,n:i64)->f64{
let ret=(n as f64).sqrt()*self.weight();
ret.min(n as f64)
}
}
const MONEY:i64=2000000;
const TURN:usize=52;
const N:usize=10;
struct IOYuki{
scan:Scanner,
turn:usize,
money:i64,
store:[Store;N],
history:Vec<Vec<f64>>,
score:i64,
}
impl IOYuki{
fn new()->IOYuki{
let mut scan=Scanner::new();
input!{
scan,
d:(usize,usize,i64),
}
assert!(d==(TURN,N,MONEY));
let store=[Store{P:0,rest:0,D:1.};N];
let history=vec![vec![1.];N]; // todo: 重み
IOYuki{
scan,
turn:0,
money:MONEY,
store,
history,
score:0,
}
}
fn read(&mut self){
input!{
self.scan,
money:i64,
s:[i64;N], // 売れたやつ
p:[i64;N], // 人気度
r:[i64;N], // 残り
}
let add=s.iter().sum::<i64>();
self.score+=add;
self.money+=add*1000;
for i in 0..N{
// historyを更新する
// min(n,n^0.5*1.05^P*D)=s[i]
// n^0.5*1.05^P*D=s[i]
// s[i]/(n^0.5)/(1.05^P)=D
let mut d=s[i] as f64/(self.store[i].rest as f64).sqrt()/1.05f64.powi(self.store[i].P as i32);
d=d.clamp(0.5,1.5);
self.history[i].push(d);
self.store[i].P=p[i];
assert!(self.store[i].rest==s[i]+r[i]);
self.store[i].rest=r[i];
let D=self.history[i].iter().sum::<f64>()/self.history[i].len() as f64;
assert!(0.5<=D && D<=1.5);
self.store[i].D=D;
}
assert!(self.money==money);
self.turn+=1;
if self.turn==TURN{
std::process::exit(0);
}
}
fn write(&mut self,ans:&[i64]){
print!("1");
for i in 0..N{
let n=ans[i];
print!(" {}",n);
self.store[i].rest+=n;
self.money-=n*500;
}
println!();
assert!(0<=self.money);
}
fn write_ad(&mut self,level:i64){
println!("2 {}",level);
self.money-=500000*2i64.pow(level as u32-1);
for i in 0..N{
self.store[i].P+=level;
}
assert!(0<=self.money);
}
}
struct IOLocal{
d:[f64;N],
table:[[f64;N];TURN],
turn:usize,
money:i64,
store:[Store;N],
history:Vec<Vec<f64>>,
score:i64,
}
impl IOLocal{
fn new()->IOLocal{
let mut scan=Scanner::new();
input!{
scan,
i_d:[f64;N],
i_table:[[f64;N];TURN],
}
let mut d=[0.;N];
for i in 0..N{
d[i]=i_d[i];
}
let mut table=[[0.;N];TURN];
for i in 0..TURN{
for j in 0..N{
table[i][j]=i_table[i][j];
}
}
let store=[Store{P:0,rest:0,D:1.};N];
let history=vec![vec![1.];N];
IOLocal{
d,table,
turn:0,
money:MONEY,
store,
history,
score:0,
}
}
fn read(&mut self){
let mut s=[0;N];
let mut p=[0;N];
let mut r=[0;N];
for i in 0..N{
let new=self.store[i].predict(self.store[i].rest)*self.table[self.turn][i];
s[i]=(new as i64).min(self.store[i].rest as i64);
r[i]=self.store[i].rest-s[i];
p[i]=self.store[i].P;
if self.store[i].rest==0{
continue;
}
if 0.3*self.store[i].rest as f64<=new{
p[i]+=1;
} else if new<0.1*self.store[i].rest as f64{
p[i]-=1;
}
}
let add=s.iter().sum::<i64>();
self.score+=add;
self.money+=add*1000;
for i in 0..N{
// historyを更新する
// min(n,n^0.5*1.05^P*D)=s[i]
// n^0.5*1.05^P*D=s[i]
// s[i]/(n^0.5)/(1.05^P)=D
let mut d=s[i] as f64/(self.store[i].rest as f64).sqrt()/1.05f64.powi(self.store[i].P as i32);
if d.is_nan(){
d=1.;
}
d=d.clamp(0.5,1.5);
self.history[i].push(d);
self.store[i].P=p[i];
assert!(self.store[i].rest==s[i]+r[i]);
self.store[i].rest=r[i];
let D=self.history[i].iter().sum::<f64>()/self.history[i].len() as f64;
assert!(0.5<=D && D<=1.5);
self.store[i].D=D;
}
self.turn+=1;
if self.turn==TURN{
self.dump();
std::process::exit(0);
}
}
fn write(&mut self,ans:&[i64]){
for i in 0..N{
let n=ans[i];
self.store[i].rest+=n;
self.money-=n*500;
}
assert!(0<=self.money);
}
fn write_ad(&mut self,level:i64){
self.money-=500000*2i64.pow(level as u32-1);
for i in 0..N{
self.store[i].P+=level;
}
assert!(0<=self.money);
}
fn dump(&self){
eprintln!("score = {}",self.score);
}
}
#[allow(unused)]
fn get_time()->f64{
static mut START:f64=-1.;
let time=std::time::SystemTime::now().duration_since(std::time::UNIX_EPOCH).unwrap().as_secs_f64();
unsafe{
if START<0.{
START=time;
}
#[cfg(local)]{
(time-START)*1.6
}
#[cfg(not(local))]{
time-START
}
}
}
#[macro_export]
macro_rules! timer{
()=>{
#[cfg(local)]
let _timer=Timer(get_time());
}
}
static mut TIME:f64=0.;
struct Timer(f64);
impl Drop for Timer{
fn drop(&mut self){
unsafe{
TIME+=get_time()-self.0
}
}
}
#[allow(unused)]
mod rnd {
static mut N:usize=0xcafef00dd15ea5e5;
// 注意: 上の方のbitが0になってる
pub fn next()->usize{
unsafe{
let x=N;
N*=6364136223846793005;
(x^x>>22)>>(22+(x>>61))
}
}
pub fn hash()->u64{
unsafe{
let x=N;
N*=6364136223846793005;
x as u64
}
}
pub fn nextf()->f64{
unsafe{
std::mem::transmute::<u64,f64>(0x3ff0000000000000|(next() as u32 as u64)<<20)-1.
}
}
pub fn range(a:usize,b:usize)->usize{
assert!(a<b);
next()%(b-a)+a
}
pub fn range_skip(a:usize,b:usize,skip:usize)->usize{
assert!(a<=skip && skip<b);
let ret=range(a,b-1);
ret+(skip<=ret) as usize
}
pub fn rangei(a:i64,b:i64)->i64{
assert!(a<b);
(next()%((b-a) as usize)) as i64+a
}
pub fn shuffle<T>(list:&mut [T]){
for i in (0..list.len()).rev(){
list.swap(i,next()%(i+1));
}
}
}
trait RandomChoice{
type Output;
fn choice(&self)->&Self::Output;
}
impl<T> RandomChoice for [T]{
type Output=T;
fn choice(&self)->&T{
&self[rnd::next() as usize%self.len()]
}
}
struct Scanner{
stack:std::str::SplitAsciiWhitespace<'static>
}
impl Scanner{
// fn new()->Self{
// use std::io::Read;
// let mut tmp=String::new();
// std::io::stdin().read_to_string(&mut tmp).unwrap();
// Self{stack:Box::leak(tmp.into_boxed_str()).split_ascii_whitespace()}
// }
// fn read<T:std::str::FromStr>(&mut self)->T{
// self.stack.next().unwrap().parse::<T>().unwrap_or_else(|_|panic!("parse error {}",std::any::type_name::<T>()))
// }
// インタラクティブ用
fn new()->Self{
Self{stack:"".split_ascii_whitespace()}
}
fn read<T:std::str::FromStr>(&mut self)->T{
loop{
if let Some(v)=self.stack.next(){
return v.parse::<T>().unwrap_or_else(|_|panic!("{}: parse error",std::any::type_name::<T>()));
}
let mut tmp=String::new();
std::io::stdin().read_line(&mut tmp).unwrap();
assert!(!tmp.is_empty());
self.stack=Box::leak(tmp.into_boxed_str()).split_ascii_whitespace();
}
}
}
#[macro_export]
macro_rules! input{
($scan:expr $(,)?)=>{};
($scan:expr, mut $name:ident:$t:tt $($rest:tt)*)=>{
let mut $name=read_value!($scan,$t);
input!{$scan $($rest)*}
};
($scan:expr, $name:ident:$t:tt $($rest:tt)*)=>{
let $name=read_value!($scan,$t);
input!{$scan $($rest)*}
};
}
#[macro_export]
macro_rules! read_value{
($scan:expr, ($($t:tt),*))=>{
($(read_value!($scan, $t)),*)
};
($scan:expr, [$t:tt;$len:expr])=>{
(0..$len).map(|_|read_value!($scan,$t)).collect::<Vec<_>>()
};
($scan:expr, [$t:tt])=>{
(0..$scan.read()).map(|_|read_value!($scan,$t)).collect::<Vec<_>>()
};
($scan:expr, Chars)=>{
read_value!($scan,String).chars().collect::<Vec<char>>()
};
($scan:expr, Usize1)=>{
read_value!($scan,usize)-1
};
($scan:expr, $t:ty)=>{
$scan.read::<$t>()
};
}
fn lerp(a:f64,b:f64,t:f64)->f64{
a+(b-a)*t
}
#[derive(PartialEq,PartialOrd)]
struct O<T:PartialEq+PartialOrd>(T);
impl<T:PartialEq+PartialOrd> Eq for O<T>{}
impl<T:PartialEq+PartialOrd> Ord for O<T>{
fn cmp(&self,a:&O<T>)->std::cmp::Ordering{
self.0.partial_cmp(&a.0).unwrap()
}
}