hitoare日記

たまに書きます

F - Tree and Constraints (AtCoder Beginner Contest 152)

問題リンク atcoder.jp 問題概要 \(N\)頂点の木が与えられる。\(N-1\)本の辺を白または黒に塗り分ける方法であって、次の\(M\)個の条件全てを満たすものはいくつあるか。 条件\(i(1≦i≦M) \) : \(u_i\)と\(v_i\)を結ぶパスの間に、黒い辺が少なくとも1つ存在…

E - Bichromization (キーエンス プログラミング コンテスト 2020)

問題リンク atcoder.jp 問題概要 N頂点M辺の無向グラフが与えられる。各頂点を白または黒に塗り分け、更に辺に重みを割り当てる方法であって次の条件を満たすものは存在するか。存在すれば1つ構築せよ。 \(1\leqq i\leqq N\)にし、点iから色の異なる点に移動…

E - Change a Little Bit (AtCoder Beginner Contest 150)

公式解説と解法が違っていたので。 問題リンク atcoder.jp 問題概要 長いので省略 解法 Cが小さいものからとる方が良いので、まずCを小さい順にソートする。 動的計画法によって答えを求める。 dp[i] = (i文字目まで見た時のfの総和)とする。 1文字の文字列…

アルゴリズム実技検定(PAST)受験記+問題解説

エキスパートです#PAST受験結果 pic.twitter.com/0e8l183xRV — ひとあれ (@hitoare1) December 14, 2019 12月14日にAtCoder社のアルゴリズム実技検定(PAST)をリアルタイム受験しました。 結果は満点でエキスパート認定を獲得できました。 受験時の実力 受験…