競プロ典型90問をRustで解いていこう（簡易グラフ）10日目

2022-04-26

はじめに

最近（でもなくずっとですが…）「ワイ、英語できなさすぎじゃね？」って事が多くてですね… 中高年の頃に修めておけば良かったもの後悔しながらも、再開し始めました。やってきた人からするとかなり、周回遅れ感はあります。再開し始めたものの、ずっと嫌だったものがそんなにすんなり気持ちを込めてやれるかは甚だ疑問ですが…手頃なところから触れていきたい。

NHKを見てると、大西泰斗の英会話定番レシピという番組がやっており、10分番組なのものあって録画して、朝早起きしたときとか、昼休みに流しながら見てます。

テキストとかも買ってやったほうが良いんだろうなと思いながらノートにまとめながら見てます。テキストは本屋で見かけたら買おうと思います。

TOEICが400前後の人はまず基礎文法が疎かになっているようなので、そこから始めるとい良いという先人のアドバイス通りやりましょう。

そんなモチベーションで続けならが先日、TOEIC受けてきました。いつもは、1から4で好きな数字を選んでいいよって言われて「これ！」って選ぶようなキッズでしたが、「文法的にお前はオカシイだろ。単語の意味は正直わからんが俺は正しいはずだ」と選べた気がします。成長を感じました。（あってるかは今後、点数で教えてくれることでしょう。450ぐらいはあって欲しいなぁせめて…）

ゴミカス野郎が何いってんだとは思いますが、私は今まで文法を疎かにしてきたことに気がついたのです。これはかなり大きい収穫ですよ。言わばビデオゲームでルールを知らないままキャラを動かして、勝てない！って言うてるようなものだったわけです。

まずはゲームのルール（文法）を覚えて、立ち回り（単語）と共にキャラの動かし方（イディオム、単語の変形）を反復練習するのが良いと考えたわけです。必殺技（TOEICの解き方）とか飛び道具（リスニング）は後で良いんじゃないかと。ストリートファイターとかでも、飛び道具の使い方は結構重要らしいので、リスニングはいりますかね。

あとは、ワイ駄目だと感じたのがPart3,Part4,Part7でした。わからないことだらけの中でも輝いて見えましたね。

当面の方針としては、今まで勉強してこなかった英文法を固めるところ。並行して、英単語をDUO3.0使って、復習用のリスニングＣＤを使って耳と語彙を増やす。

英語ができないのはやってないだけ。なんならやるだけ。

できなかったから現状なわけですが、やりましょう…やってみましょう……。

本日の問題

まぁ、英語はそれとして、中途半端が一番駄目ということで競技プログラミングの続きやります。

競プロ典型90問をRustで解いていこう（準備）0日目

今日は上の記事から10問目を解いていきます。

078 - Easy Graph Problem（★2）を解いていこうと思います。

情報系の大学に通っていたら実装課題として出たり、実装せずとも理論だけは少なくとも触れることになるであろうグラフの初歩の初歩を実装する問題です。私の業務的には使うことが殆どないため、書いたことはあるけど記憶は遥か彼方…そんなグラフですね。

078 - Easy Graph Problem（★2）

Node数がN個で、それぞれがM本の辺でつながる単純無向グラフが与えられる。その中で、自分よりも小さい値のNodeがつながっているNodeはどれか列挙する問題です。

イメージこんな感じですかね。

この例で言えば、自分よりも小さな値のNodeに繋がる3,4,5,6を出力するのが正解となります。

PaizaのAランク問題でこの辺が出てくるようなので、グラフ系の問題は息を吐くように解けるようにしたいなと思っています。

ちなみに図は、Mermaid.jsを使って書きましたが簡単に書けるのいいですね。

```mermaid
flowchart LR
id1((1))
id2((2))
id3((3))
id4((4))
id5((5))
id6((6))

id1 --- id2;
id1 --- id3;
id2 --- id5;
id3 --- id4;
id2 --- id6;
id1 --- id6;

Rustでの回答例

問題としては、繋がる先のノードリストがあれば解けるためそちらを用意しました。最初のforループで、繋がる元と繋がる先のノードに「繋がってるよ」ということでidを詰め込みます。

2つ目のループは、各ノードごとに詰め込んだリストを取り出して、3つ目のループで、自身のノードと繋がる先の値を比較します。もし自分より小さい値のノードが1つだけの場合は、Ansに1つずつ加算して回答を求めます。

use proconio::input;
use proconio::marker::Usize1;

fn main() {
    input! {
        n : usize,
        m : usize,
        ab : [(Usize1, Usize1);m]
    }
    let mut graph = vec![vec![]; n];
    for (a, b) in ab {
        graph[a].push(b);
        graph[b].push(a);
    }

    let mut ans = 0;
    for i in 0..n {
        let it = graph[i].iter();
        let mut tmp = 0;
        for j in it {
            if j < &i {
                tmp += 1;
            }
        }
        if tmp == 1 {
            ans += 1;
        }
    }
    println!("{}", ans);
}