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

• 問題: No.5018 Let's Make a Best-seller Book
• ユーザー: rhoo
• 提出日時: 2023-10-01 16:25:08
• 言語: Rust (1.77.0)
• 結果: AC
• 実行時間: 51 ms / 400 ms
• コード長: 12,004 bytes
• コンパイル時間: 1,018 ms
• コンパイル使用メモリ: 168,028 KB
• 実行使用メモリ: 24,492 KB
• スコア: 917
• 平均クエリ数: 52.00
• 最終ジャッジ日時: 2023-10-01 16:25:17
• 合計ジャッジ時間: 9,012 ms
• ジャッジサーバーID （参考情報）: judge15 / judge14

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	30 ms; 24,048 KB
testcase_01	AC	26 ms; 24,024 KB
testcase_02	AC	26 ms; 23,844 KB
testcase_03	AC	28 ms; 23,820 KB
testcase_04	AC	26 ms; 24,036 KB
testcase_05	AC	26 ms; 23,376 KB
testcase_06	AC	26 ms; 23,664 KB
testcase_07	AC	26 ms; 23,520 KB
testcase_08	AC	27 ms; 23,820 KB
testcase_09	AC	27 ms; 23,628 KB
testcase_10	AC	26 ms; 24,024 KB
testcase_11	AC	27 ms; 23,676 KB
testcase_12	AC	26 ms; 23,520 KB
testcase_13	AC	26 ms; 23,844 KB
testcase_14	AC	27 ms; 23,376 KB
testcase_15	AC	27 ms; 23,412 KB
testcase_16	AC	27 ms; 24,036 KB
testcase_17	AC	29 ms; 24,348 KB
testcase_18	AC	51 ms; 24,024 KB
testcase_19	AC	26 ms; 23,652 KB
testcase_20	AC	26 ms; 24,264 KB
testcase_21	AC	27 ms; 24,036 KB
testcase_22	AC	26 ms; 23,640 KB
testcase_23	AC	27 ms; 24,420 KB
testcase_24	AC	27 ms; 23,412 KB
testcase_25	AC	27 ms; 24,024 KB
testcase_26	AC	27 ms; 23,652 KB
testcase_27	AC	27 ms; 24,264 KB
testcase_28	AC	27 ms; 23,400 KB
testcase_29	AC	27 ms; 23,532 KB
testcase_30	AC	27 ms; 24,264 KB
testcase_31	AC	26 ms; 23,376 KB
testcase_32	AC	27 ms; 23,976 KB
testcase_33	AC	27 ms; 23,832 KB
testcase_34	AC	27 ms; 23,532 KB
testcase_35	AC	27 ms; 24,264 KB
testcase_36	AC	27 ms; 23,640 KB
testcase_37	AC	27 ms; 23,832 KB
testcase_38	AC	27 ms; 23,820 KB
testcase_39	AC	27 ms; 24,336 KB
testcase_40	AC	27 ms; 24,012 KB
testcase_41	AC	27 ms; 24,372 KB
testcase_42	AC	27 ms; 23,400 KB
testcase_43	AC	27 ms; 23,532 KB
testcase_44	AC	27 ms; 23,412 KB
testcase_45	AC	27 ms; 24,024 KB
testcase_46	AC	27 ms; 23,844 KB
testcase_47	AC	28 ms; 24,048 KB
testcase_48	AC	27 ms; 23,640 KB
testcase_49	AC	27 ms; 24,396 KB
testcase_50	AC	27 ms; 24,396 KB
testcase_51	AC	27 ms; 23,832 KB
testcase_52	AC	26 ms; 23,640 KB
testcase_53	AC	27 ms; 23,412 KB
testcase_54	AC	28 ms; 23,640 KB
testcase_55	AC	27 ms; 24,024 KB
testcase_56	AC	27 ms; 23,640 KB
testcase_57	AC	26 ms; 24,012 KB
testcase_58	AC	27 ms; 24,492 KB
testcase_59	AC	26 ms; 24,324 KB
testcase_60	AC	26 ms; 23,544 KB
testcase_61	AC	26 ms; 24,024 KB
testcase_62	AC	27 ms; 24,372 KB
testcase_63	AC	27 ms; 23,640 KB
testcase_64	AC	28 ms; 23,412 KB
testcase_65	AC	27 ms; 24,024 KB
testcase_66	AC	27 ms; 23,832 KB
testcase_67	AC	27 ms; 23,220 KB
testcase_68	AC	26 ms; 24,012 KB
testcase_69	AC	26 ms; 23,424 KB
testcase_70	AC	27 ms; 24,036 KB
testcase_71	AC	27 ms; 23,400 KB
testcase_72	AC	26 ms; 24,348 KB
testcase_73	AC	26 ms; 24,372 KB
testcase_74	AC	27 ms; 23,544 KB
testcase_75	AC	26 ms; 24,036 KB
testcase_76	AC	27 ms; 23,532 KB
testcase_77	AC	26 ms; 23,676 KB
testcase_78	AC	26 ms; 23,832 KB
testcase_79	AC	27 ms; 23,532 KB
testcase_80	AC	27 ms; 23,532 KB
testcase_81	AC	26 ms; 24,024 KB
testcase_82	AC	26 ms; 23,424 KB
testcase_83	AC	27 ms; 24,396 KB
testcase_84	AC	26 ms; 23,424 KB
testcase_85	AC	27 ms; 24,276 KB
testcase_86	AC	27 ms; 24,036 KB
testcase_87	AC	27 ms; 23,544 KB
testcase_88	AC	27 ms; 24,336 KB
testcase_89	AC	27 ms; 23,832 KB
testcase_90	AC	27 ms; 23,628 KB
testcase_91	AC	26 ms; 23,820 KB
testcase_92	AC	26 ms; 24,048 KB
testcase_93	AC	28 ms; 23,412 KB
testcase_94	AC	27 ms; 24,024 KB
testcase_95	AC	27 ms; 23,532 KB
testcase_96	AC	27 ms; 24,060 KB
testcase_97	AC	26 ms; 24,036 KB
testcase_98	AC	27 ms; 24,360 KB
testcase_99	AC	26 ms; 23,652 KB

コンパイルメッセージ

warning: struct `IOLocal` is never constructed
   --> Main.rs:223:8
    |
223 | struct IOLocal{
    |        ^^^^^^^
    |
    = note: `#[warn(dead_code)]` on by default

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

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

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

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

warning: associated function `dump` is never used
   --> Main.rs:335:8
    |
335 |     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();
    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.4,0.7,ratio.powf(1.))*0.8;
        let B=10./3.*lerp(1.7,0.9,ratio.powf(1.))*1.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.13
        };

        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.01 || 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();
        let d:(usize,usize,i64)=(scan.read(),scan.read(),scan.read());

        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){
        let money:i64=self.scan.read();
        let mut s=[0;N];
        let mut p=[0;N];
        let mut r=[0;N];
        for i in 0..N{
            s[i]=self.scan.read();
        }
        for i in 0..N{
            p[i]=self.scan.read();
        }
        for i in 0..N{
            r[i]=self.scan.read();
        }

        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 mut D=self.history[i].iter().sum::<f64>()/self.history[i].len() as f64;
            // assert!(0.5<=D && D<=1.5);
            D=D.clamp(0.5,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);
    }

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