@e869120 さんがTwitterで投稿されている「競プロ典型90問」に参加しています。
先週末の問題023 Avoid WarでTLEから抜け出せずかなり苦労した1のですが、ACに至った最後の一手が意外だったので。
通らなかったコード
解説を読んで下記のコードまでたどりついたものの、AtCoderのジャッジに投げるとTLEが一つ出てしまいます。2
use proconio::{fastout, input, marker::*};
use std::cmp::*;
use std::collections::*;
const MOD: i64 = 1000000007;
#[fastout()]
fn main() {
input! {
H:usize,W:usize,c:[Chars;H]
}
let W2 = 1 << W;
let mut block = vec![vec![false; W]; H];
//let mut black = vec![0; H];
for h in 0..H {
for w in 0..W {
block[h][w] = c[h][w] == '.';
//black[h] *= 2;
//black[h] += if c[h][w] == '#' { 1 } else { 0 };
}
}
// 前のW+1マス分前を見て、dpする。そのままだとMLE
// 24マスのうち、可能な並びは高々121393通り。
let mut possible_base = Vec::with_capacity(130000);
for s in 0..W2 {
let mut flag = true;
for j in 0..W {
if s & (3 << j) == (3 << j) {
flag = false;
}
}
if flag {
possible_base.push(s);
}
}
// pos = possibleがi+1桁以上になるindex
let mut pos = vec![0; W + 1];
for i in 0..W {
pos[i] = match possible_base.binary_search(&(1 << i)) {
Ok(k) => k,
Err(k) => k,
};
}
pos[W] = possible_base.len();
// W+1マス分を並べると2段になる。下の段と上の段をつなげることで、ありえるパターン数を網羅する。
// wの値(何列目か)によって、可能なマスは異なる。
let mut possible = vec![Vec::with_capacity(170000); W];
let mut possible_inverse = vec![HashMap::with_capacity(170000); W];
for w in 0..W {
// i 桁以内を上位bit,W-i+1桁以内を下位bitとして、合成。
let low_num = if w == 0 { 1 } else { W - w + 1 };
let up_num = if w == 0 { W } else { w };
for j in 0..pos[up_num] {
let upper = possible_base[j] << low_num;
for k in 0..pos[low_num] {
let lower = possible_base[k];
let s = upper | lower;
if s & 1 != 0 && s & (1 << W) != 0 {
continue;
}
if W > 1 && w != 1 && s & 1 != 0 && s & (1 << (W - 1)) != 0 {
continue;
}
if w != 0 && s & 2 != 0 && s & (1 << W) != 0 {
continue;
}
possible_inverse[w].insert(s, possible[w].len());
possible[w].push(s);
}
}
}
let maxpossible = possible.iter().fold(0, |a, v| max(a, v.len()));
let mut dp = vec![vec![0; maxpossible]; W * H + 1];
dp[0][0] = 1;
// 最初の1段目
for h in 0..H {
for w in 0..W {
let mut nh = h;
let mut nw = w + 1;
if nw == W {
nh = h + 1;
nw = 0;
}
let mut id = h * W + w;
let mut nid = nh * W + nw;
for j in 0..possible[w].len() {
let s = possible[w][j];
// そのまま移動させた場合、次のマスの状態は？
let s2 = s >> 1;
let s2index = *possible_inverse[nw].get(&s2).unwrap();
dp[nid][s2index] += dp[id][j];
dp[nid][s2index] %= MOD;
let mut flag = true;
if block[h][w]
&& !(s & 1 != 0 && h >= 1 && w >= 1)
&& !(s & 2 != 0 && h >= 1)
&& !(s & 4 != 0 && h >= 1 && w < W - 1)
&& !(s & (1 << W) != 0 && w >= 1)
{
let s3 = s2 | (1 << W);
if let Some(&s3index) = possible_inverse[nw].get(&s3) {
dp[nid][s3index] += dp[id][j];
dp[nid][s3index] %= MOD;
}
}
}
}
}
let mut ans = 0;
for i in 0..possible[0].len() {
ans += dp[H * W][i];
ans %= MOD;
}
println!("{}", ans);
}
通したコード
で、本題です。
試行錯誤しているうちに、ダメ元で HashMapをBTreeMapに変えて提出したところ、ACしてしまいました。時間ギリギリ切りでしたが。
let mut possible_inverse = vec![HashMap::with_capacity(170000); W]; // before
let mut possible_inverse = vec![BTreeMap::new()); W]; // after
BTreeMapは$O(log(N))$でHashMapは$O(1)$のため、HashMapのほうが早いものと思い込んでいたのですが、定数時間であってもそれ自体結構かかるということなんでしょうね。よく考えると$log_2 170000 < 18$ ですし、基本的にBTreeMapのほうが高速なのかもしれません。
もっとずっと深くなればBTreeMapのほうが遅くなるんでしょうか？ ちょっと気になります。