問題 問題概要 木の上での最短経路(根からの距離、葉からの距離)を求める問題。 解法 根から葉、葉から根へ向けて、bfsをすればいい。その時に注意することはbfsで次に進む方向を決めるときに、来た方向に戻ってしまうと、正確な値が求まらないので、queueの…

問題 問題概要 バスが通るのを記録する。それぞれの系統に対して、最終１つ前のバスと最終のバスはほかのバスとその他のバスをそれぞれ異なるように記録している。その記録が条件に沿ったものかを判定する問題。 解法 それぞれの系統のバスは、WGRの順に出て…

問題 問題概要 門松列になる組み合わせを求める問題。 解法 この問題の注意点は並び順が違っても、同じ竹の組み合わせなら同じとカウントするという点である。よって、門松列になる竹の組み合わせが何通りあるかを求めるには、３本の竹が異なるようにとるこ…

問題 問題概要 条件を満たす最大の値を求める問題。 解法 求める棒の長さは条件を満たす最大の値であり、その値より棒の長さを短くしても条件を満たすが、それより大きくすると条件を満たさなくなる。よって、このような場合は、二分探索をして効率よく求め…

問題 問題概要 期待値問題。 解法 期待値の線形性を使うと簡単にできる問題。 ミス 数学ガール読みます。 コード #include <iostream> #include <cstdio> #include <set> #include <algorithm> using namespace std; typedef long long ll; #define rep(i,n) for(int i=0;i<(n);i++) const int </algorithm></set></cstdio></iostream>…

問題 問題概要 条件を満たす最長の文字列の長さを求める問題。 解法 白のブロックをいじることはないので、赤と青のブロックさえいじればいい。ブロックのいじりかたも、そのブロックを使用するか、しないかだけであり、いじらなければならないブロックの総…