ABC387

Cを見た瞬間に諦めてDに行くというトンデモ戦法が刺さり、なんと3完で水perf..(え)。まぁレート的には微負けなので反省して次です。

A - Happy New Year 2025

タイトルから問題文の落差にびっくりしますが、 pow(A+B, 2) で良いです。modを取らないので (A+B)**2 のほうが記述量が少なくて嬉しいという話もありますが先に思いついた方を使いましょう。
提出

A, B= map(int, input().split())
print(pow(A+B, 2))

B - 9x9 Sum

\(9\times9\) に収まるので、言われたとおりに2重ループで全探索で良いでしょう。
提出

use proconio::input;
fn main() {
    input!{
        x: u64,
    }
    let mut ans = 0;
    for i in 1..=9 {
        for j in 1..=9 {
            if i * j != x {
                ans += i*j;
            }
        }
    }
    println!("{ans}");
}

\(k\) を登場回数として、 \(2025-kx\) を計算するような方針はABC-Dぐらいでありそうでちょっと面白いなぁと思いました。でも \(O(N^2)\) 方針を落とす問題にするのはちょっと難しそう？

D - Snaky Walk

やりたいことは重み1のグラフ上の最短距離なのでBFSですが、example1を見ると不思議な図が書いてあります。何回数えても最短距離は5にしか見えませんが？
縦横の動作を連続で行えない、なるほど。縦横の動作を連続で行えないというのを言い換えると、次に移動できる方向が縦か横のいずれかに決まるということです。「次に横に移動できるマス \((i, j)\) 」「次に縦に移動できるマス \((i, j)\) 」と頂点を倍加させてBFSをすることによってこの問題が解けます。
提出

#[allow(unused_imports)]
use proconio::{input, marker::Chars};

pub static INF: u64 = 1e18 as u64;
pub static DI: &[usize] = &[0, !0, 0, 1, !0, 1, !0, 1];
pub static DJ: &[usize] = &[!0, 0, 1, 0, !0, !0, 1, 1];

fn main() {
    input!{
        h: usize,
        w: usize,
        s: [Chars; h],
    }

    let mut start=(0, 0);
    let mut goal = (0, 0);
    for i in 0..h {
        for j in 0..w {
            if s[i][j] == 'S' {
                start = (i, j);
            }
            if s[i][j] == 'G' {
                goal = (i, j);
            }
        }
    }

    let mut seen = vec![vec![vec![INF; w]; h]; 2];
    seen[0][start.0][start.1] = 0;
    seen[1][start.0][start.1] = 0;

    let mut que = VecDeque::new();
    que.push_back((0, start));
    que.push_back((1, start));

    while let Some((i, (pi, pj))) = que.pop_front() {
        let nxt= 1 - i;
        for r in 0..4 {
            if r % 2 == i {
                continue;
            }

            let ni = pi.wrapping_add(DI[r]);
            let nj = pj.wrapping_add(DJ[r]);
            if ni < h && nj < w && seen[nxt][ni][nj] == INF && s[ni][nj] != '#' {
                seen[nxt][ni][nj] = seen[i][pi][pj] + 1;
                que.push_back((nxt, (ni, nj)));
            }
        }
    }

    let ans = seen[0][goal.0][goal.1].min(seen[1][goal.0][goal.1]);
    println!("{}", if ans == INF { -1 } else { ans as i64 });
}

スタートとゴールはグリッド上に置かずに入力で与えてほしいなぁという気持ち。snippetにしても良いな。

C - Snake Numbers(upsolve)

ABC-Cなのにどう見ても桁dpです。困りました。ほんとうに？を繰り返していたらコンテストが終わってしまいました。悲しい。
dpの中でも群を抜いて桁dpが苦手という話もあります。通常のよくあるdpだと愚直な、そのままやるとTLEする解を改善する手法を取ることが多く、このフローに持っていけるとかなり高い確度でACを取れるという自信があるのですが、これは愚直なdpが見えるという前提です。桁dpの場合だと何を状態に持ってどう遷移するのかというのが分からなくなり壊れてしまいがちで、大変苦手としています。
それはそうとして解法はというと、 dp[i][j][k] := i桁目まで見たときに先頭の値がjである個数(kは0のときN未満になる可能性があるというフラグ) として、j=0とk=1に気をつけながら遷移を書くことでACできます。桁dpなので \(i\) , \(k\) は状態として持ちたくて、どの桁においても先頭の値を知りたいのでそれを \(j\) として状態にする、という形でdpテーブルを決めると良いでしょう。
提出

use itertools::Itertools;
use proconio::input;

fn to_i(c: char) -> usize {
    c as usize - '0' as usize
}

fn count(x: u64) -> u64 {
    // x未満で条件を満たすものの個数
    // dp[i][j][k] := i桁目まで見たときに、頭の桁がjであり、
    // if k = 1 then x未満であることが確定している
    // else x未満になる可能性がある
    let xs = x.to_string().chars().collect_vec();
    let len = x.to_string().len();
    let mut dp = vec![vec![vec![0u64; 2]; 10]; len+1];

    dp[0][0][0] = 1;

    for i in 0..len {
        if i != len-1 {
            // j = 0 && k = 0
            for nj in 0..to_i(xs[i]) {
                dp[i+1][nj][1] += dp[i][0][0];
            } 
            dp[i+1][to_i(xs[i])][0] += dp[i][0][0];

            // j = 0 && k = 1
            for nj in 0..=9 {
                dp[i+1][nj][1] += dp[i][0][1];
            }
        }

        // k = 0
        for j in 1..=9 {
            if to_i(xs[i]) < j {
                dp[i+1][j][0] += dp[i][j][0];
            }

            for _ in 0..to_i(xs[i]).min(j) {
                dp[i+1][j][1] += dp[i][j][0];
            }
        }

        // k = 1
        for j in 1..=9 {
            let val = dp[i][j][1] * j as u64;
            dp[i+1][j][1] += val; 
        }
    }
    dp[len].iter().flatten().sum()
}

fn main() {
    input!{
        l: u64,
        r: u64,
    }
    println!("{}", count(r) - count(l-1));
}

E - Digit Sum Divisible 2(upsolve)

とても面白いと思いますが本当にABC-Eですか？ARC-Bではなく？
考え方として「 \(N\) が十分大きいときは双子の良い整数が存在しないことがありえない、なぜなら全てについて条件を満たさない場合は全てについて条件を満たさないことを確認しないといけないがそんなことは不可能なので」というのを聞いたときとてもかしこいなぁ、なるほどと思いました。人類は天才です。
\(N\) が小さいときは全探索で良く、大きいときは8の倍数(下3桁が8で割り切れる)と9の倍数(桁和が9の倍数である)を作るのが簡単で良いと思います。真心込めた条件分岐を書いて祈ると通りますが、真心を込めないと落ちる場合があります(3敗)。
提出

use std::iter::repeat;
use itertools::Itertools;
use proconio::input;

fn digit_sum(s: &String) -> u32 {
    s.chars().map(|c| c as u32 - '0' as u32).sum()
}

fn small_n(n: &String) {
    let n = n.parse::<usize>().unwrap();
    for a in n..2*n {
        if a % digit_sum(&a.to_string()) as usize == 0 && (a+1) % digit_sum(&(a+1).to_string()) as usize == 0{
            println!("{}", a);
            return;
        }
    }
    println!("-1");
}

fn big_n(n: &String) {
    let d = n.chars().next().unwrap();
    let length = n.len();
    let z = repeat(0).take(length-4).join("");
    let ans = match d {
        '1' => {
            let d2 = n.chars().nth(1).unwrap();
            let f = format!("{}{}", d, d2).parse::<u64>().unwrap() + 1;
            let z = repeat(0).take(length-5).join("");

            match f {
                11 => format!("11{}240", z),
                12 => format!("12{}104", z),
                13 => format!("13{}040", z),
                14 => format!("14{}120", z),
                15 => format!("15{}200", z),
                _ => format!("20{}024", z),
            }
        },
        '2' => format!("3{}104", z),
        '3' => format!("4{}040", z),
        '4' => format!("5{}120", z),
        '5' => format!("6{}200", z),
        '6' | '7' | '8' | '9' => format!("11{}240", z),
        _ => unreachable!()
    };
    println!("{}", ans);
}

fn main() {
    input!{
        n: String,
    }
    if n.len() < 7 {
        small_n(&n);
    } else {
        big_n(&n);
    }
}