🥶

Atcoder ABC275 A~DをRustで解く

2022/10/30に公開約5,000字

はじめに

競プロ記事初投稿になります。どこか間違っている箇所を見つけましたら、
お手数で申し訳ございませんがコメント等のこしていってくださると幸いです...!!

A

AtCoder 村には N 本の橋があり、i 本目( i は 1 以上 N 以下の整数)の橋の高さは
{H_i}です。

ここで、AtCoder 村にある N 本の橋のうち、どの相異なる 2 本の橋も高さが異なります。

AtCoder 村で最も高い橋は何本目の橋か出力してください。

制約

  • 1≤ N≤ 100

  • 1≤{H_i}≤10^9

  • {H_i}はすべて異なる

  • 入力はすべて整数

解法

制約から1≤ N≤ 100なので、愚直にfor文で一つずつ高さを比較していけばよさそうです。

use proconio::{fastout, input};
#[fastout]
pub fn main() {
    input! {
    n:usize,
    h:[usize;n],
        }
    let mut highest = 0;
    for i in 0..n {
        if h[highest] < h[i] {
            highest = i;
        }
    }
    println!("{}", highest + 1);
}

B

非負整数 A,B,C,D,E,F があり、A×B×C ≥ D×E×F をみたしています。

(A×B×C)−(D×E×F) の値を 998244353 で割った余りを求めてください。

制約

  • 0≤A,B,C,D,E,F≤10^{18}
  • A×B×C≥D×E×F
  • A,B,C,D,E,F は整数

解法

以下の分配則により、予め余りをとってから計算してもよいことが分かります。

(a + b)\bmod n =( (a\bmod n) + (b\bmod n) )\bmod n
ab\bmod n =( (a\bmod n) * (b\bmod n) )\bmod n

制約より、A×B×C≥D×E×F ではあるものの余りについては上記の関係性を満たさないため、998244353を足してから差分を取ります。

use proconio::{fastout, input};
#[fastout]
pub fn main() {
    input! {
    mut  a:u128,
    mut  b:u128,
    mut  c:u128,
    mut  d:u128,
    mut  e:u128,
    mut  f:u128,
         }
    let m = 998244353;
    a %= m;
    b %= m;
    c %= m;
    d %= m;
    e %= m;
    f %= m;
    let abc = (a * b) % m * c % m;
    let def = (d * e) % m * f % m;
    println!("{}", (abc + m - def) % m);
}

C

二次元平面があります。1 以上 9 以下の整数 r,c について、{S_r}の c 番目の文字が#であるとき座標 (r,c) にポーンが置いてあり、
{S_r}の c 番目の文字が . であるとき座標 (r,c) に何も置かれていません。

この平面上の正方形であって、4 頂点全てにポーンが置いてあるものの個数を求めてください。

制約

  • {S_1}, … , {S_9}はそれぞれ #. からなる長さ 9 の文字列

解法

一応ACとはなりましたが、かなり嘘解法っぽいと自分で思ってます...
解説の解き方の方が数倍綺麗なコードなので解説を見るのをおすすめします....

マス目は9 * 9 = 81マスしかないので、全てのマスにポーンが置いてあると仮定しても全探索が出来そう。

最大81個のポーンの座標を保持し、その中から4つ選ぶ組合わせを列挙。一つずつ正方形を満たすかどうかをチェックすればよさそうです。ありえる組み合わせは最大1663740通りです。

{}_{81} \mathrm{C}_4 = \frac{81*80*79*78}{4!} = 1663740 \fallingdotseq 2 * 10^6

ある座標平面上の第一象限に存在する正方形の外側にその正方形を内包する正方形がさらに存在すると仮定します。

頂点Bと頂点Aのx座標の差B_x - A_x、y座標の差B_y-A_yより線分ABの傾きが分かります。

線分DCと線分ABの傾きは等しいので、左上の区画についてもB_y-A_y,B_x-A_xであると言えそうです。

また、線分CBは線分ABと直行し、両者の傾きの積が-1となるので、上図の線分CDの傾きをXとすると

\frac{B_y-A_y}{B_x-A_x}* X = -1
X = -\frac{B_x-A_x}{B_y-A_y}

となります。

線分DAについても線分DCと同じことが言えそうです。

頂点ABCDについて、実際にBとCのx座標の差分が|By-Ay|,y座標の差分が|Bx-Ax|かどうかをチェック。CとD,DとAについても同様にチェックし、全て満たせば正方形としてカウントします。

一点注意として、任意の四点を組み合わせた際、必ずしも上図のABCDのような順番で選ばれているとは限りません。
ACBDの順番なら正方形の関係を満たすが、組合せの順番がABCDだった場合正方形とカウントされない恐れがあります。

なので各組み合わせに付き、頂点Aを固定した円順列だと考えることで、一つの組み合わせに付き3! = 6通りの並び方をチェックします。
各組み合わせに付き6通りのチェックをするので、

2.0 * 10^6 * 6 = 1.2 * 10^7

通りとなります。

use itertools::Itertools;
use proconio::{fastout, input, marker::Chars};
#[fastout]
pub fn main() {
    input! {
    s:[Chars;9]
        }
    let mut coor = vec![];
    for i in 0..9 {
        for j in 0..9 {
            let a = s[i][j];
            if a == '.' {
                continue;
            }
            coor.push((i as i64, j as i64));
        }
    }
    let comb: Vec<_> = coor.iter().combinations(4).collect();
    let mut res = 0;
    for i in 0..comb.len() {
        let (a, b, c, d) = (comb[i][0], comb[i][1], comb[i][2], comb[i][3]);
        // 円順列6通り
        if check(a, b, c, d)
            || check(a, b, d, c)
            || check(a, c, b, d)
            || check(a, c, d, b)
            || check(a, d, b, c)
            || check(a, d, c, b)
        {
            res += 1;
        }
    }
    println!("{}", res);
}
 
fn check(a: &(i64, i64), b: &(i64, i64), c: &(i64, i64), d: &(i64, i64)) -> bool {
    let dx = (a.0 - b.0).abs();
    let dy = (a.1 - b.1).abs();
    if b.0 + dy == c.0
        && b.1 + dx == c.1
        && c.0 - dx == d.0
        && c.1 + dy == d.1
        && d.0 - dy == a.0
        && d.1 - dx == a.1
    {
        return true;
    }
    false
}

D

非負整数 x に対し定義される関数 f(x) は以下の条件を満たします。

  • f(0)=1

  • 任意の正整数 k に対し
    f(k)=f(⌊ 2k​⌋)+f(⌊ 3k​⌋)
    ここで、⌊A⌋ は A の小数点以下を切り捨てた値を指します。

このとき、 f(N) を求めてください。

制約

  • N は 0≤N≤10^{18}を満たす整数

解法

C問題がとても難しかったのでD問題は恐る恐るページを開きました。
メモ化再帰で解けそうです。

use std::collections::HashMap;
 
use proconio::{fastout, input};
#[fastout]
pub fn main() {
    input! {n:u64}
    let mut memo = HashMap::new();
    println!("{}", f(n, &mut memo));
}
 
fn f(n: u64, memo: &mut HashMap<u64, u64>) -> u64 {
    if n == 0 {
        return 1;
    }
    if memo.contains_key(&n) {
        return memo[&n];
    }
    let ans = f(n / 2, memo) + f(n / 3, memo);
    memo.insert(n, ans);
    ans
}

感想

https://atcoder.jp/users/k_xor_yama/history/share/abc275

a,c,dの3問が解けて入茶しました。
C問題は嘘解法臭い & d問題もメモ化再帰を張り付けるだけだったので、かなり
上振れしたパフォーマンスが出ました。

自分の実力はまだまだ茶色に届くか届かないか位だと思うので、しっかり明日からも精進頑張ろうと思います。

Discussion

ログインするとコメントできます