#include <bits/stdc++.h>

using namespace std;

#define rep(i,n)      for(long long(i)=0;(i)<(n);(i)++)
#define kiriage(a,b)  ((a)+(b)-1)/(b)

int main(){

    long mod = 1000000007;

    long n,a,b;
    cin >> n >> a >> b;
    a--;
    b--;
    
    vector<vector<long>> Graph(n);

    long m;
    cin >> m;

    rep(i,m){
        long x,y;
        cin >> x >> y;
        x--;
        y--;
        Graph[x].push_back(y);
        Graph[y].push_back(x);
    }

    vector<long>    path_cnt(n,0);
    vector<long>    dist(n, -1);

    queue<long> q;
    q.push(a);
    dist[a] = 0;
    path_cnt[a] = 1;

    while(q.size()){
        long cur = q.front();
        q.pop();

        if(cur == b){
            // 目的地ならそこからどこにも行かない。
            // 別ルートでBに行くかもしれないのでbreakではなくcontinueにする
            continue;
        }
        long d = dist[cur];
        long p = path_cnt[cur];

        for(auto it : Graph[cur]){

            // 未到達の場合
            if(dist[it] == -1){
                // 距離を入れて、経路数を入れる。
                // BFSなので、今が最小になっている。
                dist[it] = d + 1;
                path_cnt[it] = p % mod;
                q.push(it);
            } else if(dist[it] == d + 1){
                // 到達済の場合
                // こんかいも最短距離なら、パスの数を追加する。
                path_cnt[it] = (p + path_cnt[it]) % mod;
            }
        }
    }

    cout << path_cnt[b] << endl;


    return 0;
}

学んだこと

最短距離ならBFSで見つけれる。

感想

学んだことっていうか思い出したことだよね。一時期サボっていたタイミングで忘れてしまった。BFSはすらすらとかけたのでよかった。

2021-01-13

ABC014 -C - AtColor

勉強記録競技プログラミング

imos法みたいなことをやる。みたいなっていうかそのもの？

問題

atcoder.jp

考えたこと

全部の色の絵の具について購入してもいい人の人数を入れる箱を用意しておく。クエリで与えられる「購入してもいい色の範囲」について、その箱をプラスしていけば良さそう。

→ でもそれだと時間が足りないはず。たとえば、0 ~ 1000000の絵の具を買っていいという人が100000人いたら？

まずは先頭と終わりだけ＋１、ー１を入れておいて、購入してもいい人リストを頭からナメていけば良さそう。

解答

#include <bits/stdc++.h>

using namespace std;

#define rep(i,n)      for(long long(i)=0;(i)<(n);(i)++)
#define kiriage(a,b)  ((a)+(b)-1)/(b)

int main(){

    long s = 1000000;
    vector<long> ank(s + 1,0);
    
    long n;
    cin >> n;    
    rep(i,n){
        long lhs,rhs;
        cin >> lhs >> rhs;

        ank[lhs] += 1;
        ank[rhs + 1] -= 1;
    }

    long ans = 0;
    rep(i,s){
        ank[i + 1] = ank[i] + ank[i + 1];
    }

    long pop = 0;
    rep(i,s + 1){
        if(pop < ank[i]){
            pop = ank[i];
        }
    }

    cout << pop << endl;
    return 0;
}

感想

今だったら緑diffくらい？ひょっとしたら茶色かも。

2021-01-12

ABC018 - C - 菱型カウント

勉強記録復習するやつ競技プログラミング

ABC - C埋めを再開しました。解説ACです。

問題

atcoder.jp

考えたこと

ひし形の中心でループ回して探索してく。

行/列のループを回せば、r <= 50, c<= 50の制約はクリアできるので部分点はもらえるけれど…。ひし形の判定の計算量を落とす方法がわからなかった。

解答

ここを参考にした。 qiita.com

要は累積和っぽいことをするとよくて、左から右へ向かって、そのマスが白マス何個連続しているかを前処理で持っておくようにした。

リンク先によると、こういうデータ列が与えられたときにとりあえず累積和を取る、というのはセオリー的な技みたい。

ソースを開く

#include <bits/stdc++.h>

using namespace std;

#define rep(i,n)      for(long long(i)=0;(i)<(n);(i)++)
#define kiriage(a,b)  ((a)+(b)-1)/(b)

int main(){

    long r,c,k;
    cin >> r >> c >> k;

    vector<string> m(r);
    rep(i,r) cin >> m[i];

    vector<vector<long>> ru(r, vector<long>(c + 1, 0));

    // 'o'の連続個数の和？
    rep(i,r){
        rep(j,c){
            if(m[i][j] == 'o'){
                ru[i][j + 1] = ru[i][j] + 1;
            }
        }
    }

    long ans = 0;

    long s_r,s_c,e_r,e_c;
    s_r = k - 1;
    s_c = k - 1;

    e_r = r - k;
    e_c = c - k;

    // ひし形の中心で探索する
    for(int x = s_c; x <= e_c; x++){
        for(int y = s_r; y <= e_r; y++){

            // ひし形のてっぺんを計算する
            long t_x = x;
            long t_y = y - k + 1;

            // ひし形のてっぺんからしたまで右端を見ていく
            long i = 0; // 下方向
            long j = 0; // 右方向
            long wid = 1;
            bool flg = true;

            for(; i < 2 * k - 1; i++){
                long c_x = t_x + j;
                long c_y = t_y + i;

                if(ru[c_y][c_x + 1] < wid * 2 - 1){
                    flg = false;
                    break;
                }

                if(i < k - 1){
                    j++;
                    wid++;
                } else {
                    j--;
                    wid--;
                }
            }

            if(flg) ans++;
        }
    }

    cout << ans << endl;
    return 0;
}

学んだこと

データ列が与えられたときはとりあえず累積和ととってみる。
計算量を減らす手段として、次元を減らしましょう。（たとえば今回のだと、累積和をとって横方向の判定をO(1)にしたり。）

感想

gridは頭こんがらがる。

2021-01-11

APC001 - C - Vacant Seat

勉強記録競技プログラミング

にぶたんをスラスラ書けるようになりたい。

この問題でAtCoder Problems の BootCamp for Beginners 完埋めです～！初のインタラクティブ問題だった。

問題

atcoder.jp

考えたこと

男性と女性が隣り合っちゃいけないので、男女男女男女…と並べればいいけれど、椅子は奇数個なのでどこかで隣り合っちゃう。椅子の番号のodd/evenでの性別を帰るためには空席を挟む必要がある。

はじめに０番目の椅子に座ってる性別をチェックして、二分探索しながら検索範囲を狭めていけば、20回以内に終わらせることができる。

範囲を狭めた結果、クエリを投げる椅子の偶奇が変わっちゃうことがあるので注意した。

解答

にぶたんの基本的な書き方を整理しといたほうがいい気がした。

#include <bits/stdc++.h>

using namespace std;

#define rep(i,n)      for(long long(i)=0;(i)<(n);(i)++)
#define kiriage(a,b)  ((a)+(b)-1)/(b)

int main(){

    long n;
    cin >> n;

    string ret, top_sex;
    long lhs = 0;
    long rhs = n - 1;
    long cur = (rhs + lhs) / 2;

    // 0の位置がなにか調べる
    cout << 0 << endl;
    cin >> ret;
    if(ret == "Vacant"){
        return 0;
    }

    top_sex = ret;

    do{
        // query 送出
        cout << cur << endl;

        // ans get
        cin >> ret;

        if(ret == "Vacant"){
            return 0;
        } else {
            bool flg1 = ( cur & 0x01 ) == 0;
            bool flg2 = ret == top_sex;

            if(flg1 & flg2 || !flg1 && !flg2){
                lhs = cur;
                cur = kiriage((rhs - lhs), 2) + lhs;
            } else {
                rhs = cur - 1;
                cur = kiriage((rhs - lhs), 2) + lhs;
            }
        }
    } while(1);

    return 0;
}

学んだこと

にぶたんで検索範囲は左端は範囲外にしとくといいらしい。←もう少し勉強しましょう。

感想

BootCampの最終問題だったので緊張しました。

終わってみるとあっけないような気持ち。これからはCのやってないの解いたり、Recommend解いたりしていくかな。

2021-01-11

エンベデッドシステムスペシャリストになった話

自己紹介勉強記録

この間の2020年秋期エンベデッド試験に無事合格しました。これで僕も晴れてエンベデッドシステムスペシャリストです。高度持ちとしてドヤっていけます。今回はエンベデッド試験とかについてかきます。

実はQiitaにすでに記事を書いたんですが、もうちょっと個人的な話とか、せっかくのネタだし自分のブログにも書くかーって感じです。

せっかくとったしどんどんアピールしていかないとね！

エンベデッドシステムスペシャリストとは
経緯とか
感想
勉強方法
- 午前対策
- 午後対策
おわりに　次何勉強しよう

エンベデッドシステムスペシャリストとは

これについては、IPAの説明に任せたほうがいいので、詳細は書きません。

エンベデッドシステムスペシャリスト試験 - IPA

ざっくりいうと、最近流行りのIoTとか、機械を制御するマイコンなど組み込み系システムを扱うエンジニア向けの資格です。

経緯とか

受けた動機

僕の会社だと、学卒だとだいたい8年目？くらいに主査への昇進試験があります。入社5年目までは自動昇格して、その後3年経つと昇進試験を受けられます。

エンベデッドに限らないんですが、高度を持ってるとこの3年の下積？みたいなのが一年早めることができるので今回取ることにしました。高度ならなんでも良かったんですが、会社で特に推奨してたので、エンベデッドを受験しました。

もともと持っていた情報処理資格

入社した年に基本と応用を取っています。なんで取れたのか…今受けても取れない気がします。基本と応用は分野が広すぎて、なんならエンベデッドよりも難しかった印象があります。

勉強期間

本格的に勉強を始めたのは９月中頃です。試験が10月中旬にあるので大体一ヶ月くらいでしょうか。また8月頭くらいから、午前2の過去問はスマホのアプリでちょくちょく解いていました。 9月に入ってからは、参考書を買ってしっかり読み込んだり問題を解いたりしていきました。

感想

試験当日

事前の過去問演習では、概ね7割くらい解けていたのでそんなに緊張しなかったです。やはりコロナ対策はしっかりされてましたね。昼食はCoCo壱にしました。注文なかなか出てこなくて午後問題に間に合うか心配でした。昼飯はちゃんとカツカレーにしました(^-^)v

問題はそんなに詰まることもなく、午後も回答欄全部埋めることができました。最後までいましたけど、安心して試験終われました。

答え合わせ

帰り際に電車の中で午前問題の答え合わせをしました。解答速報を見てたのですが、そのサイトが間違えだらけで午前で不合格になったと勘違いしたまま帰宅しました。家に帰ってから問題文で検索かけて、１つずつ照らし合わせたら、帰りに見た解答速報間違いだらけだった。恨む。 午前がダメなら帰りたい〜とかで昼休みに答え合わせをする人がいるとは思いますが、解答速報はあくまで速報で、間違ってる場合もあるので気をつけてください。

どうしても答え合わせをしたい場合は、問題文を１つずつ検索して、過去問と答えを一個ずつ引っ張ってくるのがいいと思います。

合格

午後問題は記述式なので、さじ加減で合格にも不合格にもできそうなので答え合わせはしませんでした。意図的に忘れていました。あからさまに１００点とかじゃないと、あらを探して最低ラインを見つけようとしそうなので……。

そんなこんなしてたら、12月25日に会社の研修課みたいなところから合格おめでとうメールが来て知りました。会社経由で申し込んだので１月下旬辺りに上長あてに合格証が届くらしいです。やった！

今後の情報処理ライフ

春期にネットワークスペシャリストが受けれるみたいなんで受けるか迷っています。ネットワーク周りの技術は全然知らないですし、業務にも役立てそうなんで。エンベデッド受かったばかりで午前Ⅰの免除特権があるのである内に受けてみようかな、と。でもやっぱり知らなすぎるから受けないかもしれない。

勉強方法

このやり方はどこかで見たわけでもなく自分一人しかやってないですし受かってないので再現性は低いです。

でもこれくらい載せとかないと完全にただの日記なのでかけるだけ思い出してみます。

午前対策

１にも２にも過去問です。過去問解いてるだけで受かると言っても過言ではありません。ぼくは応用とっていたこともあったので、いきなり過去問を解いていました。

当然、最初のうちは全然わかりませんが、問題→選択肢→解説と読むだけでも力になります。

大抵の解説は４択それぞれの回答に対して、あっているか、間違っているか、それぞれの理由が書いてあるので全部読むようにします。これで１問解くだけで４単語覚えることができます。選択肢が説明の問題もありますが、間違っている選択肢は問題の主題とは別の単語を説明していることが多いです。正解以外の選択肢まで読むことをおすすめします。

午後対策

正直コレはあまり語ることがないのですが……。

やっぱり過去問を何年か解くといいと思います。エンベデッドは文章題で知識を問われることはあまりないので、覚えておくことはそんなに多くありません。ただ物理的な法則なんかは覚えておいたほうがいいです。（デューティ比覚えなきゃ…とか考えてたのを思い出しました）。

問題を解くときはタスク間のメッセージを聞いてくることが多いので、注意して文章を読んでおくといいです。タスク表にある「○○へ～～を通知する」だとか「○○メッセージを送る」だとか「□□タスクへ依頼する」なんかを見つけたら要チェック。また、タスク図でタスク同士が結ばれている箇所は何らかのメッセージや情報のやり取りをしているので、タスク表から関連を読み取るといいです。

おわりに　次何勉強しよう

何勉強しましょうかね……。感想のところで書いたようにネスペでもとるか、自分の好きなことをやるか悩みます。でも高度２つ持っているとかすごい人感があるので一回目指してみてもいいかもしれない。

環境

解決方法

結果

問題

考えたこと

解答

学んだこと

感想

問題

考えたこと

解答

感想

問題

考えたこと

解答

学んだこと

感想

問題

考えたこと

解答

学んだこと

感想

エンベデッドシステムスペシャリストとは

経緯とか

受けた動機

もともと持っていた情報処理資格

勉強期間

感想

試験当日

答え合わせ

合格

今後の情報処理ライフ

勉強方法

午前対策

午後対策

おわりに 次何勉強しよう

おわりに　次何勉強しよう