はじめに
AtCoder Beginner Contest 269 の C問題までを Rust で解きました！
詳しめに解説をしていこうと思います。
役にたちましたらいいねいただけると嬉しいです。
AC 確認はしてますが、もっとスマートな書き方がありましたら教えてください。
なぜやるのか
プログラミングは知っているけれどアルゴリズムは知らない、という方に向けて書いています。半分は社内向けです。
また、私は Rust に慣れておらず、その練習のためにやっています。
(コンテスト本番には C++ を使って参加している水色コーダーです。)
問題
A - Anyway Takahashi (Difficulty 8)
B - Rectangle Detection (Difficulty 68)
C - Submask (Difficulty 384)
D - Do use hexagon grid (Difficulty 612)
E - Last Rook (Difficulty 1030)
F - Numbered Checker (Difficulty 1601)
G - Reversible Cards 2 (Difficulty 2440)
Ex - Antichain (Difficulty 3178)
前提
この記事にあるコードはこちらを import しています。
#[allow(unused_imports)]
use proconio::{input, fastout, marker::Chars, marker::Usize1};
#[allow(unused_imports)]
use std::collections::{HashSet, HashMap, BTreeSet, VecDeque};
#[allow(unused_imports)]
use std::cmp::{max, min};
#[allow(unused_imports)]
use itertools::Itertools;
A - Anyway Takahashi
問題文そのままですね。
引き算があるので isize で受け取ることに注意です。
usize で受け取ると、 $C-D$ の結果が負になるときに panick します。
input! {
a: isize,
b: isize,
c: isize,
d: isize
}
println!("{}", (a + b) * (c - d));
println!("Takahashi");
B - Rectangle Detection
入力でもらった文字の中から四角形の領域を切り取る問題ですね。
考察
出力する $A,B,C,D$ について考えてみます。
$A$ は四角形の上
$B$ は四角形の下
$C$ は四角形の左
$D$ は四角形の右
になります。
ここで、$A$について言い換えると、「上下方向」の「最小値」と言えますね。
他の要素もいいかえると、
$A$ は「上下方向」の「最小値」
$B$ は「上下方向」の「最大値」
$C$ は「左右方向」の「最小値」
$D$ は「左右方向」の「最大値」
となります。上下方向と左右方向に分解して実装できることがわかりました。
実装
$A$ は「上下方向」の「最小値」
について考えます。 (y, x) 座標について、「上下方向」は y ですね。なので、 $A$ は y の最小値を求めます。
ほかの $B,C,D$ についても同様にすると答えがわかります。
a,b,c,d は初期値に注意です。a,c は最小値を求めるので、マスの最大サイズである 10以上の数にして、b,d はマスの最小サイズである 1以下の数にします。
実装はこのようになりました。
input! {
mp: [Chars; 10]
}
let mut a = 100;
let mut b = 0;
let mut c = 100;
let mut d = 0;
for y in 0..10 {
for x in 0..10 {
if mp[y][x] == '#' {
a = min(a, y + 1); // a は「上下方向」の「最小値」
b = max(b, y + 1); // b は「上下方向」の「最大値」
c = min(c, x + 1); // c は「左右方向」の「最小値」
d = max(d, x + 1); // d は「左右方向」の「最大値」
}
}
}
println!("{} {}", a, b);
println!("{} {}", c, d);
C - Submask
2進数がでてくる問題です。慣れていないとびっくりするかもしれません。
考察
問題文は複雑ですが、問題文の出力例1 をみてみると考えやすいです。
$N = 1011_{(2)}$ の時の答えは
$0000_{(2)}$、$0001_{(2)}$、$0010_{(2)}$、$0011_{(2)}$、$1000_{(2)}$、$1001_{(2)}$、$1010_{(2)}$、$1011_{(2)}$ ですね。これらの数値は、$N$ の桁をひとつずつ見て、「0 ならば 0」「1ならば0か1」というものになっています。
これはつまり、整数 x について、 if x | N == N を満たせば x は答えになります。計算量を考えると $O(N)$ なのですが、$0 \le N \lt 2^{60}$ なので、実行時間制限に間に合いません。なにか高速化が必要です。
上に書きましたが「1ならば0か1」なので、$N$の桁で1となる位ひとつにつき2通りの答えができます。これに注目します。問題文より、$N$の桁で 1となる位は15個以下ですね。つまり、答えの数値は最大で $2^{15} = 32768$個です。全探索できそうです。
$N$ の桁で 1となる場所を記憶しておいて、それぞれの場所を使うかどうかを探索します。「使うかどうか」は bit全探索が有効です。
計算量を考えると、$N$ の桁で 1 となっている個数を $n$ とすると、答えの数値をひとつ作るのに $O(n)$ かかります。これが $2^n$ 個あるので、全体では $O(n * 2^n)$ になります。 $1 \le n \le 15$ なので、実行時間制限内に解けそうなことがわかります。
実装
実装です。
$N$ の桁で 1 となっている場所を pos に保存します。
mask の桁を見て、 i番目の桁が 1 になっていたら、pos[i] を使用します。
( mask という名前は bit mask からきています。)
1<<sz はシフト演算です。$2^{sz}$ の値が得られます。
mask >> i もシフト演算です。$ mask / 2^i$ (切り捨て) の値が得られます。
if mask >> i & 1 == 1 は、mask を2進数で見たときに右から i 番目の位が 1 かどうかを判定しています。
コードは以下のようになりました。
input! {
n: usize
}
let mut pos = vec![];
for i in 0..60 {
if n >> i & 1 == 1 { // n の右から i 番目の桁が 1 ならば
pos.push(i);
}
}
let sz = pos.len();
let mut ans = vec![];
for mask in 0..1<<sz { // 0 から 2 ^ {sz} まで
let mut score = 0_u64; // usize は 32bit になることがあるので u64 型で
for i in 0..sz {
if mask >> i & 1 == 1 { // mask の右から i 番目の桁が 1 ならば
score += 1 << pos[i]; // 2 ^ {pos[i]} を足す
}
}
ans.push(score);
}
ans.sort();
for v in ans.into_iter() {
println!("{}", v);
}
最後まで読んでいただきありがとうございます！