Rust LT #4 で LT をした
これに参加して5分枠で発表した。
テーマ決め
AtCoder Problems というサービスのバックエンドを Rust で書いていたので、それについて発表しようと思った。
技術的にはそこまで難しくなく、やっていることはドキュメントを読めば誰でもできるレベルなので話をするかは迷ったが、 Rust コミュニティの性質上、低レイヤーや言語仕様に関する発表が多いことが予想され、ライトな発表があってもよいだろうと考えた。サービス上にはクローラー、サーバーレス REST API、 DB 更新バッチの大きく分けて 3 つのアプリケーションが存在したが、サーバーレス API が身近で面白いだろうと考え、これについて話すことにした。
準備
いざスライドを作り始めてみると、想像以上に書くことがなく、AWS 公式ブログの内容を日本語訳しただけのスライドになってしまった。
このブログにあるとおりに Lambda を組み、API Gateway でつなぎこんでやれば、本当に 5 分程度で Rust 製のサーバーレス API ができてしまう。つまりスライドを使って説明している間にデプロイで来てしまうのだ。というわけで、スライドを使った発表はやめ、実際に Rust + Lambda + API Gateway で作ってその場でデプロイすることにした。
実際に練習としてやってみると、crate のダウンロードやコンパイルに時間がかかって 5 分をオーバーしてしまったり、simple_logger や serde などを使っているおかげで見た目の複雑さが増していたりなど、発表する上での問題点を見つけた。これらについて、必要な crate はあらかじめコンパイルしておいたり、不要なコードは削除したりして対処した。
発表
実際に発表で書いた（コピペして削った）コードがこちら。
#[macro_use] extern crate lambda_runtime as lambda; use lambda::error::HandlerError; use serde_json::{json, Value}; use std::error::Error; fn main() -> Result<(), Box<dyn Error>> { lambda!(my_handler); Ok(()) } fn my_handler(e: Value, c: lambda::Context) -> Result<Value, HandlerError> { let name = e .get("pathParameters") .unwrap() .get("name") .unwrap() .as_str() .unwrap(); Ok(json!({ "isBase64Encoded": false, "statusCode": 200, "body": format!("Hello {}!\n",name) })) }
isBase64EncodedをisBase64と書いてしまったおかげで Internal Server Error が発生してしまったときはもうダメかと思ったが、すぐに発見できたおかげで何とか完成にたどり着けた。ただ、入力部を実装する前に、バグからのデバッグ成功で会場が盛り上がってしまったので、入力部も含めて真に REST API にしていく部分が若干おまけっぽくなってしまった。次に発表するときは最初にゴールを明確にしておきたい。
AtCoderJobs で転職した
この記事を読んで思い出しましたが、僕も2ヶ月ほど前に AtCoderJobs を利用して転職したので、その時のことを書きます。この転職に満足しているので、他の人が AtCoderJobs を使う際の参考になれば幸いです。
AtCoderJobs を使う前
前に働いていた会社 SoundHound Inc. は AI スピーカーを作っている会社で、G●●gle や Amaz●n と正面から競合していたので、「俺はレッドオーシャンで血で血を洗うような戦いがしてぇ！」と思って入社しました。しかし、意外にも事業は順調（これとかこれとかこれ）で、血で血を洗う感じではありませんでした。当初の予定通り戦いを求めて転職を考えましたが、周りに僕よりはるかに優秀な競技プログラマが何人もいて刺激がありましたし、給料が1300万円（ベース1100+ボーナス200）だったり、ストックオプションが束でついていたり、自分にとっては二度と出会えないのではないかと思えるほど待遇も良かったので、かなり迷いました。最終的には、20代で守りに入るようではニートだった頃の自分に顔向けできないと考えて、転職することにしました。
転職活動を始めたばかりの頃は AtCoderJobs を使うことは考えておらず、知り合い経由で気になる会社をいくつか受けて祈られるなどして過ごしました。
AtCoderJobs で転職活動
AtCoderJobs では 2 社受けました。
A 社
ウェブサービスの会社の研究開発の部門に応募しました。
事前課題として問題が1問出題されました。提出期限は1週間後だったので、落ち着いて解けば良かったのですが、たまたまその問題を過去にコンテストで解いたことがあったので、勢いに任せて書き上げて提出しました。嘘解法でした。後で見てみたら、そのコンテストでも同じ嘘解法で通してました。全く成長していない…… その後の面接では、提出したコードについて全く触れられなかったのですが、どういう気持ちで見ていたのか未だに気になっています。
面接では、ネットワークのことからコンパイラのことまで幅広く質問されました。今までの仕事の中で身につけた知識や、競プロや趣味を通して得た知識で答えられる質問もありましたが、全く何を聞かれてるのか分からない質問もいくつかあり、全体的に厳しい印象でした。また、面接官が英語話者のこともあり、答えがわかっても英語で何と言えば良いか分からず、独自の言い回しを発明するシーンが多々ありました。外資で1年働くくらいで英語がどうにかなったりはしないですね…… その他、事前に提出していた経歴書に沿って質問されることもありましたが、経歴書に書いていた内容があまりに少なかったため、話す際に毎回基本的な前提から話すことになり、具体的に達成したことや技術的な工夫などまで面接時間内に話しきれないことが多かったです。
最終面接まで行きましたが、研究開発の部門では不採用ということになり、追加でバックエンド開発の部署の面接を受けました。こちらの面接は普通のウェブ系の面接という感じで、ホワイトボードコーディングなどをして、無難に終えることができ、オファーをもらうことができました。オファー内容は900万円+ボーナスで、「他の部署の面接であんなにボロボロだったのにこんなに良いオファー出していいの……？」と思わず言ってしまいました。
indeed
indeed の Search Quality という部署に応募しました。
面接前に AtCoder で問題を解く課題がありましたが、いつも通りのコンテスト形式だったので、A社の反省を踏まえて、とにかく落ち着いて取り組むことに集中しました。indeed が Java を使う会社だということは事前の調べで分かっていたので、Rust で全完した後に Java で書き直して媚びておきました。
面接はオンライン1回とオンサイト3回があり、うち3回はコーディングインタビューでした。どの問題も、実際の業務でありそうな問題設定でありながら、面接官とディスカッションしながら解いていくうちに気づけば競プロ的な計算量改善ができている、という感じで面白かったです。残りの1回の面接では経歴書に沿って話したり、入社してからやりたい仕事などについて話したりしました。ここでもA社の反省を活かして、経歴書にはA4に収まる限りの情報を盛り込んでおいたので、面接時間を効率良く使うことができました（就活初心者か…？）。今回も英語話者の面接官がいましたが、A社の反省を踏まえて瞬間英作文をやり込んでおいたので、何とかなりました。最終的に1050万円+ボーナスでオファーが出ました。
A社もindeedも大規模なウェブサービスを実運用している会社でしたし、A社の方はボーナスが多いのと家賃補助があるのでindeedと待遇面での違いもあまりなく、どちらに行くかかなり迷いました。indeedで働いている知り合いに話を聞きに行ったときに強く勧められたことや、自分がJavaが好きなこと、G●●gle J●bs との新たな戦いを予感させることから、indeedに行くことにしました。
入社して
最初に感じたこととしては、開発サイクルがとても速いです。入社して最初の週で、実装とコードレビューを経て本番環境デプロイまでできたのには感動しました。開発サイクルを遅くしない工夫や、各人の仕事を可視化する工夫が随所にあり、日々学びがあります。
まとめ
AtCoderJobs は平気で1000万円くらいの案件が流れてくる激ヤバ転職サイト。
今日解いた問題
E - Prefix-free Game
実験によって grundy 数を求めるのはよく見る気がする。
use std::collections::{BTreeMap, BTreeSet}; fn main() { let s = std::io::stdin(); let mut sc = Scanner { stdin: s.lock() }; let n: usize = sc.read(); let l: u64 = sc.read(); let mut trie = Trie { nodes: vec![[0; 2]], }; for _ in 0..n { let s: Vec<usize> = sc .chars() .into_iter() .map(|c| c as usize - '0' as usize) .collect(); trie.add(&s, 0, 0); } let mut results = vec![]; trie.traverse(0, &mut results, l); println!( "{}", if results .into_iter() .map(|h| 1 << h.trailing_zeros()) .fold(0, |xor, x| xor ^ x) == 0 { "Bob" } else { "Alice" } ); } struct Trie { nodes: Vec<[usize; 2]>, } impl Trie { fn add(&mut self, s: &[usize], pos: usize, cur: usize) { if pos == s.len() { return; } if self.nodes[cur][s[pos]] == 0 { self.nodes[cur][s[pos]] = self.nodes.len(); self.nodes.push([0; 2]); } let cur = self.nodes[cur][s[pos]]; self.add(s, pos + 1, cur); } fn traverse(&self, cur: usize, results: &mut Vec<u64>, height: u64) { let (a, b) = (self.nodes[cur][0], self.nodes[cur][1]); if a == 0 && b == 0 { return; } if a == 0 || b == 0 { results.push(height); } if a != 0 { self.traverse(a, results, height - 1); } if b != 0 { self.traverse(b, results, height - 1); } } } fn grundy(l: usize, map: &mut BTreeMap<usize, usize>) -> usize { match map.get(&l) { Some(&x) => x, None => { let mut set = BTreeSet::new(); for i in 1..(l + 1) { let mut g = 0; for j in 1..i { g ^= grundy(l - j, map); } set.insert(g); } let g = (0..).find(|x| !set.contains(x)).unwrap(); map.insert(l, g); g } } } pub struct Scanner<R> { stdin: R, } impl<R: std::io::Read> Scanner<R> { pub fn read<T: std::str::FromStr>(&mut self) -> T { use std::io::Read; let buf = self .stdin .by_ref() .bytes() .map(|b| b.unwrap()) .skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r') .take_while(|&b| b != b' ' && b != b'\n' && b != b'\r') .collect::<Vec<_>>(); unsafe { std::str::from_utf8_unchecked(&buf) } .parse() .ok() .expect("Parse error.") } pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> { (0..n).map(|_| self.read()).collect() } pub fn chars(&mut self) -> Vec<char> { self.read::<String>().chars().collect() } }
エクサウィザーズ 2019 D - Modulo Operations
問題
解法
解説にあるとおり、ある数が使われた後、その数より大きい数を使ったとしても剰余には影響しないので、大きい数から順番に見ていって数列に詰めていくことを考える。
i番目(0 <= i < n )に大きい数 x_i を数列に詰める時、空いている場所は (n-i) ヶ所ある。この (n-i) ヶ所のうち一番前を除く (n-i-1) ヶ所のどこかに詰めると、x_i より小さい数が x_i の前に来ることになり、 x_i は剰余に対して影響しなくなる。一番前に詰めると x_i の前にある数は必ず x_i より大きくなるので、剰余に影響するようになる。
コード
const MOD: usize = 1e9 as usize + 7; fn main() { let s = std::io::stdin(); let mut sc = Scanner { stdin: s.lock() }; let n: usize = sc.read(); let x: usize = sc.read(); let mut s: Vec<usize> = sc.vec(n); s.sort(); s.reverse(); let mut dp = vec![0; x + 1]; dp[x] = 1; for i in 0..n { let mut next = vec![0; x + 1]; for j in 0..(x + 1) { // unused next[j] += dp[j] * (n - 1 - i); next[j] %= MOD; // used next[j % s[i]] += dp[j]; next[j % s[i]] %= MOD; } dp = next; } let mut ans = 0; for i in 0..s[n - 1] { ans += dp[i] * i; ans %= MOD; } println!("{}", ans); } pub struct Scanner<R> { stdin: R, } impl<R: std::io::Read> Scanner<R> { pub fn read<T: std::str::FromStr>(&mut self) -> T { use std::io::Read; let buf = self .stdin .by_ref() .bytes() .map(|b| b.unwrap()) .skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r') .take_while(|&b| b != b' ' && b != b'\n' && b != b'\r') .collect::<Vec<_>>(); unsafe { std::str::from_utf8_unchecked(&buf) } .parse() .ok() .expect("Parse error.") } pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> { (0..n).map(|_| self.read()).collect() } pub fn chars(&mut self) -> Vec<char> { self.read::<String>().chars().collect() } }
エクサウィザーズ 2019 E - Black or White
問題
解法
毎回 (i個目を取る時に白が無くなっている確率) + (i個目を取る時に白も黒も無くなっていない確率)/2 を出力する。 (i 個目を取る時に白が無くなっている確率) = (i-1個目を取る時に白が無くなっている確率) + (i-1個目で最後の白を取る確率) で求まる。
コード
use mod_int::ModInt; const MOD: usize = 1e9 as usize + 7; fn main() { let s = std::io::stdin(); let mut sc = Scanner { stdin: s.lock() }; let b: usize = sc.read(); let w: usize = sc.read(); let combination = Combination::new(b + w + 1, MOD); let mut inv_pow2 = vec![ModInt::new(1); b + w + 1]; inv_pow2[1] = ModInt::new(2).pow(MOD - 2); for i in 1..(b + w) { inv_pow2[i + 1] = inv_pow2[i] * inv_pow2[1]; } let mut w_zero = vec![ModInt::new(0); b + w + 1]; for i in 0..(w + b) { if i + 1 > w { w_zero[i + 1] = w_zero[i] + combination.get(i - 1, w - 1) * inv_pow2[i]; } } let mut b_zero = vec![ModInt::new(0); b + w + 1]; for i in 0..(b + w) { if i + 1 > b { b_zero[i + 1] = b_zero[i] + combination.get(i - 1, b - 1) * inv_pow2[i]; } } // eprintln!("{:?}", inv_pow2); for i in 1..(b + w + 1) { // black==0 let b_zero = if i > b { b_zero[i] } else { ModInt::new(0) }; // white==0 let w_zero = if i > w { w_zero[i] } else { ModInt::new(0) }; let other = ModInt::new(1) - b_zero - w_zero; let ans = other * inv_pow2[1] + w_zero; // eprintln!("b_zero={} w_zero={} other={}", b_zero.0, w_zero.0, other.0); println!("{}", ans.0); } } pub mod mod_int { use super::MOD; use std::ops::{Add, AddAssign, Mul, MulAssign, Sub, SubAssign}; type Num = usize; #[derive(Clone, Copy, Debug)] pub struct ModInt<T: Copy + Clone>(pub T); impl Add<ModInt<Num>> for ModInt<Num> { type Output = ModInt<Num>; fn add(self, rhs: ModInt<Num>) -> ModInt<Num> { self + rhs.0 } } impl Add<Num> for ModInt<Num> { type Output = ModInt<Num>; fn add(self, rhs: Num) -> ModInt<Num> { let mut t = rhs + self.0; if t >= MOD { t = t - MOD; } ModInt(t) } } impl Sub<Num> for ModInt<Num> { type Output = ModInt<Num>; fn sub(self, rhs: Num) -> ModInt<Num> { let rhs = if rhs >= MOD { rhs % MOD } else { rhs }; let value = if self.0 < rhs { self.0 + MOD } else { self.0 }; ModInt(value - rhs) } } impl Sub<ModInt<Num>> for ModInt<Num> { type Output = ModInt<Num>; fn sub(self, rhs: ModInt<Num>) -> ModInt<Num> { self - rhs.0 } } impl AddAssign<Num> for ModInt<Num> { fn add_assign(&mut self, other: Num) { *self = *self + other; } } impl AddAssign<ModInt<Num>> for ModInt<Num> { fn add_assign(&mut self, other: ModInt<Num>) { *self = *self + other; } } impl SubAssign<Num> for ModInt<Num> { fn sub_assign(&mut self, other: Num) { *self = *self - other; } } impl SubAssign<ModInt<Num>> for ModInt<Num> { fn sub_assign(&mut self, other: ModInt<Num>) { *self = *self - other; } } impl Mul<ModInt<Num>> for ModInt<Num> { type Output = ModInt<Num>; fn mul(self, rhs: ModInt<Num>) -> ModInt<Num> { self * rhs.0 } } impl Mul<Num> for ModInt<Num> { type Output = ModInt<Num>; fn mul(self, rhs: Num) -> ModInt<Num> { let t = (self.0 * rhs) % MOD; ModInt(t) } } impl MulAssign<Num> for ModInt<Num> { fn mul_assign(&mut self, rhs: Num) { *self = *self * rhs; } } impl MulAssign<ModInt<Num>> for ModInt<Num> { fn mul_assign(&mut self, rhs: ModInt<Num>) { *self = *self * rhs; } } impl ModInt<Num> { pub fn new(value: Num) -> Self { ModInt(value) } pub fn pow(self, e: usize) -> ModInt<Num> { let mut result = ModInt::new(1); let mut cur = self; let mut e = e; while e > 0 { if e & 1 == 1 { result *= cur; } e >>= 1; cur *= cur; } result } } } pub struct Combination { fact: Vec<usize>, inv_fact: Vec<usize>, modulo: usize, } impl Combination { pub fn new(max: usize, modulo: usize) -> Combination { let mut inv = vec![0; max + 1]; let mut fact = vec![0; max + 1]; let mut inv_fact = vec![0; max + 1]; inv[1] = 1; for i in 2..(max + 1) { inv[i] = inv[modulo % i] * (modulo - modulo / i) % modulo; } fact[0] = 1; inv_fact[0] = 1; for i in 0..max { fact[i + 1] = fact[i] * (i + 1) % modulo; } for i in 0..max { inv_fact[i + 1] = inv_fact[i] * inv[i + 1] % modulo; } Combination { fact: fact, inv_fact: inv_fact, modulo: modulo, } } pub fn get(&self, x: usize, y: usize) -> ModInt<usize> { assert!(x >= y); ModInt::new( self.fact[x] * self.inv_fact[y] % self.modulo * self.inv_fact[x - y] % self.modulo, ) } pub fn h(&self, n: usize, r: usize) -> ModInt<usize> { self.get(n + r - 1, r) } } pub struct Scanner<R> { stdin: R, } impl<R: std::io::Read> Scanner<R> { pub fn read<T: std::str::FromStr>(&mut self) -> T { use std::io::Read; let buf = self .stdin .by_ref() .bytes() .map(|b| b.unwrap()) .skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r') .take_while(|&b| b != b' ' && b != b'\n' && b != b'\r') .collect::<Vec<_>>(); unsafe { std::str::from_utf8_unchecked(&buf) } .parse() .ok() .expect("Parse error.") } pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> { (0..n).map(|_| self.read()).collect() } pub fn chars(&mut self) -> Vec<char> { self.read::<String>().chars().collect() } }
フルマラソンを走った時のメモ
初めてフルマラソンを走った。それなりに準備していったが、思ったとおりには走れなかった。今後も続けていきたい感じはするので、メモを残しておく。
準備として、本番前の2ヶ月は毎週1回20km走った。近所を走るのは苦手なので、毎回わざわざ水戸まで行って、水戸から大洗まで走るというコースで練習していた。これで基礎的な体力はできていたと思う。実際にマラソンでも、折り返し地点まではいつもの練習通りのペースで走れていた。だが、マラソンは42.195kmあるので、折り返しまではチュートリアルで、30kmまでは準備体操、30kmからマラソンが始まっていた。本番では折り返しまで普通に走り、そこから30kmまでペースが落ちていき、30kmから完全に歩くという感じになってしまった。体力が尽きたとか、長時間コンクリートの上を走り続けたので膝が痛くなったとかいったものではなく、前半の分の筋肉痛が後半に早くも出始めていて、足に力が入らなくなっていた。膝が痛くならないようにフォームを気をつけたり、水分補給をこまめに行ったりしていたが、筋肉が痛くなるのは想定外だった。前半に飛ばすと後半バテるというのはスタミナの話ではなく、前半の負荷が後半に筋肉痛として発生して動けなくなるということでもあったらしい。42kmの練習を少なくとも1回はやっておくべきだった。
それ以外の知見
- 荷物置き場があり、リュック1個くらいなら普通に預けておける。ガバガバの管理なので貴重品などは置けない。
- 給水所が3kmおきくらいにあり、トイレも1kmおきにあるので、水分に関しては全く不自由しなかった。
- 給水所には食品もあり、アンパンなども食べられた。
- 食品の種類は限られているので、アミノ酸ゼリーなど自分の好きな物を携帯している人も多く居た。
- 冷却スプレーがどのくらい効くのかはわからないが、携帯している人が多かった。練習で必要だと感じたら当日も持っていったほうが良さそう。
- イヤホンをしている人が結構居た。禁止されていない大会ではイヤホンを持っていっても良いかも知れない。
キーエンス プログラミング コンテスト 2019: E - Connecting Cities
問題
解法
の値が大きい方から小さい方に辺を張ると考えても良いので、そう考える。
となるような i, j, k を考え、頂点kからiかjのどちらかに辺を引くことを考える。
- i-j 間のコストは
- j-k 間のコストは
- i-k 間のコストは
の場合、
だから
だから j-k 間に辺が張られるより先に i-k 間および i-j 間にパスが存在するので、 j-k 間に辺が張られることはない。
同様にして の場合、 i-k 間に辺が張られることはない。
よって頂点 k から となるような頂点 i へ辺を張ることを考える時、
が最小であるような i のみについて考えれば良い。
となるような i についても同様。
コード
use std::cmp; const INF: usize = 1e16 as usize; fn main() { let s = std::io::stdin(); let mut sc = Scanner { stdin: s.lock() }; let n = sc.read(); let d: usize = sc.read(); let a: Vec<usize> = sc.vec(n); let mut ai: Vec<(usize, usize)> = a.iter().enumerate().map(|(i, &a)| (a, i)).collect(); ai.sort(); let mut left_seg = SegmentTree::new(n, (INF, 0), |a, b| cmp::min(a, b)); let mut right_seg = SegmentTree::new(n, (INF, 0), |a, b| cmp::min(a, b)); let mut edges = vec![]; for (_, i) in ai.into_iter() { if i > 0 { let (tmp, j) = left_seg.query(0, i); if tmp < INF { let cost = (i - j) * d + a[i] + a[j]; edges.push((cost, i, j)); } } if i + 1 < n { let (tmp, j) = right_seg.query(i + 1, n); if tmp < INF { let cost = (j - i) * d + a[i] + a[j]; edges.push((cost, i, j)); } } left_seg.update(i, (a[i] + (n - i) * d, i)); right_seg.update(i, (a[i] + i * d, i)); } edges.sort(); let mut ans = 0; let mut uf = UnionFind::new(n); for (cost, i, j) in edges.into_iter() { if uf.find(i) == uf.find(j) { continue; } uf.unite(i, j); ans += cost; } println!("{}", ans); } pub struct SegmentTree<T, F> { seg: Vec<T>, n: usize, f: F, initial_value: T, } impl<T: Copy, F> SegmentTree<T, F> where F: Fn(T, T) -> T, { pub fn new(size: usize, initial_value: T, f: F) -> SegmentTree<T, F> { let mut m = 1; while m <= size { m <<= 1; } SegmentTree { seg: vec![initial_value; m * 2], n: m, f: f, initial_value: initial_value, } } pub fn update(&mut self, k: usize, value: T) { let mut k = k; k += self.n - 1; self.seg[k] = value; while k > 0 { k = (k - 1) >> 1; self.seg[k] = (self.f)(self.seg[k * 2 + 1], self.seg[k * 2 + 2]); } } /// Get the minimum value in the array in the range [a, b) /// /// # Panics /// /// Panics if `a >= b`. pub fn query(&self, a: usize, b: usize) -> T { assert!(a < b); self.query_range(a, b, 0, 0, self.n) } fn query_range(&self, a: usize, b: usize, k: usize, l: usize, r: usize) -> T { if r <= a || b <= l { self.initial_value } else if a <= l && r <= b { self.seg[k] } else { let x = self.query_range(a, b, k * 2 + 1, l, (l + r) >> 1); let y = self.query_range(a, b, k * 2 + 2, (l + r) >> 1, r); (self.f)(x, y) } } } pub struct UnionFind { parent: Vec<usize>, sizes: Vec<usize>, size: usize, } impl UnionFind { pub fn new(n: usize) -> UnionFind { UnionFind { parent: (0..n).map(|i| i).collect::<Vec<usize>>(), sizes: vec![1; n], size: n, } } pub fn find(&mut self, x: usize) -> usize { if x == self.parent[x] { x } else { let px = self.parent[x]; self.parent[x] = self.find(px); self.parent[x] } } pub fn unite(&mut self, x: usize, y: usize) -> bool { let parent_x = self.find(x); let parent_y = self.find(y); if parent_x == parent_y { return false; } let (large, small) = if self.sizes[parent_x] < self.sizes[parent_y] { (parent_y, parent_x) } else { (parent_x, parent_y) }; self.parent[small] = large; self.sizes[large] += self.sizes[small]; self.sizes[small] = 0; self.size -= 1; return true; } } pub struct Scanner<R> { stdin: R, } impl<R: std::io::Read> Scanner<R> { pub fn read<T: std::str::FromStr>(&mut self) -> T { use std::io::Read; let buf = self .stdin .by_ref() .bytes() .map(|b| b.unwrap()) .skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r') .take_while(|&b| b != b' ' && b != b'\n' && b != b'\r') .collect::<Vec<_>>(); unsafe { std::str::from_utf8_unchecked(&buf) } .parse() .ok() .expect("Parse error.") } pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> { (0..n).map(|_| self.read()).collect() } pub fn chars(&mut self) -> Vec<char> { self.read::<String>().chars().collect() } }
