#917201 (Rust) No.5018 Let's Make a Best-seller Book

提出ソース

結果

問題	No.5018 Let's Make a Best-seller Book
ユーザー	rhoo
提出日時	2023-10-01 15:41:57
言語	Rust (1.77.0 + proconio)
結果	TLE
実行時間	-
コード長	12,276 bytes
コンパイル時間	1,062 ms
コンパイル使用メモリ	168,236 KB
実行使用メモリ	4,384 KB
スコア	0
最終ジャッジ日時	2023-10-01 15:42:01
合計ジャッジ時間	4,817 ms
ジャッジサーバーID （参考情報）	judge11 / judge13

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
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:220:8
    |
220 | struct IOLocal{
    |        ^^^^^^^
    |
    = note: `#[warn(dead_code)]` on by default

warning: associated function `new` is never used
   --> Main.rs:230:8
    |
230 |     fn new()->IOLocal{
    |        ^^^

warning: associated function `read` is never used
   --> Main.rs:262:8
    |
262 |     fn read(&mut self){
    |        ^^^^

warning: associated function `write` is never used
   --> Main.rs:315:8
    |
315 |     fn write(&mut self,ans:&[i64]){
    |        ^^^^^

warning: associated function `write_ad` is never used
   --> Main.rs:324:8
    |
324 |     fn write_ad(&mut self,level:i64){
    |        ^^^^^^^^

warning: associated function `dump` is never used
   --> Main.rs:332:8
    |
332 |     fn dump(&self){
    |        ^^^^

warning: 6 warnings emitted

ソースコード

raw source code

#![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();
    IO.write_ad(2);
    IO.read();
    loop{
        // todo
        if IO.money>=(500000f64*2.).round() as i64 && 38>=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;
        }
        print!("\n");
        stdout().flush().unwrap();
        assert!(0<=self.money);
        panic!();
    }

    fn write_ad(&mut self,level:i64){
        println!("2 {}",level);
        stdout().flush().unwrap();
        self.money-=500000*2i64.pow(level as u32-1);
        for i in 0..N{
            self.store[i].P+=level;
        }
        assert!(0<=self.money);
    }
}


use std::io::{stdout, Write};



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()
    }
}

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード