ABC386:Rustで解く！問題解説
AtCoder Beginner Contest 386のA~E問題をRustで解いた際の解法をまとめました。
A問題
- 問題
- 解説
1〜13までの各カードが何枚あったのかを数えます。任意のカードを1枚追加してフルハウスとなるのは、以下の条件(1)または(2)を満たす場合です。それぞれチェックします。
(1) 3枚同じカードが1種類、かつ1枚だけのカードが1種類、残りは全て0枚
(2) 2枚同じカードが2種類、残りは全て0枚
カードの枚数が多い順に並び替えて枚数の多いもの2つを見ると、(1)または(2)を満たしているかどうかを判定できます。
- コード
use proconio::{input, marker::Usize1};
fn main() {
input!{
abcd: [Usize1; 4],
}
// 1〜13までのカードの枚数を数える(0始まり)
let mut cnt = vec![0; 13];
for i in 0..4 {
cnt[abcd[i]] += 1;
}
// 降順にして上位2つが(3,1)または(2,2)ならOK
cnt.sort();
cnt.reverse();
if (cnt[0] == 3 && cnt[1] == 1) || (cnt[0] == 2 && cnt[1] == 2) {
println!("Yes");
} else {
println!("No");
}
}
B問題
- 問題
- 解説
文字列Sについて、文字の固まりごとに順番に見ていきます。
これはランレングス圧縮を用いて変換すると良いです。
文字の固まりに現れる文字の値に応じて、(1)または(2)の回数を数えていきます。
(1) 文字が1~9の場合
文字の個数分ボタンを押します。
(2) 文字が0の場合
0を2個で001個に置き換えてボタンを押します。0が奇数個だった場合は、00にできない0が1個残るため追加で0を押します。したがって、(連続した0の個数/2)を切り上げした回数分のボタンを押します。
- コード
use proconio::{input, marker::Chars};
fn main() {
input! {
s: Chars,
}
// ランレングス圧縮して、(文字,連続個数)のリストを作成する
let rang = ranglen(&s);
let mut ans = 0;
for &(ch, cnt) in &rang {
// 0のみ、(連続個数 / 2) の切り上げ
if ch == '0' {
ans += (cnt + 1) / 2;
} else {
ans += cnt; // 1~9の場合はそのまま加算
}
}
println!("{}", ans);
}
// ランレングス圧縮
pub fn ranglen(arr: &Vec<char>) -> Vec<(char, usize)> {
let len = arr.len();
let mut arr_ret = Vec::new();
let mut tail = 0;
let mut top = 0;
while tail < len {
let now_c = arr[tail];
while top < len && now_c == arr[top] {
top += 1;
}
arr_ret.push((now_c, top - tail)); // 現在の文字とその連続数を記録
tail = top;
}
arr_ret
}
C問題
- 問題
- 解説
文字列SとTの長さに応じて場合分けします。
(1) 文字列SとTの長さが一致する場合
完全一致か、違う箇所が1つだけである必要があります。文字列SとTを順に見て、異なる文字数が1つ以下かどうかを確認します。
(2) 文字列SとTの長さが1つ違う場合
文字列 S が1文字多い場合は1文字削除、文字列Sが1文字少ない場合は1文字挿入で一致する可能性があります。文字列の長さが短い方を基準にして文字列SとTを順に見ていき、違っていたら1つだけ飛ばして中身が一致するかどうかを確認します。
(3) 文字列S と Tの長さが2つ以上違う場合
文字を1つ追加または削除しても一致させることは不可能です。
- コード
use proconio::{input, marker::Chars};
use std::mem::swap;
fn main() {
input! {
_k: usize, // kは1固定
mut s: Chars, // 文字列S
mut t: Chars, // 文字列T
}
// sとtの文字数が一致
if s.len() == t.len() {
// 完全一致か、違う箇所が一つであればよい。
let mut cnt = 0; // 異なる文字の数
for i in 0..s.len() {
if s[i] != t[i] { cnt += 1; }
}
if cnt <= 1 {
println!("Yes");
} else {
println!("No");
return;
}
}
// sとtの文字数が異なる
else {
// 文字数がs < tとなるようにswap
if s.len() > t.len() {
swap(&mut s, &mut t);
}
// 文字数が2以上違う場合は、不可
if t.len() - s.len() >= 2 {
println!("No");
return;
}
// 文字列sにあるものがtに全て表れるかを見る
let mut cnt = 0; // 異なる文字のオフセット
for i in 0..s.len() {
// 文字が一致するまでループ
while s[i] != t[i + cnt] {
cnt += 1;
// 2つ以上ずれたら不可
if cnt == 2 {
println!("No");
return;
}
}
}
println!("Yes");
return;
}
}
D問題
- 問題
- 解説
問題文に書かれている条件について考えます。
- すべての行について以下の条件が成り立つ。
ある整数が存在して、その行の左から i (0 \leq i \leq N) i個のマスは黒、それ以外は白で塗られている。- すべての列について以下の条件が成り立つ。
ある整数が存在して、その列の上から i (0 \leq i \leq N) i個のマスは黒、それ以外は白で塗られている。
これは以下図のように、黒マスが各行の左端から、各列の上端から塗られていて、間に白マスが含まれていないことを指します。
図より、上から下に進むにつれ、左端から右に塗ることができる黒マスが減っていることがわかるため、上から考えればよいとわかります。(左から右に見た場合も同様です。)
次に、各行について左端から右に見た場合のW,Bについて考えます。
-
W:マス(x,y)に存在する場合、左隣のマスのy-1列目までしか黒で塗れなくなります。また次の行以降についてもy-1列目までしか黒で塗れなくなります。 -
B:マス(x,y)に存在する場合、y列目まで黒で塗らないといけません。Wの条件より、y列目まで黒で塗ることができない場合は問題文の条件を満たせなくなります。
このことから、Wのマスで見た条件に矛盾しないようにBのマスが黒で塗れるかどうかを見ていけばよいです。各列に対して考えた場合も同じことが言えるので、行と列両方で試して問題文の条件に矛盾しないかをチェックすればよいです。
- コード
use proconio::input;
use std::cmp::min;
fn main() {
input! {
n: usize, m: usize,
mut xyc: [(usize, usize, char); m],
}
xyc.sort();
// 横方向に見る
if !paint_check(n, m, &xyc) {
println!("No");
return;
}
// 縦横入れ替える
let mut yxc = Vec::new();
for (x, y, c) in xyc {
yxc.push((y, x, c));
}
yxc.sort();
// 入れ替え後の横方向(縦方向)に見る
if !paint_check(n, m, &yxc) {
println!("No");
return;
}
println!("Yes");
fn paint_check(n: usize, _m: usize, xyc: &Vec<(usize, usize, char)>) -> bool {
// 横方向に塗ることができる最大数
let mut paint_max = n;
// 昇順に調べて、横方向に塗れるかどうかをチェック
for &(_x, y, c) in xyc {
if c == 'W' {
paint_max = min(paint_max, y - 1);
} else {
if y > paint_max {
return false;
}
}
}
true
}
}
E問題
- 問題
-
解説
問題文の制約より、\binom{N}{K} 10^6 10^6 K \binom{N}{K} K K K N K O(\binom{N}{K} K)
このため、2つ目のパターンでは、選ばないN-K A -
コード
use proconio::input;
use std::cmp::max;
fn main() {
input! {
n: usize, k: usize,
mut a: [usize; n],
}
// ダミーをセットして、aの配列を1始まりにする
a.insert(0, 0);
// k < n-kならそのまま全探索。
// k > n-kなら全探索した結果にa全体のXORでmaskする
let mut mask = 0;
let mut sz_k = k;
if k > n - k {
sz_k = n - k;
for &aa in &a {
mask ^= aa; // 配列aの全体のXORを計算
}
}
// n C sz_kを全探索
let mut ans = 0;
fn rec(
cnt: usize, sz_k: usize, // 選んだ個数、選ぶ必要がある個数
now_i: usize, a: &Vec<usize>, n: usize, // 現在選択中のインデックス、配列aとサイズ
ret: usize, // 現在のXOR値
ans: &mut usize, mask: usize // 答え(最大値)とXORするmask値
) {
// sz_k個選んだ場合、maskとのXORを取る
if cnt == sz_k {
*ans = max(*ans, ret ^ mask);
return;
}
// まだ選んでいないものを一つ選ぶ
for next_i in now_i + 1..=n {
rec(cnt + 1, sz_k, next_i, a, n, ret ^ a[next_i], ans, mask);
}
}
rec(0, sz_k, 0, &a, n, 0, &mut ans, mask);
println!("{}", ans); // 最大のXOR値を出力
}
Discussion