結果

問題 No.5018 Let's Make a Best-seller Book
ユーザー rhoorhoo
提出日時 2023-10-01 16:30:11
言語 Rust
(1.77.0 + proconio)
結果
AC  
実行時間 54 ms / 400 ms
コード長 12,076 bytes
コンパイル時間 1,136 ms
コンパイル使用メモリ 167,188 KB
実行使用メモリ 24,396 KB
スコア 48,637
平均クエリ数 52.00
最終ジャッジ日時 2023-10-01 16:30:22
合計ジャッジ時間 10,546 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge11
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 41 ms
23,364 KB
testcase_01 AC 34 ms
23,652 KB
testcase_02 AC 32 ms
23,412 KB
testcase_03 AC 30 ms
24,036 KB
testcase_04 AC 33 ms
23,676 KB
testcase_05 AC 32 ms
23,376 KB
testcase_06 AC 34 ms
23,412 KB
testcase_07 AC 36 ms
23,376 KB
testcase_08 AC 34 ms
23,652 KB
testcase_09 AC 32 ms
23,832 KB
testcase_10 AC 40 ms
23,376 KB
testcase_11 AC 31 ms
23,532 KB
testcase_12 AC 33 ms
24,036 KB
testcase_13 AC 34 ms
23,652 KB
testcase_14 AC 35 ms
24,264 KB
testcase_15 AC 36 ms
23,640 KB
testcase_16 AC 31 ms
23,364 KB
testcase_17 AC 34 ms
24,360 KB
testcase_18 AC 37 ms
23,820 KB
testcase_19 AC 32 ms
23,820 KB
testcase_20 AC 31 ms
23,832 KB
testcase_21 AC 35 ms
23,424 KB
testcase_22 AC 31 ms
23,652 KB
testcase_23 AC 35 ms
24,060 KB
testcase_24 AC 38 ms
23,676 KB
testcase_25 AC 32 ms
23,412 KB
testcase_26 AC 33 ms
23,376 KB
testcase_27 AC 31 ms
23,640 KB
testcase_28 AC 33 ms
23,652 KB
testcase_29 AC 36 ms
23,820 KB
testcase_30 AC 34 ms
23,532 KB
testcase_31 AC 36 ms
24,048 KB
testcase_32 AC 33 ms
24,036 KB
testcase_33 AC 37 ms
23,532 KB
testcase_34 AC 34 ms
23,376 KB
testcase_35 AC 34 ms
24,024 KB
testcase_36 AC 37 ms
24,348 KB
testcase_37 AC 33 ms
23,520 KB
testcase_38 AC 35 ms
23,376 KB
testcase_39 AC 37 ms
24,036 KB
testcase_40 AC 32 ms
23,532 KB
testcase_41 AC 35 ms
23,376 KB
testcase_42 AC 54 ms
23,664 KB
testcase_43 AC 36 ms
23,400 KB
testcase_44 AC 34 ms
24,348 KB
testcase_45 AC 37 ms
23,652 KB
testcase_46 AC 33 ms
23,664 KB
testcase_47 AC 31 ms
23,532 KB
testcase_48 AC 32 ms
24,024 KB
testcase_49 AC 32 ms
24,036 KB
testcase_50 AC 38 ms
23,412 KB
testcase_51 AC 32 ms
23,400 KB
testcase_52 AC 31 ms
23,364 KB
testcase_53 AC 36 ms
24,048 KB
testcase_54 AC 32 ms
24,348 KB
testcase_55 AC 36 ms
23,376 KB
testcase_56 AC 36 ms
23,376 KB
testcase_57 AC 32 ms
23,832 KB
testcase_58 AC 32 ms
23,544 KB
testcase_59 AC 31 ms
23,844 KB
testcase_60 AC 37 ms
23,376 KB
testcase_61 AC 33 ms
24,396 KB
testcase_62 AC 35 ms
23,640 KB
testcase_63 AC 33 ms
23,532 KB
testcase_64 AC 34 ms
24,348 KB
testcase_65 AC 34 ms
23,532 KB
testcase_66 AC 30 ms
23,844 KB
testcase_67 AC 38 ms
23,364 KB
testcase_68 AC 36 ms
23,412 KB
testcase_69 AC 35 ms
24,024 KB
testcase_70 AC 36 ms
24,264 KB
testcase_71 AC 36 ms
23,676 KB
testcase_72 AC 31 ms
23,412 KB
testcase_73 AC 31 ms
23,640 KB
testcase_74 AC 32 ms
24,312 KB
testcase_75 AC 31 ms
24,360 KB
testcase_76 AC 33 ms
24,012 KB
testcase_77 AC 34 ms
23,544 KB
testcase_78 AC 32 ms
24,036 KB
testcase_79 AC 34 ms
24,384 KB
testcase_80 AC 32 ms
24,036 KB
testcase_81 AC 32 ms
24,036 KB
testcase_82 AC 34 ms
23,832 KB
testcase_83 AC 33 ms
23,376 KB
testcase_84 AC 32 ms
24,396 KB
testcase_85 AC 32 ms
23,424 KB
testcase_86 AC 34 ms
23,544 KB
testcase_87 AC 34 ms
23,388 KB
testcase_88 AC 34 ms
24,264 KB
testcase_89 AC 32 ms
24,336 KB
testcase_90 AC 38 ms
24,036 KB
testcase_91 AC 37 ms
23,832 KB
testcase_92 AC 36 ms
24,024 KB
testcase_93 AC 34 ms
23,412 KB
testcase_94 AC 31 ms
23,376 KB
testcase_95 AC 37 ms
23,376 KB
testcase_96 AC 33 ms
23,388 KB
testcase_97 AC 33 ms
24,348 KB
testcase_98 AC 34 ms
23,820 KB
testcase_99 AC 36 ms
23,628 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
warning: struct `IOLocal` is never constructed
   --> Main.rs:226:8
    |
226 | struct IOLocal{
    |        ^^^^^^^
    |
    = note: `#[warn(dead_code)]` on by default

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

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

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

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

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

warning: 6 warnings emitted

ソースコード

diff # 

#![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);
            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;
        }

        assert!(self.money==money);

        self.turn+=1;
        if self.turn==TURN{
            eprintln!("score = {}",self.score);
            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()
    }
}
0