概要 問題文 頂点数の単純無向グラフが与えられる。 また各頂点には値が割り当てられている。 このとき、頂点を含む独立集合のうち値の総和の最大値を求めよ。 制約: 解法 半分全列挙+高速ゼータ変換 (想定解法ではないらしい)。 頂点を半分に分けて、を含む…

概要 問題文 電車で目的地まで行くための最短経路を求めるというよくある感じの問題。 本の路線がありそれぞれの路線は個の駅からなる。 一つの路線について駅とそれらの間の所要時間が与えられる。 電車は両方向にあるのでどちら向きに移動しても良い。 ま…

概要 問題文 自然数列 に対して以下の操作を 回行ったときの先頭の数字を答えよ。 先頭から 番目の数字を削除する。 制約: 解法 下のように、ある数字が削除される前は先頭から何番目だったか逆から構成していくと分かりやすい。 削除前 012…k-1kk+1k+2… 削…