hitoare日記

たまに書きます

競技プログラミング

E - Roaming (AtCoder Beginner Contest 156)

問題リンク atcoder.jp 問題概要 n個の部屋に1人ずつ人がいる。 「ある部屋から1人、別の部屋に移動する」という操作がちょうどk回行われた後の人数の組み合わせとしてありえるのは何通りか。 解法 \(n\geqq3\)なので無駄打ちが可能。 たとえば部屋1→部屋2と…

F - Silver Fox vs Monster (AtCoder Beginner Contest 153)

問題リンク atcoder.jp 問題概要 数直線上に\(N\)体のモンスターがいる。それぞれのモンスターは座標\(X_i\)にいて、体力は\(H_i\)である。 次の操作を好きなだけおこなう。 好きな座標\(x\)を選び、爆弾を使用する。このとき座標が\(x-D\)以上\(x+D\)以下の…

E - Flatten (AtCoder Beginner Contest 152)

問題リンク atcoder.jp 問題概要 \(N\)個の正整数\(A_1,…A_N\)が与えられる。 正整数列\(B_1,…B_N\)であって、\(A_iB_i = A_jB_j\) が全ての\( (i,j)(1\leqq i < j\leqq N)\)にして成り立つ物のうち、\(B_1+B_2+ \ldots +B_N\)の最小値を\(10^9+7\)で割った…

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)をリアルタイム受験しました。 結果は満点でエキスパート認定を獲得できました。 受験時の実力 受験…