はじめに
Rustの勉強のためにAtCoderのコンテストでRustを使うことにしました。
解説を読んだりして自分がわかった範囲で復習します。
復習
A - Power
提出
愚直にAのB乗を求める。
型がi64とu32なのは「Rust pow」で検索して上にあったからだったと思う。
use proconio::input;
fn main() {
input! {
a: i64,
b: u32,
}
println!("{}", a.pow(b));
}
B - First Query Problem
提出
愚直に実装すると各クエリは$O(1)$で計算できるので間に合う。
use proconio::input;
use proconio::marker::Usize1;
fn main() {
input! {
n: usize,
mut a: [u64; n],
q: usize,
}
for _ in 0..q {
input! {
t: u64,
}
if t == 1 {
input! {
k: Usize1,
x: u64,
}
a[k] = x;
} else {
input! {
k: Usize1,
}
println!("{}", a[k]);
}
}
}
C - Cash Register
提出
要は$S$の1文字につき1回ボタンを押していく。ただし、00は1回ボタンを押すだけで入力できる。
数字はとても大きいのでu64などの数値型ではなく文字列型で受け取る。
前から1文字ずつ見ていき、その文字と後ろの文字が両方0なら後ろの0をスキップして何文字見たかをカウントする。
$S$が0の場合は例外として1ではなく0を出力する必要があるが今回は制約で$S$が1以上なので考慮しなくてもよい。
use proconio::input;
use proconio::marker::Chars;
fn main() {
input! {
s: Chars,
}
let mut ans = 0u64;
let n = s.len();
let mut i = 0usize;
while i < n {
if s[i] == '0' && i + 1 < n && s[i+1] == '0' {
i += 1;
}
i += 1;
ans += 1;
}
println!("{}", ans);
}
D - Scope
提出
文字列を前から見ていき今まで見たことある文字が出たら失神する。ただし既に閉じられた括弧の中の文字は忘れる。
見た文字の管理はセットを使うことでできるが、括弧の中の文字を忘れる処理が難しい。
なので括弧の中を再帰関数で処理してセットを再帰関数内でコピーすることで忘れることにした。
再帰関数は返り値をOption型にし、失神した場合はNone、意識を保っている場合は$S$の次に見るべきインデックスを返すことにした。
関数が終了する条件は閉じ括弧を見つけたとき、または文字列の終端にしている。(おそらくこの処理のおかげで良い文字列でないテストケースに対しても正しい答えが出せていると思う。それがいいことかは別として)
ここでセットのコピーは$O(|S|)$かかりそうに見えるが文字は英小文字26種のみなので$O(1)$で行える。
use proconio::input;
use proconio::marker::Chars;
use std::collections::HashSet;
fn recursive(start: usize, n: usize, s: &Vec<char>, mut set: &mut HashSet<char>) -> Option<usize> {
let mut i = start;
while i < n {
if s[i] == '(' {
let mut new_set = set.clone();
match recursive(i+1, n, &s, &mut new_set) {
Some(index) => {
i = index;
},
None => {
return None;
}
}
} else if s[i] == ')' {
return Some(i+1);
} else {
if !set.insert(s[i]) {
return None;
}
i += 1;
}
}
return Some(n);
}
fn main() {
input! {
s: Chars,
}
let mut set = HashSet::new();
match recursive(0, s.len(), &s, &mut set) {
Some(_) => {
println!("Yes");
},
None => {
println!("No");
}
}
}
E - Don't Isolate Elements
提出
行列のマスに2種類の数字が書かれていて、各マスに対して自分の上下左右のマスに同じ数字があるようにできるだけ少ない行の各マスを反転($A_{i,j}$を$1-A_{i,j}$に置き換える)させる。
上下左右だけ見ればいいので一番上の行から順に自分より①2つ上の行と②1つ上の行、③自分自身の行に対して、反転させた場合と反転させていない場合の全てのパターンで②1つ上の行で孤立した要素がないかをチェックし最小の操作回数を求める。
状態を管理するのでDPを使用した。
$dp[i][j][k]$は上から$i$行目(0-indexed)を見ているとき、$i-1$行目の反転状態が$j$、$i$行目の反転状態が$k$でかつ、$i-1$行目までに孤立した要素がないように全体を反転させ場合の最小の操作回数になる。
ここで反転状態は$0$(反転させていない)、$1$(反転させた)の2つの状態を数字で表している。
また、$dp[i][j][k]$の値はOptionにしており、そのようなパターンで孤立した要素がなければSome、あればNoneにしている。
DPの更新は
dp[i][previous][current] = min(
dp[i][previous][current],
dp[i-1][previus2][previous] + current
)
としている。
ここで$previous2$は現在位置の2つ上、$previous$は現在位置の1つ上、$current$は現在行の反転状態になっている。
現在の行を反転させる場合に操作回数が1増えることを$+current$で表している(横着している)。
use proconio::input;
use std::cmp::min;
fn main() {
input! {
h: usize,
w: usize,
a: [[i64; w]; h],
}
// dp[i][j][k]
// j: 2-previous flip
// k: previous flip
let mut dp = vec![vec![vec![None; 2]; 2]; h];
dp[0][0][0] = Some(0u64);
dp[0][0][1] = Some(1u64);
for y in 1..h {
for previous2 in 0..2 {
for previous in 0..2 {
if dp[y-1][previous2][previous] == None {
continue;
}
for current in 0..2 {
let mut is_valid = true;
for x in 0..w {
let mut is_isolated = true;
if 0 < x && a[y-1][x] == a[y-1][x-1] {
is_isolated = false;
}
if x + 1 < w && a[y-1][x] == a[y-1][x+1] {
is_isolated = false;
}
if 1 < y && (previous as i64 - a[y-1][x]).abs() == (previous2 as i64 - a[y-2][x]).abs() {
is_isolated = false;
}
if (previous as i64 - a[y-1][x]).abs() == (current as i64 - a[y][x]).abs() {
is_isolated = false;
}
if is_isolated {
is_valid = false;
}
}
let pd = dp[y-1][previous2][previous].unwrap() + current as u64;
if is_valid {
dp[y][previous][current] = Some(match dp[y][previous][current] {
Some(d) => min(d, pd),
None => pd,
});
}
}
}
}
}
let mut ans = None;
for previous in 0..2 {
for current in 0..2 {
if dp[h-1][previous][current] == None {
continue;
}
let mut is_valid = true;
for x in 0..w {
let mut is_isolated = true;
if 0 < x && a[h-1][x] == a[h-1][x-1] {
is_isolated = false;
}
if x + 1 < w && a[h-1][x] == a[h-1][x+1] {
is_isolated = false;
}
if (current as i64 - a[h-1][x]).abs() == (previous as i64 - a[h-2][x]).abs() {
is_isolated = false;
}
if is_isolated {
is_valid = false;
}
}
let d = dp[h-1][previous][current].unwrap();
if is_valid {
ans = Some(match ans {
Some(a) => min(a, d),
None => d,
})
}
}
}
match ans {
Some(a) => {
println!("{}", a);
},
None => {
println!("-1");
}
}
}
F - Permutation Distance
提出(時間内には解けていない)
$i$と$j$の選び方によって計算が4通りあるのでSegmentTreeで全パターン管理する。
\begin{equation}
|P_i - P_j| + |i - j| = \left\{
\begin{array}{}
P_j - P_i + j - i (P_i < P_j \& i < j) \\
P_j - P_i + i - j (P_i < P_j \& j < i) \\
P_i - P_j + j - i (P_j < P_i \& i < j) \\
P_i - P_j + i - j (P_j < P_i \& j < i)
\end{array}
\right.
\\
= \left\{
\begin{array}{1}
(P_j + j) - P_i - i (P_i < P_j \& i < j) \\
(P_j - j) - P_i + i (P_i < P_j \& j < i) \\
(-P_j + j) + P_i - i (P_j < P_i \& i < j) \\
(- P_j - j) + P_i + i (P_j < P_i \& j < i)
\end{array}
\right.
\end{equation}
上の式のように変形し、$i$と$j$を分けておく。
SegmentTreeでは常に最小の値が取れるようにしておき、上記の4パターンそれぞれについて作成しておく。
$D_i$を求める手順は、まず$P_i < P_j$の場合の2つのSegmentTreeに$j$に関する値を入れる。
その後、$P_i$が小さい方から順に$D_i$を求めていく。
求める前に$P_i < P_j$のパターンのSegmentTreeから自身の値を消し、$i == j$ということが起きないようにする。
そして、各パターンのSegmentTreeで条件を満たす範囲のインデックスで最小値を取得し、上記の式に代入したものの内一番小さい数を答えとしてセットする。
その後、$P_j < P_i$のパターンのSegmentTreeに自身の値を追加する。
use proconio::input;
use proconio::marker::Usize1;
use std::cmp::min;
#[derive(Clone)]
struct SegmentTree {
n: usize,
data: Vec<i64>,
}
impl SegmentTree {
fn new(n: usize) -> Self {
let mut i = 1;
while i < n {
i *= 2;
}
SegmentTree {
n: i,
data: vec![0; 2*i-1],
}
}
fn eval(&mut self, val1: i64, val2: i64) -> i64 {
return std::cmp::min(val1, val2);
}
fn add(&mut self, index: usize, value: i64) {
let mut index = self.n + index - 1;
self.data[index] += value;
while 0 < index {
index = (index - 1) / 2;
let val1 = self.data[2*index+1];
let val2 = self.data[2*index+2];
self.data[index] = self.eval(val1, val2);
}
}
fn sub(&mut self, index: usize, value: i64) {
let mut index = self.n + index - 1;
self.data[index] -= value;
while 0 < index {
index = (index - 1) / 2;
let val1 = self.data[2*index+1];
let val2 = self.data[2*index+2];
self.data[index] = self.eval(val1, val2);
}
}
fn set(&mut self, index: usize, value: i64) {
let mut index = self.n + index - 1;
self.data[index] = value;
while 0 < index {
index = (index - 1) / 2;
let val1 = self.data[2*index+1];
let val2 = self.data[2*index+2];
self.data[index] = self.eval(val1, val2);
}
}
fn _query(&mut self, index: usize, l: usize, r: usize, left: usize, right: usize) -> Option<i64> {
if r <= left || right <= l {
return None;
} else if l <= left && right <= r {
return Some(self.data[index]);
} else {
let mid = (left + right) / 2;
let val1 = self._query(2*index+1, l, r, left, mid);
let val2 = self._query(2*index+2, l, r, mid, right);
if val1 == None {
return val2;
}
if val2 == None {
return val1;
}
return Some(self.eval(val1.unwrap(), val2.unwrap()));
}
}
fn query(&mut self, l: usize, r: usize) -> i64 {
return self._query(0, l, r, 0, self.n).unwrap();
}
}
fn main() {
input! {
n: usize,
p: [Usize1; n],
}
let mut inv = vec![0usize; n];
// st[i][j]
// i: 0-lower value, 1-higher value
// j: 0-lower index, 1-higher index
let mut st = vec![vec![SegmentTree::new(n); 2]; 2];
let default = std::i64::MAX / 2;
for i in 0..n {
inv[p[i]] = i;
st[0][0].set(i, (p[i] + i) as i64);
st[0][1].set(i, (p[i] - i) as i64);
st[1][0].set(i, default);
st[1][1].set(i, default);
}
let mut ans = vec![0i64; n];
for i in 0..n {
st[0][0].set(inv[i], default);
st[0][1].set(inv[i], default);
let ll = st[0][0].query(inv[i], n) - i as i64 - inv[i] as i64;
let lh = st[0][1].query(0, inv[i]+1) - i as i64 + inv[i] as i64;
let hl = st[1][0].query(inv[i], n) + i as i64 - inv[i] as i64;
let hh = st[1][1].query(0, inv[i]+1) + i as i64 + inv[i] as i64;
ans[inv[i]] = min(
min(ll, lh),
min(hl, hh)
);
st[1][0].set(inv[i], (inv[i] - i) as i64);
st[1][1].set(inv[i], -((i + inv[i]) as i64));
}
println!("{}", ans.iter().map(|&x| x.to_string()).collect::<Vec<_>>().join(" "));
}
G - Partial Xor Enumeration
提出(解説動画を見て解いた)
数列$A$の空でもいい部分集合のxorをソートした場合にL番目からR番目に当たる数字を列挙する問題。
xorの下記の性質を利用する。
a \oplus b = c \\
\Rightarrow a \oplus c = b
この性質より$\{a, b\}$を$\{a, c\}$で置き換えても良いことがわかる。
次にこの置き換えを利用して集合の要素を扱いやすい数字に置換する。
具体的には集合の各要素で、あるビットが立っている数字が1種類しかないようにする。
そうすることで任意の部分集合のxorが足し算になる。
このようにするには各要素で立っているビットがある場合、他の要素で同じビットが立っているものをxor取ったものに入れ替えるとよい。
この操作は一見$O(N^2)$になっているように感じるが、同じビットは2度以上見ることがないので$O(N \log N)$で行える。
また、同じ数字や$0$はどちらも$0$やその数字自身を表すためにしか使えない上、今回は空集合で$0$が表現できるので集合から抜いても良い。そうすると集合の要素数は高々$60$になる(同じビットが立っている数字が2つ以上なく、制約で$0 \le A_i \lt 2^{60}$となっているため)
答えとなる$s_i$は、$i$の下から$bit$ビット目が立っている場合はソートされた値の小さい方から$bit-1$番目の値を足していった値になる。これは$s_i$あたり$O(\log \max A_i)$で求めることができるので全体で$O((R-L) \log (\max A_i))$になる。
use proconio::input;
fn msb(num: u64) -> u64 {
for bit in (0..60).rev() {
if 0 < (num & (1 << bit)) {
return bit;
}
}
unreachable!();
}
fn main() {
input! {
n: usize,
l: usize,
r: usize,
a: [u64; n],
}
let mut bases = vec![];
for &ai in &a {
if 0 < ai {
bases.push(ai);
}
}
let mut index = 0usize;
while index < bases.len() {
let base = bases[index];
let bit = msb(base);
let mut new_bases = vec![];
for i in 0..bases.len() {
let val = if i != index && 0 < (bases[i] & (1 << bit)) {
bases[i] ^ base
} else {
bases[i]
};
if 0 < val {
new_bases.push(val);
}
}
bases = new_bases;
index += 1;
}
bases.sort();
let mut ans = vec![];
for i in l-1..r {
let mut val = 0u64;
for bit in 0..60 {
if 0 < (i & (1 << bit)) {
val ^= bases[bit];
}
}
ans.push(val);
}
println!("{}", ans.iter().map(|&x| x.to_string()).collect::<Vec<_>>().join(" "));
}