2020年 6月 20日

まえがき

朝、それはつまり・・・・朝

健康管理

昨日の昼に大学で買ってきた豚丼を今食ってます。

お腹が重たい…

寝るわ (起きました ( 13:00))

何した

具体的に

今日解いた問題

ABC022 C- Blue Bird

[天才パズル,ワーシャルフロイド法,全点対間最短距離,閉路から経路]

これ面白いですね。天才パズルコンだ。僕はBFSで解こうとしました…（駄目でした)

距離が短くなった時だけまたpushする、みたいにやってたんですけど、ソレだとゴールに到着出来ない、的なことが起きてて泣いてました。

想定解法が賢すぎる。
閉路に対して、ある頂点を1個除いてやれば、辺の数が2個減った経路になる。

vector<P> graph[100100];
int main()
{
    int n, m;
    cin >> n >> m;
    vector<P> zer(0);
    vector<vector<ll>> d(n,vector<ll> (n,1e9));
    rep(i,m){
        int x, y, l;
        cin >> x >> y >> l;
        --x, --y;
        if(x==0){ //頂点0(高橋くんの家)と繋がっている点だけ別に保持しておく
            zer.push_back({y,l});
        } else {
            d[x][y] = l;
            d[y][x] = l;
        }
    }
    // ワーシャルフロイド法
    vector<ll> dist(n,1e9);
    rep(i,n){
        d[i][i] = 0; // これなくてもAC　まじ？
    }
    for (int k = 1; k < n; k++){
        for(int i = 1; i < n; i++){
            for(int j = 1; j < n; j++){
                chmin(d[i][j], d[i][k] + d[k][j]);
            }
        }
    }
    ll ans = 1e9;
    rep(i,zer.size()){ // 高橋君の家の家の隣にあって、最初に訪れる家と最後に訪れる家を全て試す
        For(j,i+1,zer.size()){
            chmin(ans,d[zer[i].first][zer[j].first] + zer[i].second + zer[j].second);
        }
    }
    cout << (ans ==  1e9? -1 : ans) << endl;
    //cout << ans << endl;
}

ABC021 C- 正直者の高橋くん

[BFS,最短経路,経路の数え上げ]

ミスったこと、[1e9+7で割った余りを出力するのを忘れていた]
- 難しかったこと BFSのときに、既にみた頂点とか、そこに行く道の最短であるよってことをどうやって書くかに悩んだ。
経路の数え上げって、道路にそこに行くまでの道順か何通りか書き込んでいくタイプのパスカルの三角形みが深いよね。

Aからの距離がKの頂点xに行く最短の道順が何通りあるか。
それは、Aからの距離がK-1であり、さらにそこから1進むとxに行ける頂点を(x0,x1,...,)とします。
すると、Aからxへの最短の道順の個数は、Aからx0までの個数、Aからx1までの個数…って感じ。

ABC020 C-壁抜け

[二分探索,幅優先探索が難しい]

あるxが達成可能かを判定しよう！ xが可能ならx-1は可能なのは分かると思う。単調性があるってやつだね〜
最初は、黒を通る回数をできるだけ少なくして、出来るだけ最短手数で行けばいいって思ったんだけど、必ずしもそうじゃないたぷ… S####
.###G
.....
みたいな時、最短で行くよりなんとなく.だけ通ってS->Gの方が良さそうなパターンもあるたぷ…

あとがき

ねむ〜い

以下は毎回記事に貼っているテンプレート

基本的に読書はTwitterで絡みのある人だけだと思いますが、僕のブログだけ見てるって人もいるかもしれないので、一応自己紹介っぽいことをしている記事を貼っておきます - 瑞々しぃにぼしの自己紹介(自己紹介の記事です)

草体にぼ日記

だらだらと

2020年6月20日　日記