AtCoder Beginner Contest 380 F

https://atcoder.jp/contests/abc380/tasks/abc380_f

カードは、プレーヤー1、2が持っているのと場にあるかなので、3つの状態があります。これは2ビットで表せます。あと、どちらの手番かを1ビットで表せばよいです。次の状態への遷移はビット操作で計算できます。

// Exchange Game
#![allow(non_snake_case)]

use std::collections::HashMap;


//////////////////// library ////////////////////

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

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>().split_whitespace()
            .map(|e| e.parse().ok().unwrap()).collect()
}


//////////////////// process ////////////////////

fn read_input() -> (Vec<i32>, Vec<i32>, Vec<i32>) {
    let _v: Vec<usize> = read_vec();
    let A: Vec<i32> = read_vec();
    let B: Vec<i32> = read_vec();
    let C: Vec<i32> = read_vec();
    (A, B, C)
}

fn encode(v: &Vec<(i32, usize)>) -> usize {
    let mut code: usize = 0;
    for (i, &(_, place)) in v.iter().enumerate() {
        code += place << (i*2+1)
    }
    code
}

fn collect(A: &Vec<i32>, B: &Vec<i32>, C: &Vec<i32>) -> (usize, Vec<i32>) {
    let mut v: Vec<(i32, usize)> = vec![];
    for &a in A.iter() {
        v.push((a, 1))
    }
    for &b in B.iter() {
        v.push((b, 2))
    }
    for &c in C.iter() {
        v.push((c, 0))
    }
    v.sort();
    let code = encode(&v);
    let w: Vec<i32> = v.into_iter().map(|(e, _)| e).collect();
    (code, w)
}

fn nexts(c0: usize, v: &Vec<i32>) -> Vec<usize> {
    let turn = (c0 & 1) + 1;
    // 手番の人の手の札
    let hands: Vec<usize> = (0..v.len()).
                        filter(|&i| ((c0 >> (i*2+1)) & 3) == turn).collect();
    let board: Vec<usize> = (0..v.len()).
                        filter(|&i| ((c0 >> (i*2+1)) & 3) == 0).collect();
    
    let mut codes: Vec<usize> = vec![];
    for i in hands.into_iter() {
        let size = codes.len();
        let c1 = c0 ^ (turn << (i*2+1)) ^ 1;
        for &j in board.iter() {
            if v[i] <= v[j] {
                break
            }
            let c2 = c1 | (turn << (j*2+1));
            codes.push(c2)
        }
        if codes.len() == size {
            codes.push(c1)
        }
    }
    codes
}

fn wins(c0: usize, v: &Vec<i32>, memo: &mut HashMap<usize, bool>) -> bool {
    match memo.get(&c0) {
        Some(&b) => b,
        None     => {
            let b = nexts(c0, &v).into_iter().any(|c| !wins(c, v, memo));
            memo.insert(c0, b);
            b
        }
    }
}

fn F(A: Vec<i32>, B: Vec<i32>, C: Vec<i32>) -> String {
    let mut memo: HashMap<usize, bool> = HashMap::new();
    let (c0, v) = collect(&A, &B, &C);
    (if wins(c0, &v, &mut memo) { "Takahashi" } else { "Aoki" }).to_string()
}

fn main() {
    let (A, B, C) = read_input();
    println!("{}", F(A, B, C))
}