はじめに
paizaxQiitaコラボキャンペーンに参加して、対象問題をすべて解いてみました。
言語は全問題Rustで記述しました。
標準入力からの受け取りについて
Rustは標準入力の受け取りがめんどくさいと巷でよく言われています。
普段自分が遊んでいる競技プログラミングサイトではproconioという偉大なるクレートを用いることができるためここら辺はストレスフリーなのですが、
残念ながらpaizaでは導入されていなかったため、proconioのソースから必要な一部分を拝借・修正して入力できるようにしています。(最小限のものだけとってきてるので簡易版です)
入力箇所のinputマクロは以下に記載しますが、問題の本質とはズレるので解答コードからは省略しています。
#!/usr/bin/env rust-script
use std::{collections::HashMap, io::Read};
macro_rules! input {
(source = $s:expr, $($r:tt)*) => {
let mut iter = $s.split_whitespace();
input_inner!{iter, $($r)*}
};
($($r:tt)*) => {
let mut s = {
let mut s = String::new();
std::io::stdin().read_to_string(&mut s).unwrap();
s
};
let mut iter = s.split_whitespace();
input_inner!{iter, $($r)*}
};
}
macro_rules! input_inner {
($iter:expr) => {};
($iter:expr, ) => {};
($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
let $var = read_value!($iter, $t);
input_inner!{$iter $($r)*}
};
}
macro_rules! read_value {
($iter:expr, ( $($t:tt),* )) => {
( $(read_value!($iter, $t)),* )
};
($iter:expr, [ $t:tt ; $len:expr ]) => {
(0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
};
($iter:expr, chars) => {
read_value!($iter, String).chars().collect::<Vec<char>>()
};
($iter:expr, usize1) => {
read_value!($iter, usize) - 1
};
($iter:expr, $t:ty) => {
$iter.next().unwrap().parse::<$t>().expect("Parse error")
};
}
本の整理
私の解答
1番目の本、2番目の本、...と順番に整理していくことを考えましょう。
その本が今どこにあるか(配列の何番目にあるか)をfor文の中で都度求めていると、計算量オーダーはO(N^2)になります。
1 ≦ N ≦ 100,000なので、10^10くらいの計算が必要になります。
家庭用コンピュータが一秒間に行える最大計算回数は10 ^ 9回くらいといわれているので、
10^10回の計算は実用的な実行時間では終わりません。(paizaの制限時間が何秒かよくわかっていませんが、おおよその実行時間の目安とされる1~2秒には間に合わない見積もりです)
そこで、各数字が今配列の何番目に格納されているかをmap(連想配列)で持っておくことにします。
mapで管理すれば、keyに対応するgetはO(1)でできますので、何番目の本とswapすればよいかを高速に求めることができるため、O(N)でこの問題を解くことができました！
fn main() {
input! {
n: usize,
a: [usize; n]
}
let mut aa = a.clone();
let mut map = HashMap::new();
for (idx, &num) in a.iter().enumerate() {
map.insert(num, idx);
}
let mut ans = 0usize;
for idx in 0..n {
let num = aa[idx];
let &num_i = map.get(&(idx + 1)).unwrap();
if num_i == idx {
continue;
}
map.insert(idx + 1, idx);
map.insert(num, num_i);
aa.swap(idx, num_i);
ans += 1;
}
println!("{}", ans);
}
山折り谷折り
私の解答
実際にやってみました。
実際にやっていく中で一回折るとに折られた線の左側に谷折り、右側に山折りがされることがわかりました。
ということで再帰関数を実装すればこれが実現できそうです。
気になるのは計算量ですが、1 ≦ N ≦ 20とかなり小さいので比較的なんでもできそうと考えて割と何も考えずに実装しています。
fn dfs(n: usize) -> (Vec<char>, HashSet<usize>) {
let mut map = HashSet::new();
if n == 1 {
map.insert(0);
return (vec!['0'], map);
}
let (pre, idxs) = dfs(n - 1);
let mut ans = vec![];
let mut now = 0;
for i in 0..pre.len() {
if idxs.contains(&i) {
ans.push('0');
map.insert(now);
now += 1;
ans.push(pre[i]);
now += 1;
ans.push('1');
map.insert(now);
now += 1;
} else {
ans.push(pre[i]);
now += 1;
}
}
(ans, map)
}
fn main() {
input! {
n: usize
}
let (ans, _) = dfs(n);
let ans = ans.iter().collect::<String>();
println!("{}", ans);
}
ハノイの塔
私の解答
有名なハノイの塔です。
最適解はとてもシンプルな再帰で実装できることは有名だと思います。
この再帰関数の実装のなかで、どこからどこに動かしたかを記録しておいて、
それが終わったあとに一つずつ、どう動いたかをシミュレーションするような実装にしました。
fn f(n: usize, from: usize, target: usize, oths: usize, ans: &mut Vec<(usize, usize)>) {
if n > 0 {
f(n - 1, from, oths, target, ans);
ans.push((from, target));
f(n - 1, oths, target, from, ans);
}
}
fn main() {
input! {
n: usize,
k: usize
}
let mut ans = vec![];
f(n, 0, 2, 1, &mut ans);
let mut tower = vec![VecDeque::new(); 3];
for i in 0..n {
tower[0].push_back(i);
}
for i in 0..k {
let (from, to) = ans[i];
let pre = tower[from].pop_front().unwrap();
tower[to].push_front(pre);
}
for row in tower.iter() {
if row.len() == 0 {
println!("-");
continue;
}
let mut tmp = row.clone().into_iter().collect::<Vec<usize>>();
tmp.reverse();
let ans = tmp.iter().map(|e| (e + 1).to_string()).collect::<Vec<String>>().join(" ");
println!("{}", ans);
}
}
じゃんけんの手の出し方
私の解答
純粋に各回グーを出した時、チョキを出した時、パーを出した時と全探索してシミュレーションすると3 ^ nの計算量になり, n<= 1000のため、これをそのまま実装するのは無理そうです。
そこでdpをします。dpテーブルを
dp[i][j] = i番目までのじゃんけんで出した手の合計がjになるときの最大勝利数
と定義します。
このdpテーブルの要素数を考えると、iは、n試合するため、最大1000,
jは指の本数の合計がMになったときの答えを求めればよく、出した指の合計がMより大きくなったときのことは考える必要がないので、最大M <= 5000なので、
要素数は最大1000 * 5000 <= 5 * 10 ^ 6となり、このdpテーブルのフル計算であれば十分に高速に求められそうです。
あとはそれぞれの試合でそれぞれの手を出した時の勝敗をfという関数で出力するようにして勝った時はセルの中の値に+1して遷移してあげればよいですね。
よって、この問題をO(NM)でとくことができました。
fn f(c1: char, c2: char) -> bool {
if c1 == 'G' && c2 == 'C' || c1 == 'C' && c2 == 'P' || c1 == 'P' && c2 == 'G' {
return true
}
false
}
fn main() {
input! {
n: usize,
m: usize,
s: String
}
let ss = s.chars().collect::<Vec<char>>();
let mut dp = vec![vec![None; m + 1]; n + 1];
dp[0][0] = Some(0usize);
for i in 0..n {
for j in 0..m + 1 {
if dp[i][j].is_none() {
continue;
}
let now = dp[i][j].unwrap();
match dp[i + 1][j] {
Some(v) => {
let next = if f('G', ss[i]) {1} else {0};
dp[i + 1][j] = Some(max(v, now + next));
},
None => {
let next = if f('G', ss[i]) {1} else {0};
dp[i + 1][j] = Some(now + next);
}
}
if j + 2 < m + 1 {
match dp[i + 1][j + 2] {
Some(v) => {
let next = if f('C', ss[i]) {1} else {0};
dp[i + 1][j + 2] = Some(max(v, now + next));
},
None => {
let next = if f('C', ss[i]) {1} else {0};
dp[i + 1][j + 2] = Some(now + next);
}
}
}
if j + 5 < m + 1 {
match dp[i + 1][j + 5] {
Some(v) => {
let next = if f('P', ss[i]) {1} else {0};
dp[i + 1][j + 5] = Some(max(v, now + next));
},
None => {
let next = if f('P', ss[i]) {1} else {0};
dp[i + 1][j + 5] = Some(now + next);
}
}
}
}
}
let ans = dp[n][m].unwrap();
println!("{}", ans);
}
お菓子の詰め合わせ
私の解答
有名なナップザックDPというやつですね。
dp[i][j] = i個目までのお菓子のとる/とらないを決めた時に合計金額がjになるときに買える 商品数の最大値
としてdpします。
答えるのは買える商品数が最大のグループの中のお釣りの最小値を答えるのでdpテーブルの操作が終わったあと、テーブルのn行目を見て答えを算出しています。
fn main() {
input! {
n: usize,
x: usize,
xx: [usize; n]
}
let mut dp = vec![vec![None; x + 1]; n + 1];
dp[0][0] = Some(0usize);
for i in 0..n {
for j in 0..x + 1 {
if dp[i][j].is_none() {
continue;
}
let now = dp[i][j].unwrap();
let num = xx[i];
match dp[i + 1][j] {
Some(v) => {
dp[i + 1][j] = Some(max(v, now));
},
None => {
dp[i + 1][j] = Some(now);
}
}
if j + num < x + 1 {
match dp[i + 1][j + num] {
Some(v) => {
dp[i + 1][j + num] = Some(max(v, now + 1));
},
None => {
dp[i + 1][j + num] = Some(now + 1);
}
}
}
}
}
let mut count = 0;
let mut ans = usize::MAX;
for (i, num) in dp[n].iter().enumerate() {
if let Some(v) = num {
if *v > count {
count = *v;
ans = x - i;
} else if *v == count {
ans = min(ans, x - i);
}
}
}
println!("{}", ans);
}
まとめ・感想
この記事ではpaizaxQiitaコラボキャンペーン対象問題のAランク相当の問題5問を解きました。
計算量を考えないと実行時間がかかりすぎてしまう問題も出てきました！
他のランクの問題も記事があるので併せて読んでいただけると嬉しいです！