結果
問題 | No.1208 anti primenumber game |
ユーザー |
|
提出日時 | 2020-08-30 17:37:02 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 54 ms / 2,000 ms |
コード長 | 2,992 bytes |
コンパイル時間 | 14,185 ms |
コンパイル使用メモリ | 400,864 KB |
実行使用メモリ | 35,896 KB |
最終ジャッジ日時 | 2024-11-15 14:06:13 |
合計ジャッジ時間 | 17,708 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 44 |
ソースコード
use std::io::*;fn dfs(i: usize,m: i64,turn: usize,a: &mut [i64],memo: &mut Vec<Vec<(i64, i64)>>,) -> (i64, i64) {if i == a.len() {return (0, 0);}if memo[i][turn] != (-1, -1) {return memo[i][turn];}if a[i] == 1 {if turn == 0 {let mut res = dfs(i + 1, m, 1, a, memo);res.0 += 1 - m;memo[i][turn] = res;return res;} else {let mut res = dfs(i + 1, m, 0, a, memo);res.1 += 1 - m;memo[i][turn] = res;return res;}} else if a[i] == 2 || a[i] == 3 {if turn == 0 {// 次のターンにするlet mut res1 = dfs(i + 1, m, 1, a, memo);res1.0 += a[i] - m;let mut res2 = dfs(i + 1, m, 0, a, memo);res2.0 += a[i] - 1;res2.1 += 1 - m;if res1.0 > res2.0 {memo[i][turn] = res1;return res1;}memo[i][turn] = res2;return res2;} else {let mut res1 = dfs(i + 1, m, 0, a, memo);res1.1 += a[i] - m;let mut res2 = dfs(i + 1, m, 1, a, memo);res2.1 += a[i] - 1;res2.0 += 1 - m;if res1.1 > res2.1 {memo[i][turn] = res1;return res1;}memo[i][turn] = res2;return res2;}} else {if turn == 0 {let mut res1 = dfs(i + 1, m, 0, a, memo);res1.0 += a[i] - 1;res1.1 += 1 - m;let mut res2 = dfs(i + 1, m, 1, a, memo);res2.0 += a[i] - m;if res1.0 > res2.0 {memo[i][turn] = res1;return res1;}memo[i][turn] = res2;return res2;} else {let mut res1 = dfs(i + 1, m, 1, a, memo);res1.0 += 1 - m;res1.1 += a[i] - 1;let mut res2 = dfs(i + 1, m, 0, a, memo);res2.1 += a[i] - m;if res1.1 > res2.1 {memo[i][turn] = res1;return res1;}memo[i][turn] = res2;return res2;}}}fn main() {let mut s: String = String::new();std::io::stdin().read_to_string(&mut s).ok();let mut itr = s.trim().split_whitespace();let n: usize = itr.next().unwrap().parse().unwrap();let m: i64 = itr.next().unwrap().parse().unwrap();let mut a: Vec<i64> = (0..n).map(|_| itr.next().unwrap().parse().unwrap()).collect();let mut memo: Vec<Vec<(i64, i64)>> = vec![vec![(-1, -1); 2]; n];// 1だったら強制分岐、2か3だったら選べる、それ以外は分岐しないlet score = dfs(0, m, 0, &mut a, &mut memo);if score.0 > score.1 {println!("First");} else {println!("Second");}}