グラフ理論

問題方針

一見難しそうに見えますが、\( 300 \) 点の問題なので解法は簡単であることが予想できます。

実現不可能な整数列頂点 \( 1 \) からの距離について

頂点 \( 1 \) からの距離が与えられるので、 ...

問題方針

解説を見ても良く分かりませんでした。

似たような問題で、CSA の良問があります。

コード#include <bits/stdc++.h>using namespace std;typedef l ...

問題方針

グラフが連結であることから、辺の数は最低でも \( N – 1\) 本必要になります。

構築できるグラフの最短距離が \( 2 \) の頂点対の個数の最大値

辺の数が \( N – 1 \) ...

問題方針行と列を分けて考える

グリッドの問題は行と列を分けて考えることができるかを最初に考えます。この問題も行と列を分けて考えることができます。\( i \) 行 \( j \) 列のマスを \( c(i, j) \) とします。ここで ...

問題方針

グラフの問題では最短距離を答える問題が多いと思いますが、今回は違います。このような問題では、重みの符号を反転させ、最短経路問題に帰着させます。これは、\( y = f(x) \) の最大化問題を \( y = -f(x) \) ...

問題方針全点間の最短距離を求めます。これはワーシャルフロイドなどで求めることができます。点 \( (i, j) \) 間の最短距離を \( d(i, j) \) とします。辺 \( a, b\) がこの最短経路に含まれる場合、辺 \( a, ...

問題方針与えられた情報から番号を当てられるか？

\( A_{X_i} + A_{Y_i} + Z_{i}\) が偶数という情報から番号を当てられることができるかを考えます。

例えば、\( A_1 + A_2 + 3 \mod ...

問題方針各マスに番号を割り振る

\( H \) 行 \( W \) 列のマスを持つグリッドにおける \( i \) 行 \( j \) 列目のマスの番号を \( i \times W + j \) とします。このようにマスの番号を割り当 ...

問題方針最小共通祖先

根から 頂点 \( i \) までの距離を \(d_i \) とすると、頂点 \( u \) と 頂点 \( v \) の距離は、\( u \) と \( v \) の最小共通祖先までの距離 \( lca(u, v ...

問題方針二部マッチング問題

基本的には、 GRL_7_A Bipartite Matchingと同じようにして解くことができます。

頂点は与えられますが、辺がどのようになっているかは自分で実装しなければいけません。赤い点のラ ...