paizaxQiitaコラボキャンペーン対象問題全部抜く Sランク編

はじめに

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")
    };
}

村人の友好関係

私の解答

最初の所感としては最小全域木みたいなこと？と思いました。それに近しいことをやります。
人iがグループに所属しているか?を管理するflgを用意しておいて、queryに応じてこれを操作してあげます。
そして各々の友好度が配列をloopしてあげてflg[a]とflg[b]のbool値が異なるならば片方はグループに所属して片方は所属していないことになるので、その友好度が解の1候補となるわけですが、
この配列を友好度の高い順にソートしてあげれば、最初に見つかった解の1候補が最大値になるわけですから、これで求めることができます。

よって、この問題をO(MQ)で解くことができました

fn main() {
    input! {
        n: usize,
        m: usize,
        q: usize,
        abc: [(usize, usize, usize); m],
        query: [(char, usize); q]
    }
    let mut abc = abc.clone();
    abc.sort_by_key(|&e| Reverse(e.2));

    let mut flg = vec![false; n];
    for &(op, num) in query.iter() {
        let target = num - 1;
        if op == '+' {
            flg[target] = true;
        } else {
            flg[target] = false;
        }
        let mut tmp = false;
        for &(a, b, c) in abc.iter() {

            if flg[a - 1] != flg[b - 1] {
                println!("{}", c);
                tmp = true;
                break;
            }
        }
        if !tmp {
            println!("0");
        }
    }
}

島探し

私の解答

連結成分を求めるのはBFS等で探して行く手もありますがUnionFindを使うとより簡単にかけるので今回はこれを使いました。
島のなっているセルを見つけたら上下左右探索して、島があったらmergeします。

連結成分の個数に関しては島の各成分のleaderの個数を見てあげればよいです。
unionfindはac_libraryのdsuから拝借しました！

https://github.com/rust-lang-ja/ac-library-rs/blob/master/src/dsu.rs

pub struct Dsu {
    n: usize,
    parent_or_size: Vec<i32>,
}

impl Dsu {
    pub fn new(size: usize) -> Self {
        Self {
            n: size,
            parent_or_size: vec![-1; size],
        }
    }
    pub fn merge(&mut self, a: usize, b: usize) -> usize {
        assert!(a < self.n);
        assert!(b < self.n);
        let (mut x, mut y) = (self.leader(a), self.leader(b));
        if x == y {
            return x;
        }
        if -self.parent_or_size[x] < -self.parent_or_size[y] {
            std::mem::swap(&mut x, &mut y);
        }
        self.parent_or_size[x] += self.parent_or_size[y];
        self.parent_or_size[y] = x as i32;
        x
    }
    pub fn same(&mut self, a: usize, b: usize) -> bool {
        assert!(a < self.n);
        assert!(b < self.n);
        self.leader(a) == self.leader(b)
    }
    pub fn leader(&mut self, a: usize) -> usize {
        assert!(a < self.n);
        if self.parent_or_size[a] < 0 {
            return a;
        }
        self.parent_or_size[a] = self.leader(self.parent_or_size[a] as usize) as i32;
        self.parent_or_size[a] as usize
    }
    pub fn size(&mut self, a: usize) -> usize {
        assert!(a < self.n);
        let x = self.leader(a);
        -self.parent_or_size[x] as usize
    }
    pub fn groups(&mut self) -> Vec<Vec<usize>> {
        let mut leader_buf = vec![0; self.n];
        let mut group_size = vec![0; self.n];
        for i in 0..self.n {
            leader_buf[i] = self.leader(i);
            group_size[leader_buf[i]] += 1;
        }
        let mut result = vec![Vec::new(); self.n];
        for i in 0..self.n {
            result[i].reserve(group_size[i]);
        }
        for i in 0..self.n {
            result[leader_buf[i]].push(i);
        }
        result
            .into_iter()
            .filter(|x| !x.is_empty())
            .collect::<Vec<Vec<usize>>>()
    }
}



fn main() {
    input! {
        w: usize,
        h: usize,
        a: [[usize; w]; h]
    }
    let mut uf = Dsu::new(h * w);
    let didj = vec![(1, 0), (-1, 0), (0, 1), (0, -1)];
    for i in 0..h {
        for j in 0..w {
            if a[i][j] == 0 {
                continue;
            }
            for &(di, dj) in didj.iter() {
                let ni = i as isize + di;
                let nj = j as isize + dj;
                if ni < 0 || ni >= h as isize || nj < 0 || nj >= w as isize {
                    continue;
                }
                let ni = ni as usize;
                let nj = nj as usize;
                if a[ni][nj] == 0 {
                    continue;
                }
                let num1 = i * w + j;
                let num2 = ni * w + nj;
                uf.merge(num1, num2);
            }
        }
    }
    let mut set = HashSet::new();
    for i in 0..h {
        for j in 0..w {
            if a[i][j] == 0 {
                continue;
            }
            let leader = uf.leader(i * w + j);
            set.insert(leader);
        }
    }
    println!("{}", set.len());
}

mod7占い

私の解答

7で割り切れる組み合わせを考えるので7で割ったあまりで配列を7個のグループに分けます。
その後、3枚を7個のグループどこから取ってくるかを全探索します。
7で割り切れればいいので、とってきた3つのグループの和の7で割ったあまりが0になればよいですね。

同じグループから3個選ぶ時の組み合わせはnc3 = n * (n - 1) * (n - 2) / 6
2個選ぶ時はの組み合わせはnc2 = n * (n - 1) / 2
1個選ぶ時はn通りなので、それぞれO(1)で計算できます。

計算量は配列を7個のグループに分ける箇所でO(N)かかるので、O(N)でこの問題が解けました。

fn main() {
    input! {
        n: usize,
        a: [usize; n]
    }
    let mut map = HashMap::new();
    let nc3 = |n: usize| {
        if n <= 2 {
            return 0
        }
        n * (n - 1) * (n - 2) / 6
    };
    let nc2 = |n: usize| {
        if n <= 1 {
            return 0
        }
        n * (n - 1) / 2
    };
    for &num in a.iter() {
        map.entry(num % 7).and_modify(|e| *e += 1).or_insert(1usize);
    }
    let mut ans = 0;
    for i in 0..7usize {
        for j in i..7 {
            for k in j..7 {
                if (i + j + k) % 7 != 0 {
                    continue;
                }
                let mut count = HashMap::new();
                count.entry(i).and_modify(|e| *e += 1).or_insert(1);
                count.entry(j).and_modify(|e| *e += 1).or_insert(1);
                count.entry(k).and_modify(|e| *e += 1).or_insert(1usize);
                let mut tmp = 1;

                for (&m, &c) in count.iter() {
                    let &cc = map.get(&m).unwrap_or(&0);
                    if c == 3 {
                        tmp *= nc3(cc);
                    } else if c == 2 {
                        tmp *= nc2(cc);
                    } else {
                        tmp *= cc;
                    }
                }
                ans += tmp;
            }
        }
    }
    println!("{}", ans);
}

文字列収集

私の解答

query文字列、購入文字列ともに10^4くらい、
さらには文字列のlengthも100と大きくないので各文字列の先頭i文字がquery文字列に含まれているか？を調べることが可能です。
手元にあったのでさっとTrie木を使って実装してしまいましたが、
query文字列をset等で管理する方針でも正解できると思います(未検証)。

pub struct Node {
    cnt: usize,
    next: HashMap<char, Node>,
}

impl Node {
    pub fn new() -> Self {
        Self {
            cnt: 0,
            next: HashMap::new(),
        }
    }

    pub fn contain(&self, key: char) -> bool {
        self.next.contains_key(&key)
    }
}

pub struct Trie {
    root: Node,
}

impl Trie {
    pub fn new() -> Self {
        Self { root: Node::new() }
    }

    pub fn insert(&mut self, seq: &Vec<char>) {
        let mut node = &mut self.root;
        node.cnt += 1;
        for &s in seq.iter() {
            node = node.next.entry(s).or_insert_with(Node::new);
            node.cnt += 1;
        }
        node = node.next.entry(0 as char).or_insert_with(Node::new);
        node.cnt += 1;
    }

    pub fn search(&self, seq: &Vec<char>) -> bool {
        let mut node = &self.root;
        for &s in seq.iter() {
            if let Some(next) = node.next.get(&s) {
                node = next;
            } else {
                return false;
            }
        }
        node.next.contains_key(&(0 as char))
    }

}

fn main() {
    input! {
        n: usize,
        m: usize, 
        sp: [(String, usize); n],
        q: [String; m]
    }
    let mut trie = Trie::new();
    for word in q.iter() {
        let chars = word.chars().collect::<Vec<char>>();
        trie.insert(&chars);
    }
    let mut map = HashMap::new();
    for (s, p) in sp.iter() {
        let mut ans = 0;
        for i in 0..s.len() {
            let chars = &s[..=i].chars().collect::<Vec<char>>();
            if trie.search(&chars) {
                let word = chars.iter().collect::<String>();
                map.entry(word).and_modify(|e | *e += p).or_insert(*p);
            }
        }
    }
    for word in q.iter() {
        let &ans = map.get(word).unwrap_or(&0);
        println!("{}", ans);
    }
    
}

十億連勝

私の解答

この問題を見た時の最初の所感としてdpをしたくなりました。
とは言っても普通にdpテーブルを作るのは制約的に厳しいので(xが大きすぎるので)工夫する必要があります。

そこで、
dp[(j, flg)] = i + 1番目のステージまでをみたときに現在までの連勝数がj, ボーナスステージに行ける可能性があるかどうかがflgの状態になる場合の数(%MOD)
をdpすることにしましょう。
これを配列でとるのは難しいのでHashMapでとっています。

さて、遷移についてですが、
そのステージの前まででwin_count連勝して,現在のボーナスステージフラグがflgのときに、次に遷移できる場所について考えましょう。
今考えているステージの途中で負ける場合について考えれば問答無用で次のステージにおける(0, flg)に遷移できるのはまずわかります。
次に(そのステージの試合数) > x - win_countが成立しているときにはそのステージでx-wincount連勝した直後に負けるときに次のステージには(0, true)の状態で遷移できます。
x - win_count <= (そのステージの試合数)のとき、つまりはそこのステージですべて勝ってもボーナスステージ到達の連勝数に達していない時はステージ中の試合すべてに連勝して連勝数を次に引き継ぐことができます。

これらの遷移をステージ1..nまで順番に行っていくことでO(N^2)でこの問題が解けました。

fn main() {
    input! {
        n: usize,
        x: usize,
        a: [usize; n]
    }
    const MOD: usize = 1_000_000_000;
    
    let mut dp: HashMap<(usize, bool), usize> = HashMap::new();
    dp.insert((0, false), 1);

    for &num in a.iter() {
        if num == 0 {
            continue;
        }

        let mut dpp: HashMap<(usize, bool), usize> = HashMap::new();
        for (&(win_count, flg), &count) in dp.iter() {
            let target = (0, flg);
            dpp.entry(target).and_modify(|e| *e += count * (num.min(x - win_count) as usize)).or_insert(count * (num.min(x - win_count) as usize));
            if num > x - win_count {
                let target = (0, true);
                dpp.entry(target).and_modify(|e| *e+= count).or_insert(count);
            } else {
                let target = (win_count + num, flg);
                dpp.entry(target).and_modify(|e| *e += count).or_insert(count);
            }
        }
        dp = dpp;
    }
    let mut bonus = 0;

    for (&(wins, flag), &count) in dp.iter() {
        if flag || wins == x {
            bonus = (bonus + count) % MOD;
        }
    }
    println!("{}", bonus)
}

まとめ・感想

この記事ではpaizaxQiitaコラボキャンペーン対象問題のSランク相当の問題5問を解きました。
Sランク、なかなかアルゴリズムや考え方を知っていないと難しい問題が多くて楽しかったです。
他のランクの問題も記事があるので併せて読んでいただけると嬉しいです！