はじめに
Rsutで以下のインタラクティブ問題を解いていたところ、無限に追加の入力ができなくて辛酸を嘗めたので解決策を残しておきます。
なにがあったか
以下のようなコードで下記の問題を解いていました。マクロの宣言などは省略します。
CODE THANKS FESTIVAL 2017(Parallel): E - Coin Authentication
fn main() {
input! {
N: usize;
}
let mut ans = vec![0; N];
for i in 0..((N - 1) / 5 + 1) {
print!("? ");
for j in 0..N {
print!("{} ", if j >= i*5 && j < (i+1)*5 { 10u64.pow(j as u32 % 5) } else {0});
}
println!("");
io::stdout().flush().ok();
input! {
res: usize,
}
let mut res = rse;
let num = if N % 5 != 0 && i == (N - 1) / 5 { N % 5 } else { 5 };
for j in 0..num {
let ret = res % 10;
if ret <= 2 {
ans[i*5 + j] = 10 + ret;
res -= 10 + ret;
} else {
ans[i*5 + j] = ret;
res -= ret;
}
res /= 10;
}
}
let ans: Vec<usize> = ans.into_iter().map(|a| if a % 2 == 0 { 0 } else { 1 }).collect();
print!("! ");
printvec!(ans);
io::stdout().flush().ok();
}
すると、インタラクティブにやりとりする場面でどうしても追加の入力ができず、手詰まりとなりました。結局Pythonで書いて通したのですが、なぜうまくいかなかったのか原因を調査しました。
解決策
原因は入力時にスレッドロックがかかっているらしいことです。
自分が競技プログラミングの際にしようしている入出力マクロは、以下の記事を参考に使用させて頂いています。
Rustで競技プログラミングの入力をスッキリ記述するマクロ
この中のinput!マクロ内を見てみると
macro_rules! input {
(source = $s:expr, $($r:tt)*) => {
let mut iter = $s.split_whitespace();
let mut next = || { iter.next().unwrap() };
input_inner!{next, $($r)*}
};
($($r:tt)*) => {
let stdin = std::io::stdin();
* let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
let mut next = move || -> String{
bytes
.by_ref()
.map(|r|r.unwrap() as char)
.skip_while(|c|c.is_whitespace())
.take_while(|c|!c.is_whitespace())
.collect()
};
input_inner!{next, $($r)*}
};
}
stdin.lock()という式が存在していることが確認できます。
この関数が入出力を止めてしまっているらしいことが原因でした。
よって、以下のような入出力用関数を作成して代用しました。
fn get_line() -> String {
let mut s = String::new();
std::io::stdin().read_line(&mut s).ok();
s.trim().to_string()
}
fn readln<T>() -> T
where
T: std::str::FromStr,
<T as std::str::FromStr>::Err: std::fmt::Debug {
get_line().parse().unwrap()
}
変更後
fn main() {
+ let N: usize = readln();
let mut ans = vec![0; N];
...
+ let mut res: usize = readln();
...
というわけで、原因は自分がスレッド周りのことを理解できていなかったことでした。
まとめ
インタラクティブ問題特有のミスという感じがしました...
Rustを使うならスレッドやメモリに意識をちゃんとむけつつプログラムを書いていきたいところです。