問題 https://beta.atcoder.jp/contests/arc044/tasks/arc044_b N 頂点のグラフが与えられる。頂点 1 から頂点 i への最短路を a_i とするように辺を張るとき、辺の張り方は何通りか求めよ。 考え方 自明なケースを除く。まず 1 から 1 への最短路は 0 であ…

問題 https://atcoder.jp/contests/soundhound2018-summer-final-open/tasks/soundhound2018_summer_final_b 考え方 の閉区間をすべて にする。という操作の性質をフルに用いる。 DPを考える。 の最大値 と定義する。このとき操作を考えて、 の更新を考える…

54.ARC054-B:ムーアの法則 問題 https://beta.atcoder.jp/contests/arc054/tasks/arc054_b 今、ある関数の計算に p 年かかる処理がある。x 年後は処理速度が今の 2x/1.5 倍になるとき、計算が終わる最短時間を求めよ。 考え方 全体の仕事量を 1 として今の処…

問題 https://beta.atcoder.jp/contests/arc050/tasks/arc050_b 赤い花が 本、青い花が 本ある。以下の条件を満たすように花束を作る時最大いくつつくれるか？ 本の赤い花と 本の青い花からなる花束 本の赤い花と 本の青い花からなる花束 考え方 最大の花束…

問題 https://beta.atcoder.jp/contests/abc049/tasks/arc065_b 考え方 各頂点が連結なのかどうかを判定する必要があるため、素集合データ構造を使用することが思いつく。道路の K 個のクエリによって N を素集合データ構造 set1 に分割する。同様に鉄道の L…

問題 https://beta.atcoder.jp/contests/abc103/tasks/abc103_d N 頂点と N-1 本の橋がある。 N-1 本の橋は i と i+1 を結ぶ。与えられる M つの要望を満たすようにするためには、最小でいくつの橋を除けばいいか。 制約 1 <= N <= 105 1 <= M <= 105 1 <= a…

問題 https://beta.atcoder.jp/contests/abc102/tasks/arc100_b 数列 a_n から 3 点を選択して、数列を連続する 4 つの部分列に分解する。各部分列の総和を P, Q, R, S とする。 | max(P, Q, R, S) - min(P, Q, R, S) | の最小値を求めよ。 制約 4 <= N <= 2…

問題 https://beta.atcoder.jp/contests/abc034/tasks/abc034_d N 個の食塩水があり、i 番目の容器には濃度 p_i パーセントの食塩水が w_i グラム入っている。K 個の食塩水を選んだ時の最大の濃度を求めよ。 制約 1 <= N,K <= 1000 1 <= w_i <= 109 1 <= p_i …

問題 https://beta.atcoder.jp/contests/abc054/tasks/abc054_d N 個の薬品があり、それぞれ a_i, b_i, c_i で与えられる。各 i は1回まで選択できる。Σ a_i : Σ b_i = M_a : M_b となるようにいくつか薬品を選択するときの最小の Σ c_i を求めよ。 制約 1 <…

問題 https://beta.atcoder.jp/contests/abc041/tasks/abc041_d N 頂点上のグラフに、M本の有向辺が与えられる。M本の有向辺の条件を満たし、N 個の頂点を左から右へ横一列に並べる並べ方は何通りか。 制約 2 <= N <= 16 1 <= M <= N(N-1)/2 考え方 トポロジ…

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_2_A&lang=jp 巡回セールスマン問題。有向グラフ G(V, E) 上のある頂点から出発して、出発点に戻る閉路の最短距離を求めよ。 制約 2 <= |v| <= 15 0 <= d_i <= 1000 考え方 bitDPである。…

問題 https://beta.atcoder.jp/contests/agc005/tasks/agc005_b N個の数 {1, 2, 3, ..., n} の任意の順列 a_n が与えられる。 を求めよ。 考え方 ナイーブにシミュレーションするとO(N2)となり間に合わない。 N2 つの区間の最小値を求めて和を求めるのではな…

問題 https://beta.atcoder.jp/contests/abc008/tasks/abc008_3 N 枚のコインがある。それぞれ正の整数が書いてある。このコインを無作為にすべての組み合わせが同じ確率で出てくるように一列に並べる。以下の操作をした時の表を向いているコインの数の期待…

問題 https://beta.atcoder.jp/contests/arc091/tasks/arc091_b 1 <= a, b <= n である a, b が与えられる。a % b >= k である個数を求めよ。 制約 1 <= n <= 105 1 <= k <= n-1 入力値は整数 考え方 a_n = {1, 2, 3, ..., n}, b_n = {1, 2, 3, ..., n} の2…

問題 https://beta.atcoder.jp/contests/agc026/tasks/agc026_b 最初在庫が a 本ある。在庫から b 本減らす。c 本以下の時、在庫に d 個補充する。という操作を繰り返し実施した時、常に在庫が b 本以上あるかどうかを判定せよ。 制約 1 <= t <= 109 1 <= a,…

問題 https://beta.atcoder.jp/contests/code-thanks-festival-2017-open/tasks/code_thanks_festival_2017_d 1グループN人のグループに対して、定員M人のバスを用意する。すべての参加者がバスに乗り込めるような最小台数用意するとき、バスの最大の空席数…

問題 数列 (a_1, a_2, ... , a_n) の美しさを隣接2項の差の絶対値がdであるものの個数と定義する。 1<= a_i <= n である a_i を m 個並べた時の nm 個のすべての数列全体を考えたときの美しさの平均値を求めよ。 この問題で求められていることはすべての数列…

A.YahooYahooYahoo(400) 問題 方針 雑記 A.YahooYahooYahoo(400) 問題 文字列 S が与えられる。yahooの文字列を0個以上繰り返してできる文字列との編集距離を求めよ。 1 <= |S| <= 105 方針 ポイントは大きく2つ。他は普通の編集距離DPと変わらない（遷移に…

C.Minimization(300) 問題 方針 雑記 D.Snuke Numbers(500) 問題 制約 方針 雑記 C.Minimization(300) 問題 https://beta.atcoder.jp/contests/abc101/tasks/arc099_a 方針 最初に1を含んだk個置き換える。以降は最初に1で置き換えた範囲の1つの数とその他k-…

C.座圧 問題 方針 雑記 D.塗り絵 問題 方針 雑記 C.座圧 問題 https://beta.atcoder.jp/contests/abc036/tasks/abc036_c 数列 a_n = {a_1, a_2, ... , a_n} が与えられる。以下の条件を満たす数列 b_n を求めよ。 a_i < a_j ⇒ b_i < b_j a_i = a_j ⇒ b_i = b…

A.Diverse Word(300) 問題 方針 雑記 B.GCD Sequence(600) 問題 方針 雑記 C.Remainder Game(700) 問題 方針 雑記 A.Diverse Word(300) 問題 https://beta.atcoder.jp/contests/agc022/tasks/agc022_a すべての文字が異なる文字列Sが与えられる。辞書式順序…

C.Traveling(300) 問題 方針 雑記 D.Checker(500) 問題 方針 雑記 C.Traveling(300) 問題 https://beta.atcoder.jp/contests/arc089/tasks/arc089_a x-y二次元平面を考える。t=0で(0,0)にいる。1秒後に(x+1,y),(x-1,y),(x,y+1),(x,y-1)のいずれかになる。t_i…

LIS LISとはLongest Increase Subsequence の略で最長増加部分列と呼ばれる問題です。増加部分列とはすべての i < j で a_i < a_j となっている部分列のことです。 簡単な例を見てみます。 a_n = {1,3,5,2,4,6} という数列 a_n を考えます。 この時の最長増…

A.Happy Birthday!(100) 問題 方針 雑記 B.Ringo's Favorite Numbers(200) 問題 方針 雑記 C.*3 or /2(300) 問題 方針 雑記 D.Patisserie ABC(400) 問題 方針 雑記 追記 A.Happy Birthday!(100) 問題 https://beta.atcoder.jp/contests/abc100/tasks/abc100_…

はじめに これは桁DPに入門した私のメモ程度の記事になります。プロによる解説は 桁DP入門 - pekempeyのブログ Digit DP 入門 - torus711 のアレ あたりを参照することを推奨します。 ※この記事は書きかけになります。随時更新します。 桁DP 桁DPは「整数N以…

A.ABD(100) 問題 方針 雑記 B.Stone Monument(200) 問題 方針 雑記 C.Strange Bank(300) 問題 方針 雑記 D.Good Grid(400) 問題 方針 雑記 A.ABD(100) 問題 https://beta.atcoder.jp/contests/abc099/tasks/abc099_a 方針 nが999以下のときはABC、1000以上の…

C.Special Trains(300) 問題 方針 雑記 D.2017-like Number(400) 問題 方針 雑記 C.Special Trains(300) 問題 https://beta.atcoder.jp/contests/abc084/tasks/abc084_c n個の駅がある。1<=i<=n-1を満たすすべての整数iに対して、駅iから駅i+1にC_i秒で向か…

C.Train Ticket(300) 問題 方針 雑記 D.Wall(400) 問題 方針 雑記 C.Train Ticket(300) 問題 https://beta.atcoder.jp/contests/abc079/tasks/abc079_c 方針 3つのオペランドに対して+,-の8通りの組み合わせを全探索して、計算したときに7になる時のオペラン…

C.Write and Erase(300) 問題 方針 雑記 D.joisino's travel(400) 問題 方針 雑記 C.Write and Erase(300) 問題 https://beta.atcoder.jp/contests/abc073/tasks/abc073_c 方針 A_1,A_2,...,A_Nに含まれる数の個数を求め、奇数個の数の個数を出力すればよい…

A.Digits Sum 問題 方針 雑記 B.RGB Coloring 問題 方針 雑記 C.Interval Game 問題 方針 雑記 A.Digits Sum 問題 https://beta.atcoder.jp/contests/agc025/tasks/agc025_a 非負整数A,Bの和がNであるとき、A,Bの各位の和の合計の最小値を求めよ 方針 Nが105…