AtCoder Beginner Contest 416
今回もRustでのバーチャル参加です。
文法を調べつつやりABCDの三完でした。
A~Dまでまとめます。
A - Vacation Validation
$S$の$L$番目から$R$番目のスライスを取得して、$\text{Iterator}$トレイトのallメソッドで全ての文字がoであるかを確認すればよいです。
use proconio::input;
fn main() {
input! {
n: usize,
l: usize,
r: usize,
s: String,
}
let s = s.chars().collect::<Vec<_>>();
if s[l - 1..r].iter().all(|&c| c == 'o') {println!("Yes")} else {println!("No")}
}
B - 1D Akari
oの文字数の最大値を考えるにあたり、文字列$T$がどのような状態でなければいけないのかを考えましょう。特に、問題文中の条件4が大きなヒントになります。
$T_i = T_j = $o $(i < j)$ ならば、$T_{i+1}, \ldots, T_{j-1}$ の中に # が $1$ つ以上存在する。
この条件により、o..oのように、o同士の間に#がない部分が存在するような文字列はNGとなり、o.#oのような文字列が許されます。他にも、o..#.o#.oのような文字列も条件を満たします。
このことから、#同士で挟まれた範囲、もしくは#と （端）で挟まれた範囲には最大で一つしかoが入る余地がないということが言えます。
これを考慮すると、文字列$T$は「左から順に文字列$S$を確認し、#なら#を、.なら直前が#の場合o、そうでない場合.を追加する」という極めて単純なアルゴリズムにより復元できます。
これはつまり、#と#の間の空間に左詰でoを追加するということです。
use proconio::input;
fn main() {
input! {
s: String,
}
let s = s.chars().collect::<Vec<_>>();
let mut t = String::new();
let mut f = false;
for i in 0..s.len() {
if s[i] == '#' {
t.push('#');
f = false;
} else {
if f {t.push('.');} else {t.push('o');}
f = true;
}
}
println!("{}", t);
}
C - Concat (X-th)
まずは問題設定をきちんと理解しましょう。
サンプル1で整理します。
3 2 6
abc
xxx
abc
3つの文字列を2回連結させて、辞書順で6番目に小さい連結文字列を出力します。
文字列の連結方法としては、$S_i + S_j \ (i, j \in {1, 2, 3})$で全部で$3^2=9$通りあります。
ここでまず着目すべき点としては、$N\le10,K\le5$のため、最大でも$NK=10^5$通りしかありえる連結方法はありません。また、$S_i\le10$でもあるため、愚直に全探索しても最大で$NK|S|=10^6$の計算量にしかなりません。そして、辞書順に並べ替えるためのソートは$O(NK|S|log(NK|S))$で行えますから、実行速度としては愚直に全探索して十分に間に合うということがわかります。
あとはどのように実装すべきかですが、連結回数$K$が変数であるためfor文で実装するのはやや面倒です。このような場合は深さ優先探索（dfs）が有用です。
詳細な実装は以下のACコードを参照してください。
use proconio::input;
fn main() {
input! {
n: usize,
k: usize,
x: usize,
s: [String; n],
}
let mut str_arr = vec![String::new(); 0];
fn dfs(
n: usize,
s: &[String],
k: usize,
x: usize,
cur: usize,
cur_str: String,
str_arr: &mut Vec<String>,
) {
if cur == k {
str_arr.push(cur_str);
return;
}
for i in 0..n {
let str = format!("{}{}", cur_str, s[i]);
dfs(n, s, k, x, cur + 1, str, str_arr);
}
}
dfs(n, &s, k, x, 0, String::new(), &mut str_arr);
str_arr.sort();
let ans = &str_arr[x - 1];
println!("{}", ans);
}
D - Match, Mod, Minimize 2
まず、$\sum_{i=1}^{N} ((A_i + B_i) \bmod M)$について考えましょう。
何気ないのですが$0\le A_i, B_i < M$という条件がヒントになります。
もし$A_i+B_i\ge M$となる回数$\text{cnt}$がわかっている場合、
$\sum_{i=1}^{N} ((A_i + B_i) \bmod M)=\sum_{i=1}^{N} A_i +\sum_{i=1}^{N} B_i - \text{cnt} \times M $という式変形が可能です。
ここで、$\sum_{i=1}^{N} A_i$や$\sum_{i=1}^{N} B_i$や$M$は定数なので、右辺を最小化するためには$\text{cnt}$、つまり$A_i$と$B_i$を足し合わせたら$M$以上になる回数を最大化するしかないと気づきます。
これは、$A$の大きいものから順に、$B$のなるべく小さい要素をマッチングさせていくという貪欲法で求めることができます。また、この貪欲法は尺取り法などのアルゴリズムで実現することができます。
以上、ソートがボトルネックとなり$O(NlogN)$でこの問題を解くことができました。
use proconio::input;
fn main() {
input! {
t: usize
}
let mut ans = vec![];
for _ in 0..t {
input! {
n: usize,
m: usize,
a: [usize; n],
b: [usize; n],
}
let mut a = a;
let mut b = b;
a.sort_by(|x, y| y.cmp(x));
b.sort();
let mut total = a.iter().sum::<usize>() + b.iter().sum::<usize>();
let mut j = 0;
for i in 0..n {
while j < n && a[i] + b[j] < m{
j += 1;
}
if j < n {
total -= m;
j += 1;
}else {
break;
}
}
ans.push(total);
}
println!("{}", ans.iter().map(|x| x.to_string()).collect::<Vec<_>>().join("\n"));
}
まとめ
Rustを触り始めてから1週間ほど経過しました。The Rust Programming Language 日本語版を読みながら勉強しているのですが、一旦競技プログラミングで困らない程度には基礎文法を理解することができたと思います。
もっと早く慣れて、何かものづくりにも生かせるようなレベルに持っていきたいです。