D - プレゼント 概要 N項の数列HとWが与えられ、N個の箱の縦の長さと横の長さを表す。箱iと箱jはHi 入れ子にすることができるか。 制約 1 ≦ N ≦ 10^5 1 ≦ H, W ≦ 10^5 方針 Hが全て異なる場合は、H・WのペアについてHを昇順に並べた後、WのLISの長さが答え。…

D - へんてこ辞書 概要 N頂点N辺の有効グラフとN項の数列bが与えられる。各頂点から出る辺は1本であり、b[i]は頂点iから出ている辺を表す。 頂点aからスタートし、k回移動した後にいる頂点番号を答えよ。 制約 2 ≦ N ≦ 10^5 1 ≦ k ≦ 10^100000 共通方針 この…

D - Flipping Signs 概要 N項の数列Aが与えられる。「1からN-1までの番号iを選び、A[i-1]とA[i]に-1を乗算する」という操作を好きなだけ行う。操作終了後の数列をBとするとき、Bの和の最大値を求めよ。 制約 2 ≦ N ≦ 10^5 -10^9 ≦ A[i] ≦ 10^9 方針① いろい…

D - Handstand 方針 反転する区間は0が続いている区間のみを考えてよい。 すると問題は、0が続いている区間をK区間ずつ1に反転していって、1が連続する区間が最大になるものを求めればよい。これは尺取り法でO(N+K)で求めることが出来る。 感想 下記ブログを…

D - Cake 123 概要 X項の数列A、Y項の数列B、Z項の数列Cがある。 A、B、Cからそれぞれ1項ずつ取り出して和を求めるとき、その和が大きい順にK個出力せよ。 制約 1 ≦ X, Y, Z ≦ 1000 1 ≦ K ≦ min(3000, X * Y * Z) 1 ≦ Ai, Bi, Ci ≦ 10^10 方針 Ai + Bj + Ck…

Union-Find木に関する問題集です。 ATC001 B - Union Find B: Union Find - AtCoder Typical Contest 001 | AtCoder 概要 (Union-Find木そのまま) 解答 Submission #4827269 - AtCoder Typical Contest 001 | AtCoder #include <bits/stdc++.h> #define rep(i,n) for(int i=</bits/stdc++.h>…

D - 射撃王 概要 風船がN個あり、風船iは現在H[i]の高度にあり、1秒間に高度がS[i]上昇する。 現在の状態からスタートして0秒後、1秒後、…と1秒おきに1つずつ風船を撃ち、風船を割ってゆく。 各風船が割られたときの高度をその風船からのペナルティーとし、…

D - LCM Rush 概要 整数N, Kについて、LCM(1, K) + LCM(2, K) + … + LCM(N, K) を求めよ。以下、100点解答です。（満点は101点） 制約 1 ≦ N ≦ 10^9 1 ≦ K ≦ 100 方針 重要な等式としてLCM(a, b) = a * b / GCD(a, b) が成り立つ。 するとLCM(1, K) + LCM(2,…

D - We Like AGC 概要 長さNの文字列で、下記の条件をすべて満たすものはいくつあるか。 アルファベットA, G, C, Tからなる "AGC"という文字列を含まない 隣接する2文字を交換しても"AGC"を含むようにできない (mod 10^9+7して解答) 制約 3 ≦ N ≦ 100 方針 D…

D - バレンタインデー 概要 女子がN人、男子がM人いる。 女子をP人、男子をQ人選んで集団を作り、この集団に女子xiと男子yiが含まれる場合、女子は男子にチョコレートiを渡すことができ、幸福度がzi増加するものとする。(（xi, yi, zi）はR組与えられる) 女…

D - XOR World 概要 非負整数A, Bに対し、f(A, B) = A XOR A+1 XOR ... XOR B とする。f(A, B)を求めよ。 制約 0 ≦ A ≦ B ≦ 10^12 方針 XORの逆操作はXOR自身なので、f(A, B) = f(0, B) XOR f(0, A) よって0からXまでの累積XORを求めればよい。0から数字を2…

D - 阿弥陀 概要 N本の縦棒、M本の横棒をもつあみだくじがある。 1からNまでの各整数iについて、i番目の縦棒からスタートしてこのあみだくじをD回通った後に、何番目の縦棒に到達するかを出力せよ。 制約 2 ≦ N ≦ 10^5 0 ≦ M ≦ 2 * 10^5 1 ≦ D ≦ 10^9 方針 …

D - 大ジャンプ部分点100点の解法。 概要 XY平面上の(0, 0)にいる。下記の移動のうちランダムにどれか1つを実行することN回繰り返した後、(X, Y)にいる確率を求めよ。 X軸に平行に+Dだけ移動する X軸に平行に-Dだけ移動する Y軸に平行に+Dだけ移動する Y軸に…

概要 D - 金塊ゲームW×Hマスの各マスに金が置いてある。またそのうちNマスに金を回収する機械が置いてある。 金を回収する機械を動作させると、その機械が置いてある行・列の金をすべて回収することが出来る。 ただし機械を動作させたとき、機械のマスから行…

D - Lazy Faith 概要 数直線上にA項の数列s（神社の位置）とB項の数列t（寺の位置）がある。Q項の数列xの各項xiについて、次の数値を答えよ。 xiからスタートして、sの項とtの項に1つずつ移動するときの最小の移動距離(sとtはどちらから移動してもよい) 制約…

概要 10進数表記で4, 9を含む数字が禁止されているとき、整数A, BについてA以上B以下の整数で禁止された数字はいくつあるか。 制約 1 ≦ A ≦ B ≦ 10^18 方針 桁DP。 解答① ペケンペイさんのを参考に。 pekempey.hatenablog.com 制約はすべてループで考慮し、…

D - トランプ挿入ソート 概要 1からNまでの数字が書かれたN枚のカードが1列に並べられている。 このカードを挿入操作（あるカードを取り出し、別のカードとカードの間に置く操作）を繰り返し、カードを昇順に並べ替えたい。 最小の操作数を求めよ。 制約 1 …

D - Match Matching 概要 1から9までの数字のうち、使用してよい数字があらかじめ与えられる。 使用してよい数字を使ってできる最大の整数を求めよ。ただし、各数字を1つ作る度にコストがそれぞれ2, 5, 5, 4, 5, 6, 3, 7, 6かかるものとし、コストの合計がち…

D - XXOR 概要 N個の非負整数列A と非負整数Kが与えられる。 X f(X)の最大値を求めよ。 制約 1 0 0 共通方針 X, K, Aを2進数で考え、各桁（ビット）ごとに見ていく。 全てのA[j]のi桁目を確認し、0が多ければXのi桁目は1となるのがよく、逆に1が多ければXのi…

D - マーブル 概要 数直線上の整数点に箱がある。 赤玉がR個、緑玉がG個、青玉がB個あり、それぞれ数直線上の地点-100、0、100の箱に入っている。 この玉を1つずつ隣に移動させ、各地点にある箱にある玉の数が多くとも1つにしたい。ただし、玉を移動する際は…

D - AtCoder社の冬 概要 R * CマスのうちのX * Yマス内にデスクをD個、サーバーラックをL個置く。 このとき、X * Yマス内の最も外側の4辺にはそれぞれ、デスクもしくはサーバーラックが置かれているものとする。 このような置き方（X * Yマスの選び方、デス…

D - 浮気予防 概要 頂点辺の無向グラフと項の数列が与えられる。はからまでの整数からなり、相異なる。グラフの頂点は0-indexed。 グラフのうちいくつかの辺を通行止めにし、その状態で頂点から各頂点にいくつ行けるかを考える。 このとき、「通行止めにする…

D - Various Sushi 概要 項の数列とが与えられる。この中から項を選び（とで添字共通）、「の項の和(の項に現れる数値の種類数の2乗) 」(と呼ぶ)を最大化せよ。 制約 方針 ①先にを降順ソートし、先頭から項を使用してを計算する。 ②その後、それ以降の数列を…

D問題 Equal Cut (600) D - Equal Cut 概要 長さの配列を4つの部分に分け、部分の和をそれぞれとする。 このときの「最大値と最小値の差」の最小値を求めよ。 方針 区切りは全部で3つだが、このうち真ん中の区切りに注目する。 このとき、左の最適な区切り方…