Chokudai Contest 003

Submission #1123697

Source codeソースコード

use std::io::{self, Stdin};
use std::str::{self, FromStr};
use std::error::Error;
use std::thread;
use std::collections::{BinaryHeap, HashSet};
use std::ops::{Add, Sub, Index, IndexMut};
use std::cmp::*;
// 座標
#[derive(Copy, Clone, Eq, Debug)]
struct Coord {
    x: i32,
    y: i32,
}
impl Coord {
    fn new(x_: i32, y_: i32) -> Coord {
        Coord { x: x_, y: y_ }
    }
}
impl Add for Coord {
    type Output = Coord; // Coord * Coord -> Coord
    fn add(self, other: Coord) -> Coord {
        Coord::new(self.x + other.x, self.y + other.y)
    }
}
impl Sub for Coord {
    type Output = Coord;
    fn sub(self, other: Coord) -> Coord {
        Coord::new(self.x - other.x, self.y - other.y)
    }
}
impl Ord for Coord {
    fn cmp(&self, other: &Coord) -> Ordering {
        let xcmp = self.x.cmp(&other.x);
        match xcmp {
            Ordering::Equal => self.y.cmp(&other.y),
            _ => xcmp,
        }
    }
}
impl PartialEq for Coord {
    fn eq(&self, other: &Coord) -> bool {
        self.x == other.x && self.y == other.y
    }
}
//全順序なのでこれでだいじょうぶ
impl PartialOrd for Coord {
    fn partial_cmp(&self, other: &Coord) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

const ROWS: usize = 51;
const COLS: usize = 51;
const ROWS_I: i32 = ROWS as i32;
const COLS_I: i32 = COLS as i32;
// ゲームマップ用の汎用型
#[derive(Clone, Debug, Eq, PartialEq, Hash)]
struct Field<T> {
    data: Vec<Vec<T>>,
}
impl<T: Copy> Field<T> {
    fn new(init_num: T) -> Field<T> {
        let res = vec![vec![init_num; COLS + 2]; ROWS + 2];
        Field { data: res }
    }
}

impl<T> Index<Coord> for Field<T> {
    type Output = T;
    fn index(&self, id: Coord) -> &T {
        let col = id.x;
        let row = id.y;
        assert!(col >= 0 && row >= 0 && col <= COLS_I && row <= ROWS_I,
                "Index Error {:?}",
                id);
        &self.data[row as usize][col as usize]
    }
}

impl<T> Index<(i32, i32)> for Field<T> {
    type Output = T;
    fn index(&self, id: (i32, i32)) -> &T {
        let (col, row) = id;
        assert!(col >= 0 && row >= 0 && col <= COLS_I && row <= ROWS_I,
                "Index Error {:?}",
                id);
        &self.data[row as usize][col as usize]
    }
}

impl<T> IndexMut<Coord> for Field<T> {
    fn index_mut(&mut self, id: Coord) -> &mut T {
        let col = id.x;
        let row = id.y;
        assert!(col >= 0 && row >= 0 && col <= COLS_I && row <= ROWS_I,
                "Index Error {:?}",
                id);
        &mut self.data[row as usize][col as usize]
    }
}

impl<T> IndexMut<(i32, i32)> for Field<T> {
    fn index_mut<'a>(&'a mut self, id: (i32, i32)) -> &mut T {
        let (col, row) = id;
        assert!(col >= 0 && row >= 0 && col <= COLS_I && row <= ROWS_I,
                "Index Error {:?}",
                id);
        &mut self.data[row as usize][col as usize]
    }
}
fn print(f: &Field<u8>, n: i32) {
    for i in 0..n {
        for j in 0..n {
            print!("{}", f[(j + 1, i + 1)] as char);
        }
        println!("");
    }
}
const MOVES: [Coord; 4] =
    [Coord { x: 0, y: -1 }, Coord { x: -1, y: 0 }, Coord { x: 1, y: 0 }, Coord { x: 0, y: 1 }];
fn trim(field: &Field<u8>, n: i32) -> Field<u8> {
    let mut s = Field::new(b' ');
    for j in 1..n + 1 {
        let mut cur_y = n;
        for i in (1..n + 1).rev() {
            match field[(j, i)] {
                b'o' | b'x' => {
                    s[(j, cur_y)] = field[(j, i)];
                    cur_y -= 1;
                }
                b'-' => cur_y = i - 1,
                b'+' => cur_y -= 1,
                _ => {}
            }
        }
    }
    s
}
// scoring: O(N ^ 2)
fn score(field: &Field<u8>, n: i32) -> i32 {
    let s = trim(field, n);
    fn dfs(f: &Field<u8>, mut used: &mut Field<bool>, cur: Coord) -> i32 {
        used[cur] = true;
        let mut res = 1;
        for &m in &MOVES {
            let nxt = cur + m;
            if f[nxt] == f[cur] && used[nxt] == false {
                res += dfs(&f, &mut used, nxt);
            }
        }
        res
    }
    let mut used = Field::new(false);
    let (mut reso, mut resx) = (0, 0);
    for i in 1..n + 1 {
        for j in 1..n + 1 {
            if used[(j, i)] == true {
                continue;
            }
            if s[(j, i)] == b'o' {
                reso = max(reso, dfs(&s, &mut used, Coord::new(j, i)));
            }
            if s[(j, i)] == b'x' {
                resx = max(resx, dfs(&s, &mut used, Coord::new(j, i)));
            }
        }
    }
    reso + resx
}
#[derive(Clone)]
struct Search {
    field: Field<u8>,
    score: i32,
}
impl Ord for Search {
    fn cmp(&self, other: &Search) -> Ordering {
        self.score.cmp(&other.score)
    }
}
impl Eq for Search {}
impl PartialEq for Search {
    fn eq(&self, other: &Search) -> bool {
        self.score == other.score
    }
}
impl PartialOrd for Search {
    fn partial_cmp(&self, other: &Search) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}
fn cross(xl: i32, xu: i32, yl: i32, yu: i32) -> bool {
    if yl < xu || xl < yu {
        return false;
    }
    true
}
fn search(init: &Field<u8>, n: i32) {
    let mut best = Search {
        field: init.clone(),
        score: score(&init, n),
    };
    let mut heap = BinaryHeap::new();
    heap.push(best.clone());
    let mut mp = HashSet::new();
    mp.insert(init.clone());
    const W: usize = 80;
    for j_ in 1..n {
        let mut cnt = 0;
        let mut nheap = BinaryHeap::new();
        while let Some(s) = heap.pop() {
            cnt += 1;
            if cnt == W {
                break;
            }
            let fld = s.field;
            let mut gs = Vec::new();
            for k in 0..2 {
                let mut stack: Vec<(u8, i32, i32)> = Vec::new();
                let j = j_ + k;
                let mut group = Vec::new();
                let mut cur_y = n;
                for i in (1..n + 1).rev() {
                    match fld[(j, i)] {
                        b'o' | b'x' => {
                            let do_pop = match stack.last() {
                                Some(p) => p.0 != fld[(j, i)],
                                None => false,
                            };
                            if do_pop {
                                let size = stack.len() as i32;
                                let start = stack[0].2;
                                let pos = stack[0].1;
                                group.push((stack[0].0, pos, start, size));
                                stack.clear();
                            }
                            stack.push((fld[(j, i)], i, cur_y));
                            cur_y -= 1;
                        }
                        b'-' | b'+' => {
                            if stack.is_empty() == false {
                                let size = stack.len() as i32;
                                let start = stack[0].2;
                                let pos = stack[0].1;
                                group.push((stack[0].0, pos, start, size));
                                stack.clear();
                            }
                            if fld[(j, i)] == b'-' {
                                cur_y = i - 1;
                            } else {
                                cur_y -= 1;
                            }
                        }
                        _ => {}

                    }
                }
                if stack.is_empty() == false {
                    let size = stack.len() as i32;
                    let start = stack[0].2;
                    let pos = stack[0].1;
                    group.push((stack[0].0, pos, start, size));
                    stack.clear();
                }
                gs.push(group);
            }
            for &(t1, pos1, low1, len1) in &gs[0] {
                for &(t2, pos2, low2, len2) in &gs[1] {
                    if t1 != t2 {
                        continue;
                    }
                    if low1 < low2 {
                        if pos2 + len2 - 1 > low1 {
                            continue;
                        }
                        let need = (low2 - len2 + 1) - low1;
                        let mut nfld = fld.clone();
                        let mut t = 0;
                        for i in (pos2..n + 1).rev() {
                            if t == need {
                                break;
                            }
                            if nfld[(j_ + 1, i)] == b'.' {
                                t += 1;
                                nfld[(j_ + 1, i)] = b'+';
                            }
                        }
                        if t < need {
                            let low1_top = low1 - len1 + 1;
                            let mut ok = false;
                            for i in pos2..n {
                                if nfld[(j_ + 1, i)] == b'.' || nfld[(j_ + 1, i)] == b'+' {
                                    if cross(low1_top, low1, i - len2, i - 1) {
                                        nfld[(j_ + 1, i)] = b'-';
                                        ok = true;
                                        break;
                                    }
                                }
                            }
                            if ok == false {
                                continue;
                            }
                        }
                        if mp.contains(&nfld) == false {
                            let scr = score(&nfld, n);
                            mp.insert(nfld.clone());
                            let ser = Search {
                                field: nfld,
                                score: scr,
                            };
                            if best.score < scr {
                                best = ser.clone();
                            }
                            nheap.push(ser);
                        }
                    } else if low1 > low2 {
                        if pos1 + len1 - 1 > low2 {
                            continue;
                        }
                        let need = (low1 - len1 + 1) - low2;
                        let mut nfld = fld.clone();
                        let mut t = 0;
                        for i in (pos1..n + 1).rev() {
                            if t == need {
                                break;
                            }
                            if nfld[(j_, i)] == b'.' {
                                t += 1;
                                nfld[(j_, i)] = b'+';
                            }
                        }
                        if t < need {
                            let low2_top = low2 - len2 + 1;
                            let mut ok = false;
                            for i in pos1..n {
                                if nfld[(j_, i)] == b'.' || nfld[(j_, i)] == b'+' {
                                    if cross(low2_top, low2, i - len1, i - 1) {
                                        nfld[(j_, i)] = b'-';
                                        ok = true;
                                        break;
                                    }
                                }
                            }
                            if ok == false {
                                continue;
                            }
                        }
                        if mp.contains(&nfld) == false {
                            let scr = score(&nfld, n);
                            mp.insert(nfld.clone());
                            let ser = Search {
                                field: nfld,
                                score: scr,
                            };
                            if best.score < scr {
                                best = ser.clone();
                            }
                            nheap.push(ser);
                        }
                    }
                }
            }
        }
        heap = nheap;
    }
    print(&best.field, n);
}
fn exec() {
    let mut sc = Scanner::new();
    let (field, n) = {
        let mut res = Vec::new();
        while let Some(s) = sc.next::<String>() {
            res.push(s.into_bytes());
        }
        let mut f = Field::new(b' ');
        let n = res.len() as i32;
        for i in 0..n {
            for j in 0..n {
                if res[i as usize][j as usize] == b'.' {
                    f[(j + 1, i + 1)] = b'.';
                } else {
                    f[(j + 1, i + 1)] = res[i as usize][j as usize];
                }
            }
        }
        (f, n)
    };
    search(&field, n);
}
fn main() {
    const DEFAULT_STACK: usize = 16 * 1024 * 1024;
    let builder = thread::Builder::new();
    let th = builder.stack_size(DEFAULT_STACK);
    let handle = th.spawn(|| { exec(); }).unwrap();
    let _ = handle.join();
}

#[allow(dead_code)]
struct Scanner {
    stdin: Stdin,
    id: usize,
    buf: Vec<u8>,
}

#[allow(dead_code)]
impl Scanner {
    fn new() -> Scanner {
        Scanner {
            stdin: io::stdin(),
            id: 0,
            buf: Vec::new(),
        }
    }
    fn next_line(&mut self) -> Option<String> {
        let mut res = String::new();
        match self.stdin.read_line(&mut res) {
            Ok(0) => return None,
            Ok(_) => Some(res),
            Err(why) => panic!("error in read_line: {}", why.description()),
        }
    }
    fn next<T: FromStr>(&mut self) -> Option<T> {
        while self.buf.len() == 0 {
            self.buf = match self.next_line() {
                Some(r) => {
                    self.id = 0;
                    r.trim().as_bytes().to_owned()
                }
                None => return None,
            };
        }
        let l = self.id;
        assert!(self.buf[l] != b' ');
        let n = self.buf.len();
        let mut r = l;
        while r < n && self.buf[r] != b' ' {
            r += 1;
        }
        let res = match str::from_utf8(&self.buf[l..r]).ok().unwrap().parse::<T>() {
            Ok(s) => Some(s),
            Err(_) => {
                panic!("parse error, {:?}",
                       String::from_utf8(self.buf[l..r].to_owned()))
            }
        };
        while r < n && self.buf[r] == b' ' {
            r += 1;
        }
        if r == n {
            self.buf.clear();
        } else {
            self.id = r;
        }
        res
    }
    fn ne<T: FromStr>(&mut self) -> T {
        self.next::<T>().unwrap()
    }
}

Submission

Task問題 A - ○×ブロック
User nameユーザ名 mioh
Created time投稿日時
Language言語 Rust (1.15.1)
Status状態 AC
Score得点 5285
Source lengthソースコード長 15097 Byte
File nameファイル名
Exec time実行時間 6015 ms
Memory usageメモリ使用量 215420 KB

Test case

Set

Set name Score得点 / Max score Cases
test_01 524 / 2500 subtask_01_01.txt
test_02 535 / 2500 subtask_01_02.txt
test_03 461 / 2500 subtask_01_03.txt
test_04 525 / 2500 subtask_01_04.txt
test_05 561 / 2500 subtask_01_05.txt
test_06 558 / 2500 subtask_01_06.txt
test_07 563 / 2500 subtask_01_07.txt
test_08 486 / 2500 subtask_01_08.txt
test_09 533 / 2500 subtask_01_09.txt
test_10 539 / 2500 subtask_01_10.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
subtask_01_01.txt AC 5866 ms 211324 KB
subtask_01_02.txt AC 5718 ms 199036 KB
subtask_01_03.txt AC 5631 ms 199036 KB
subtask_01_04.txt AC 5860 ms 211324 KB
subtask_01_05.txt AC 5771 ms 205180 KB
subtask_01_06.txt AC 5823 ms 203132 KB
subtask_01_07.txt AC 6015 ms 215420 KB
subtask_01_08.txt AC 5491 ms 199036 KB
subtask_01_09.txt AC 5668 ms 203132 KB
subtask_01_10.txt AC 5813 ms 203132 KB