C - Snuke the Wizard 概要 N個のマスが直線状に並んでいて、そのマスにはアルファベットが記載されている。また各マスの上には一体ずつゴーレムが配置されている。Q個の命令があり、命令iはマスのアルファベットに対応するアルファベットtiと、"L"（左）か"…

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行出力し、できなければ-…

C - ロト2 概要 N項の数列Aと正整数Kが与えられる。 Ai * AjがKの倍数であるような(i, j) (i （以降、aがbの倍数である、すなわちbがaを割り切ることをb | aと記載する） 制約 1 ≦ N ≦ 200000 1 ≦ Ai ≦ 10^9 1 ≦ K ≦ 10^9 方針 まず考えられるのはすべての(i…

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ビット符号な…