結果

問題 No.453 製薬会社
ユーザー maguroflymagurofly
提出日時 2021-09-01 10:28:09
言語 Rust
(1.77.0)
結果
AC  
実行時間 1 ms / 2,000 ms
コード長 4,011 bytes
コンパイル時間 1,617 ms
コンパイル使用メモリ 153,848 KB
実行使用メモリ 4,384 KB
最終ジャッジ日時 2023-08-18 06:41:39
合計ジャッジ時間 2,403 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,376 KB
testcase_01 AC 1 ms
4,380 KB
testcase_02 AC 1 ms
4,376 KB
testcase_03 AC 1 ms
4,380 KB
testcase_04 AC 1 ms
4,376 KB
testcase_05 AC 1 ms
4,384 KB
testcase_06 AC 1 ms
4,380 KB
testcase_07 AC 1 ms
4,380 KB
testcase_08 AC 0 ms
4,380 KB
testcase_09 AC 1 ms
4,376 KB
testcase_10 AC 1 ms
4,380 KB
testcase_11 AC 1 ms
4,376 KB
testcase_12 AC 1 ms
4,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#![allow(non_snake_case)]

fn main() {
  let input = getline().trim().split_whitespace().map(|s| s.parse::<f64>().unwrap()).collect::<Vec<_>>();
  let (C, D) = (input[0], input[1]);

  let c = vec![1000.0, 2000.0];
  let mat = vec![
    vec![3.0 / 4.0, 2.0 / 7.0, C],
    vec![1.0 / 4.0, 5.0 / 7.0, D],
    vec![-1.0, 0.0, 0.0],
    vec![0.0, -1.0, 0.0],
  ];
  let bounds = vec![
    (0.0, 2000.0),
    (0.0, 2000.0),
  ];

  let x = seidel_lp(&mut Rng(1), 2, &c, &mat, &bounds).expect("No solution found");

  println!("{}", x[0] * 1000.0 + x[1] * 2000.0);
}

fn getline() -> String {
	let mut __ret=String::new();
	std::io::stdin().read_line(&mut __ret).ok();
	return __ret;
}


type T = f64;

struct Rng(u64);
impl Rng {
  pub fn next_u32(&mut self) -> u32 {
    self.0 = 48271 * self.0 % 2147483647;
    self.0 as u32
  }
}

/// Seidel's LP Algorithm
/// https://niuez.github.io/cp-cpp-library/math/seidels_lp.html
/// find x = {x[0], x[1], ..., x[d - 1]}
/// maximizes (0 .. d).map(|i| c[i] * x[i]).sum()
fn seidel_lp(rnd: &mut Rng, d: usize, c: &[T], mat: &[Vec<T>], bounds: &[(T, T)]) -> Option<Vec<T>> {
  // eprintln!("seidel_lp(rnd, d = {}, c = {:?}, mat = {:?}, bounds = {:?})", d, c, mat, bounds);
  assert_eq!(c.len(), d, "c.len() != d");
  let m = mat.len();
  for i in 0 .. m {
    assert_eq!(mat[i].len(), d + 1, "mat[{}].len() != d + 1 ({}); mat = {:?}", i, d + 1, &mat);
  }
  fn eps_eq(x: T, y: T) -> bool {
    (x - y).abs() <= 1e-9
  }

  if d == 1 {
    let (mut low, mut high) = bounds[0];
    let mut z = 0.0;
    for a in mat.iter() {
      if eps_eq(a[0], 0.0) {
        if eps_eq(a[1], z) || a[1] < z {
          z = a[1];
        }
      } else if a[0] > 0.0 {
        // greater
        // high = high.min(a[1] / a[0]);
        // 意味なし？
        let pa = a[1] / a[0];
        if eps_eq(pa, high) || pa < high {
          high = pa;
        }
      } else {
        // less
        // low = low.max(a[1] / a[0]);
        let pa = a[1] / a[0];
        if eps_eq(pa, low) || pa > low {
          low = pa;
        }
      }
    }
    if z.is_sign_negative() || high < low {
      None
    } else if eps_eq(c[0], 0.0) || c[0] > 0.0 {
      Some(vec![high])
    } else {
      Some(vec![low])
    }
  } else if m == 0 {
    // no constraints
    Some((0 .. d).map(|i| {
      if eps_eq(c[i], 0.0) || c[i] > 0.0 {
        bounds[i].1
      } else {
        bounds[i].0
      }
    }).collect())
  } else {
    let rmi = rnd.next_u32() as usize % m;
    let a = &mat[rmi];
    let mut next_mat = Vec::with_capacity(m - 1);
    for i in 0 .. m {
      if i != rmi {
        next_mat.push(mat[i].clone());
      }
    }
    // eprintln!("call from {}", line!() + 1);
    let mut v = seidel_lp(rnd, d, c, &next_mat, bounds)?;
    {
      let value = a.iter().zip(&v).fold(0.0, |sum, (&x, &y)| sum + x * y);
      if value <= a[d] {
        return Some(v);
      }
    }
    let k = (0 .. d).rev().find(|&i| !eps_eq(a[i], 0.0))?;

    let mut next_bounds = vec![];
    for i in 0 .. d {
      if i != k {
        next_bounds.push(bounds[i]);
      }
    }
    let mut bar_mat = vec![Vec::with_capacity(d); m + 1];
    for mi in 0 .. m - 1 {
      let ratio = next_mat[mi][k] / a[k];
      for i in 0 ..= d {
        if i != k {
          bar_mat[mi].push(next_mat[mi][i] - ratio * a[i]);
        }
      }
    }
    let mut bar_c = Vec::with_capacity(d - 1);
    {
      let ratio = c[k] / a[k];
      for i in 0 .. d {
        if i != k {
          bar_c.push(c[i] - ratio * a[i]);
        }
      }
    }
    for i in 0 .. d {
      if i != k {
        let x = -(a[k].recip() * a[i]);
        bar_mat[m - 1].push(x);
        bar_mat[m].push(x);
      }
    }
    bar_mat[m - 1].push(bounds[k].1);
    bar_mat[m].push(bounds[k].0);

    // eprintln!("call from {}", line!() + 1);
    v = seidel_lp(rnd, d - 1, &bar_c, &bar_mat, &next_bounds)?;
    v.insert(k, 0.0);
    let s = a.iter().zip(&v).fold(0.0, |sum, (&x, &y)| sum + x * y);
    v[k] = (a[d] - s) / a[k];
    Some(v)
  }
}
0