B - 花束 概要 赤い花がR本、青い花がB本ある。次の2種類の花束を好きなだけ作るとき、2種類の花束の合計の個数の最大値を求めよ。 赤い花がx本、青い花が1本の花束 赤い花が1本、青い花がy本の花束 制約 1 ≦ R, B ≦ 10^18 2 ≦ x, y ≦ 10^9 方針 2分探索を使…

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…

B - ドキドキデート大作戦高橋君 概要 隣接した教室がN個あり、1からNと付番されている。 M個の掃除割り当てがあり、i番目の割り当てではsi番目からti番目の教室を掃除することになっている。 i番目の割り当ては、iの割り当てのすべての教室がi以外の割り当…

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

B - 最短路問題 概要 長さNの数列Aが与えられる。 A[i]を頂点0から頂点iまでの最短距離とするようなN頂点連結無向グラフは何通りあるか。 （mod 10^9+7して解答） 制約 1 ≦ N ≦ 10^5 方針 まずは不適切なインプットを除外する。不適切なインプットは下記の通…

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,…

B - ツリーグラフ 概要 n頂点の木が与えられる。いくつかの頂点には宝石が置いてある。 頂点xからスタートして辺をたどり頂点にある宝石をすべて回収してxに戻ってきたい。 移動経路の最短の長さを答えよ。 制約 1 ≦ n ≦ 100 方針 xを根として考え、xから宝…

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

B - Balanced Neighbors 概要 N頂点の無向グラフで各頂点に１からNの番号付けがされてあり、下記の条件を持たすものを答えよ。 単純かつ連結 あるSが存在し、任意の頂点について隣接する頂点の和がS （解答はグラフの辺数・グラフの辺を出力する） 制約 3 ≦ …

A - Limited Insertion 概要 空の数列aに下記の操作をN回繰り返す。 i番目の操作では、1≦j≦iを選び、数列aの先頭からj番目にjを挿入する N項の数列bが与えられる。上記操作でbを作成できるかを判定し、できれば挿入する数字を順番にN行出力し、できなければ-…

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

B - 難易度 概要 N項の数列Dが与えられる。この数列から4項を非復元抽出する。 この4項が を満たすような抽出方法は何通りあるか。 （問題だと数列Dは「コンテストの問題の難易度」と対応） 制約 4 ≦ N ≦ 10^5 1 ≦ di ≦ 10^5 方針 下記のDP配列を考える。 dp…

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 方針 …

概要 H×Wマスのいくつかのマスに壁があり、(1, 1)にコマがある状態でゲームを行う。 先手と後手が交互に下記の操作を繰り返す。先に操作できなくなった方を負けとする。先手と後手どちらが勝つかを解答せよ。 コマを右・右下・下のいずれかの方向で、かつ壁…

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

概要 N頂点M辺の無向グラフの連結成分のうち、閉路を持たないものの個数をもとめよ。 制約 1 ≦ N ≦ 100 1 ≦ M ≦ N(N-1)/2 方針 各頂点でDFSを行い、DFS内で1度通った頂点にまた通ることがあれば閉路を持つと判定する。 感想 昔解いたやつですが、備忘のため…

概要 数列Aを下記のように定義する。数列AのM項目を答えよ。 A[1], A[2], ..., A[K] は問題で与えられる A[K+N] = (C[1] AND A[K+N-1]) XOR (C[2] AND A[K+N-2]) XOR ... XOR (C[K] AND A[N]) (N ≧ 1) 制約 1 ≦ K ≦ 100 1 ≦ M ≦ 10^9 A, C は32ビット符号な…

B - 大事な数なのでZ回書きまLた。 概要 数字と英大文字からなる長さNの文字列が2つ与えられる。2つの文字列中の数字と英大文字は下記の特徴がある。 2つの文字列は同じN桁の数字を表したものである。 2つの文字列の同じ位置の文字を見たとき、片方が英大文…

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

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

C - Synthetic Kadomatsu 概要 N項の数列lを使ってA, B, Cの3数を作る。数列には次のような加工を行う。 liに1加算する（コスト1） liに1減算する（コスト1） liとljを合体して(li + lj)の1つの項とする（コスト10） A, B, Cを作るために必要なコストの最小…

概要 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乗) 」(と呼ぶ)を最大化せよ。 制約 方針 ①先にを降順ソートし、先頭から項を使用してを計算する。 ②その後、それ以降の数列を…