Atcoder ABC275 A~DをRustで解く
はじめに
競プロ記事初投稿になります。どこか間違っている箇所を見つけましたら、
お手数で申し訳ございませんがコメント等のこしていってくださると幸いです...!!
A
AtCoder 村には N 本の橋があり、i 本目（ i は 1 以上 N 以下の整数）の橋の高さは
ここで、AtCoder 村にある N 本の橋のうち、どの相異なる 2 本の橋も高さが異なります。
AtCoder 村で最も高い橋は何本目の橋か出力してください。
制約
-
1≤ N≤ 100 -
1≤{H_i}≤10^9 -
{H_i}はすべて異なる -
入力はすべて整数
解法
制約から
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
非負整数
制約
0≤A,B,C,D,E,F≤10^{18} A×B×C≥D×E×F 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 について、#であるとき座標
. であるとき座標
この平面上の正方形であって、4 頂点全てにポーンが置いてあるものの個数を求めてください。
制約
-
{S_1}, … , {S_9} #と.からなる長さ 9 の文字列
解法
一応ACとはなりましたが、かなり嘘解法っぽいと自分で思ってます...
解説の解き方の方が数倍綺麗なコードなので解説を見るのをおすすめします....
マス目は
最大81個のポーンの座標を保持し、その中から4つ選ぶ組合わせを列挙。一つずつ正方形を満たすかどうかをチェックすればよさそうです。ありえる組み合わせは最大1663740通りです。
ある座標平面上の第一象限に存在する正方形の外側にその正方形を内包する正方形がさらに存在すると仮定します。
頂点Bと頂点Aのx座標の差
線分DCと線分ABの傾きは等しいので、左上の区画についても
また、線分CBは線分ABと直行し、両者の傾きの積が-1となるので、上図の線分CDの傾きをXとすると
となります。
線分DAについても線分DCと同じことが言えそうです。
頂点ABCDについて、実際にBとCのx座標の差分が|By-Ay|,y座標の差分が|Bx-Ax|かどうかをチェック。CとD,DとAについても同様にチェックし、全て満たせば正方形としてカウントします。
一点注意として、任意の四点を組み合わせた際、必ずしも上図のABCDのような順番で選ばれているとは限りません。
ACBDの順番なら正方形の関係を満たすが、組合せの順番がABCDだった場合正方形とカウントされない恐れがあります。
なので各組み合わせに付き、頂点Aを固定した円順列だと考えることで、一つの組み合わせに付き
各組み合わせに付き6通りのチェックをするので、
通りとなります。
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(0)=1 -
任意の正整数 k に対し
f(k)=f(⌊ 2k⌋)+f(⌊ 3k⌋)
ここで、⌊A⌋
このとき、
制約
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
}
感想
a,c,dの3問が解けて入茶しました。
C問題は嘘解法臭い & d問題もメモ化再帰を張り付けるだけだったので、かなり
上振れしたパフォーマンスが出ました。
自分の実力はまだまだ茶色に届くか届かないか位だと思うので、しっかり明日からも精進頑張ろうと思います。
Discussion