結果

問題 No.7 プライムナンバーゲーム
コンテスト
ユーザー iwot
提出日時 2019-12-21 01:34:10
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 3 ms / 5,000 ms
コード長 2,012 bytes
コンパイル時間 10,792 ms
コンパイル使用メモリ 407,524 KB
実行使用メモリ 6,824 KB
最終ジャッジ日時 2024-10-01 16:28:56
合計ジャッジ時間 11,596 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

diff # 

fn read<T: std::str::FromStr>() -> T {
  let mut s = String::new();
  std::io::stdin().read_line(&mut s).ok();
  s.trim().parse().ok().unwrap()
}

fn main() {
  let n: usize = read();
  println!("{}", no7(n));
}

fn no7(n: usize) -> String {
  fn is_prime(n: usize) -> bool {
    if n < 2 {
      return false;
    } else if n == 2 {
      return true;
    } else if n % 2 == 0 {
      return false;
    }

    let sn = (n as f64).sqrt();
    for i in (3..=sn as usize).step_by(2) {
      if n % i == 0 {
        return false;
      }
    }

    true
  }

  let primes = (0..n).filter(|a| is_prime(*a)).collect::<Vec<usize>>();

  use std::collections::HashMap;
  let mut my_memo = HashMap::new();
  let mut others_memo = HashMap::new();

  fn check(n: usize, primes: &Vec<usize>, who: &str, my_memo: &mut HashMap<usize, bool>, others_memo: &mut HashMap<usize, bool>) -> bool {
    if n == 0 || n == 1 {
      if who == "me" {
        return true;
      } else {
        return false;
      }
    }

    if who == "me" {
      if let Some(ans) = my_memo.get(&n) {
        return *ans;
      }
      for i in (0..primes.len()).rev() {
        if primes[i] > n {
          continue;
        }
        let new_n = n - primes[i];
        if check(new_n, primes, "not me", my_memo, others_memo) {
          my_memo.entry(n).or_insert(true);
          return true;
        }
      }
      my_memo.entry(n).or_insert(false);
      return false;
    } else {
      if let Some(ans) = others_memo.get(&n) {
        return *ans;
      }
      for i in (0..primes.len()).rev() {
        if primes[i] > n {
          continue;
        }
        let new_n = n - primes[i];
        if !check(new_n, primes, "me", my_memo, others_memo) {
          others_memo.entry(n).or_insert(false);
          return false;
        }
      }
      others_memo.entry(n).or_insert(true);
      return true;
    }
  }

  if check(n, &primes, "me", &mut my_memo, &mut others_memo) {
    "Win".to_string()
  } else {
    "Lose".to_string()
  }
}
0