#694567 (Rust) No.453 製薬会社

• 問題: No.453 製薬会社
• ユーザー: magurofly
• 提出日時: 2021-09-01 10:28:09
• 言語: Rust (1.77.0 + proconio)
• 結果: AC
• 実行時間: 1 ms / 2,000 ms
• コード長: 4,011 bytes
• コンパイル時間: 12,140 ms
• コンパイル使用メモリ: 378,848 KB
• 実行使用メモリ: 5,248 KB
• 最終ジャッジ日時: 2024-11-27 10:13:17
• 合計ジャッジ時間: 13,099 ms
• ジャッジサーバーID （参考情報）: judge1 / judge2

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 5,248 KB
testcase_01	AC	1 ms; 5,248 KB
testcase_02	AC	1 ms; 5,248 KB
testcase_03	AC	1 ms; 5,248 KB
testcase_04	AC	1 ms; 5,248 KB
testcase_05	AC	1 ms; 5,248 KB
testcase_06	AC	0 ms; 5,248 KB
testcase_07	AC	1 ms; 5,248 KB
testcase_08	AC	1 ms; 5,248 KB
testcase_09	AC	0 ms; 5,248 KB
testcase_10	AC	1 ms; 5,248 KB
testcase_11	AC	1 ms; 5,248 KB
testcase_12	AC	1 ms; 5,248 KB

ソースコード

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