AtCoder Beginner Contest 326振り返り

A - 2UP3DOWN

差分を取って出力すればいい。

use proconio::input;

fn main() {
    input! {
        x: i64,
        y: i64,
    }

    let diff = y - x;
    if diff <= 2 && diff >= -3 {
        println!("Yes");
    } else {
        println!("No");
    }
}

B - 326-like Numbers

nから919まで100の位、10の位、1の位を取り出して計算してfindすればよい。

use proconio::input;

fn main() {
    input! {
        n: usize,
    }

    if let Some(ans) = (n..=919).find(|&n| {
        let a = (n / 100) % 10;
        let b = (n / 10) % 10;
        let x = n % 10;

        a * b == x
    }) {
        println!("{}", ans);
    } else {
        panic!()
    }
}

C - Peak

ここまでしか解けなかった上に時間かかった。
累積和や二分探索の予感がしたが累積和は必要ない。二分探索すればよい。

ここで時間かかってしまってパフォーマンスを稼げず。

use proconio::input;
use superslice::Ext;

fn main() {
    input! {
        n: usize,
        m: usize,
        mut a: [usize; n],
    }

    a.sort();

    let a = a;
    let ans = (0..n)
        .map(|i| {
            let x = a[i];
            let y = x + m;
            let j = a.lower_bound(&y);
            j - i
        })
        .max()
        .unwrap();
    println!("{}", ans);
}

D - ABC Puzzle

まったく解けなかった。回答を見て写経してコメントを付ける。
Nの少なさから総当たりできそうに見えるが、単純に順列総当たりだとTLEする。
演算量の見積もりに苦しんだ。

use proconio::{input, marker::Chars};
use std::collections::VecDeque;

fn main() {
    input! {
        n: usize,
        r: Chars,
        c: Chars,
    }

    struct Elem {
        y: usize,
        x: usize,
        a: Vec<Vec<char>>,
        row: Vec<char>,
        cols: Vec<Vec<char>>,
    }

    let mut stack = VecDeque::new();
    stack.push_back(Elem {
        y: 0,
        x: 0,
        a: vec![vec!['.'; n]; n],
        row: vec![],
        cols: vec![vec![]; n],
    });
    let abc = String::from("ABC");

    while let Some(Elem { a, cols, row, x, y }) = stack.pop_back() {
        if y == n {
            // 全ての行に書き込んだあとに、列がABCとなっているか
            if (0..n).all(|j| {
                let mut copy_col = cols[j].clone();
                copy_col.sort();
                let str: String = copy_col.iter().collect();
                str == abc
            }) {
                println!("Yes");
                (0..n).for_each(|i| {
                    let str: String = a[i].iter().collect();
                    println!("{}", str);
                });
                return;
            }
        } else if x == n {
            // 行にABCが追加できていれば次に
            let mut copy_row = row.clone();
            copy_row.sort();
            let str: String = copy_row.iter().collect();
            if str == abc {
                stack.push_back(Elem {
                    y: y + 1,
                    x: 0,
                    a,
                    row: vec![],
                    cols,
                });
            }
        } else {
            // 何も書かずにxを移動
            stack.push_back(Elem {
                y,
                x: x + 1,
                a: a.clone(),
                row: row.clone(),
                cols: cols.clone(),
            });

            for ch in ['A', 'B', 'C'] {
                // 行に最初に書く文字はr[y]でなければならない
                // かつ、重複してはならない
                if (row.is_empty() && ch != r[y]) || row.contains(&ch) {
                    continue;
                }

                // 列に最初に書く文字はc[x]でなければならない
                // かつ、重複してはならない
                if (cols[x].is_empty() && ch != c[x]) || cols[x].contains(&ch) {
                    continue;
                }

                // a[y][x]にchを書いて移動
                let mut a = a.clone();
                let mut row = row.clone();
                let mut cols = cols.clone();
                a[y][x] = ch;
                row.push(ch);
                cols[x].push(ch);
                stack.push_back(Elem {
                    y,
                    x: x + 1,
                    a,
                    row,
                    cols,
                });
            }
        }
    }

    println!("No");
}

総括

やはりC問題に時間をかけたのが敗因。
たまに出るlower_boundの使い方に慣れない。