2018-07-01から1ヶ月間の記事一覧
問題 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と変わらない（遷移に…
