AtCoder Beginner Contest 168 ふりかえり - YU2TA7KA's BLOG ～take one step at a time～

はじめに
A問題　A - ∴ (Therefore)
B問題　　B - ... (Triple Dots)
C問題　　C - : (Colon)
D問題　　D - .. (Double Dots)
E問題　　E - ∙ (Bullet)
おわりに

はじめに

AtCoder Beginner Contest 168に参加しました。D問題まで解けて4完、これを継続していきたいです。パフォーマンスも自己ベスト更新しました。

yu2ta7kaさんのAtCoder Beginner Contest 168での成績：2627位
パフォーマンス：1046相当
レーティング：434→521 (+87) :)
Highestを更新しました！
#AtCoder https://atcoder.jp/users/yu2ta7ka/history/share/abc168?lang=ja

いろいろな解き方がある数学問題。過去問の時計盤*1からさらに進めた問題と私は捉えた。そこから余弦定理を用いれば良いという考えは合っていたが、度数法と弧度法（ラジアン）の変換を忘れていて実装に戸惑い。数学理解が浅い。Pythonでここらへんの話題を検索したら運良く良い感じの情報を得られたので、それを利用してAC。30分くらい時間を無駄にした。。。一方でRustだけでなくPythonでも競プロ練習しておいて良かったとも。
余弦定理を使用しなくても解けるようで数学復習としてリトライをしておきたい。

use std::io::*;
use std::str::FromStr;
use std::f64;

//https://qiita.com/tubo28/items/e6076e9040da57368845
fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

fn main() {
    let a:f64 = read();
    let b:f64 = read();
    let mut n: f64 = read(); //時
    let m: f64 = read(); //分

    if n > 12.0 {
        n -= 12.0;
    }

    let n_angle = n * 30.0 + m * 0.5;
    let m_angle = m * 6.0;

    let mut angle = 0.0;
    if n_angle < m_angle {
        if (m_angle - n_angle) < 360.0 - (m_angle - n_angle){
            angle = m_angle - n_angle;
        }else{
            angle = 360.0 - (m_angle - n_angle);
        }
    }else{
        if (n_angle - m_angle) < 360.0 - (n_angle - m_angle){
            angle = n_angle - m_angle;
        }else{
            angle = 360.0 - (n_angle - m_angle);
        }
    }

    let ans = a*a + b*b - 2.0*a*b*((angle.to_radians()).cos());
    println!("{:.012}",ans.sqrt());
}

D問題　　D - .. (Double Dots)

BFSで解ける問題。以前実装したBFSコードをコピペしたらACしてしまった、というのが素直な感想。近いうちにまたBFSを触っておかないと身にならない。今回は運が良かった。Noの場合も考慮と問題文にはあったが、実は全部Yesという問題。

use std::collections::VecDeque;
use std::io::*;
use std::str::FromStr;

//https://qiita.com/tubo28/items/e6076e9040da57368845
fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();

    token.parse().ok().expect("failed to parse token")
}

fn main() {
    type Graph = Vec<Vec<usize>>;
    let n: usize = read();
    let m: usize = read();
    let mut G: Graph = vec![Vec::new(); n];
    for _i in 0..m {
        let a: usize = read();
        let b: usize = read();
        G[a-1].push(b-1);
        G[b-1].push(a-1);
    }
    let mut dist = vec![-1; n];
    let mut mark = vec![-1; n];
    let mut queue: VecDeque<usize> = VecDeque::new();

    for i in 0..n {
        if dist[i] != -1 {
            continue;
        }
        dist[i] = 0;
        queue.push_back(i);
        while !queue.is_empty() {
            let v = queue.pop_front().unwrap();
            for nv in G[v].iter() {
                if dist[*nv] == -1 {
                    dist[*nv] = dist[v] + 1;
                    queue.push_back(*nv);
                    mark[*nv] = v as i32;
                }
            }
        }
    }
    println!("Yes");
    for i in 1..mark.len(){
        println!("{}",mark[i]+1);
    }
}