リンク : https://csacademy.com/contest/archive/task/uniform-trees/statement/ 問題概要 N頂点の木が与えられる、それそれの頂点にラベルがつけられる。以下の条件を満たす頂点集合の通り数を求めよ。 ・頂点集合のうちある１つの頂点はほかのすべての頂…

リンク : https://csacademy.com/contest/archive/task/wrong-brackets/statement/ 問題概要 ( がN個、) がN個の文字列で、括弧の対応が正しくない文字列の中で辞書順でK番目を求めよ。 解説 辞書順より前から求めることを考える。次に ( か ) のどっちを置…

リンク : https://csacademy.com/contest/archive/task/ultimateorbs/statement/ 問題概要 N個のオーブがある。それぞれのオーブは隣のオーブが自身のコスト+D以下だと、隣のオーブの重さを吸収する。それぞれのオーブに関して、自身が最後まで残ることがで…

リンク : https://csacademy.com/contest/archive/task/random_nim_generator/statement/ 問題概要 N個の0より大きくK以下の数字の入った配列を作ります。作った配列のすべてをxorすると0より大きくなるものは何通りあるか求めよ。 解説 まず、普通にdpをし…

リンク : https://csacademy.com/contest/archive/task/connected-tree-subgraphs/statement/ 問題概要 N頂点の木が与えられる。それぞれの頂点に新たにラベル(頂点番号)をつける。1<=k<=Nのすべてのkについて、ラベルが1からkまでの頂点を選んだとき、1から…

リンク : https://csacademy.com/contest/archive/task/partial_ladder_graph/statement/ 問題概要 N2頂点とN+2(N-1)辺のグラフが与えられる。1<=i<=N-1 の頂点iはi+1同士を結んでいる。N<=i<=2N-1も同様である。また、1<=i<=N-1の頂点iと頂点i+(N-1)は結ば…

リンク : https://csacademy.com/contest/archive/task/ball-sampling/ 問題概要 N色のボールがあり、箱にそれぞれA_i個入っている。同様に確からしいとき、すべての色のボールを一回以上取り出す期待値を求めよ。 解説 いわゆる、コンプリート問題と言われ…

リンク : https://csacademy.com/contest/archive/task/amusement-park/statement/ 問題概要 N*Mの行列Aが与えられる。このA[i][j]は座標(i,j)からA[i][j]の確率で座標(i,j+1)に進み、それ以外は座標(i+1,j+1)に進む。このとき、iがNになるときの移動回数の…

リンク : https://csacademy.com/contest/archive/task/city-attractions/statement/ 問題概要 N頂点の木が存在する。それぞれの頂点に美しさA[i]として入力される。d(x,y):=頂点xと頂点yの距離とする。頂点xにいるとき、次に進む場所はA[y]-d(x,y)が最大に…

リンク : https://csacademy.com/contest/archive/task/subarray-medians/ 問題概要 長さNの数列が与えられる。(1<=i<=j<=N かつ j-i=0 mod2)のすべてのi,jに関して[i,j]の中央値をmとしたとき、ijmの総和を求めよ。 解説 最初、iを決めて、前から順にBIT上…

リンク : https://csacademy.com/contest/archive/task/maxor/statement/ 問題概要 N個の数字が与えられ、任意の二つの数字をorで計算したときの最大値とこの最大値となる通り数を求めよ。 解説 これもまた高速ゼータ変換...dp1[i]をiを部分集合としてもつ数…

リンク : https://csacademy.com/contest/archive/task/max-score-tree/statement/ 問題概要 N頂点の木とScoreiが与えられる。木のスコアは木に含まれる頂点vが持つ辺の数をEdge[v]とすると、この木のスコアはΣScore[Edge[v]]となる。入力で与えられた木の部…

リンク : https://csacademy.com/contest/archive/task/distinct-palindromes/statement/ 問題概要 文字列が与えられる。この文字列の部分文字列であり、回文であるのは何種類か求めよ。 解説 文字列をSとし、i番目の文字をS[i]とする。dp[l][r]をS[l]=S[r]=…

リンク : https://csacademy.com/contest/archive/task/bst-fixed-height/statement/ 問題概要 Nこの頂点を持ち、深さHの完全二分木の一部を使った木は何通りあるか求めよ。 解説 正直自分にはこの解説はかけない。最初、dp[i][j][k]:深さiのときの頂点をj個…

リンク : https://csacademy.com/contest/archive/task/subarray_removal/submissions/ 問題概要 長さNの数列が与えられる。この数列から空でないかつ最大N-1個の連続した数列を取り除く。そのときの区間の和が最大のときの値を求めよ。 解説 まず、5つの区…

リンク : https://csacademy.com/contest/archive/task/and-closure/statement/ 問題概要 長さNの数列が与えられて、個の部分集合のすべてをandで計算したときの数字の種類は何種類か求めよ。 解説 一見簡単そうに見えたが実は罠。dp[i]をiの集合を部分集合…

リンク : https://csacademy.com/contest/archive/task/to-front-to-back/statement/ 問題概要 長さNの1～Nを一つずつ含む数列が与えられる。この数列をソートしたい。任意の数字を先頭か後尾に移動させることによってソートする。ソートし終わったときのこ…

リンク : https://csacademy.com/contest/archive/task/surrounded-rectangle/statement/ 問題概要 N*Mの行列が与えられる。これは0,1から成る。0で完全に囲まれた1のみからなる長方形の面積を求めよ。完全に囲まれるとは、入力例を参照してほしい。 解説 や…

リンク : https://csacademy.com/contest/archive/task/lightbulbs/statement/ 問題概要 01から成る文字列が入力される。i番目が0の場合電球iがついてなくて、i番目が1の場合電球iがついているとする。電球iの操作できる条件が電球i+1がついていて、電球i+2,…

リンク : https://csacademy.com/contest/archive/task/expected-merge/statement/ 問題概要 マージソートのアルゴリズムと同様の関数を考えた時に、数列を半分にすることを繰り返す。奇数長の場合、区切られる場所は一意に定まらない。そこで、一様にランダ…

リンク : https://csacademy.com/contest/archive/task/restricted-permutations/ 問題概要 Nが与えられ、N-1個の数字が与えられる。この数字はi番目の数字が1ならば、iより後ろにi+1が存在する、0ならばiより前にi+1が存在する。N-1個の数字が示す条件をす…

リンク : https://csacademy.com/contest/archive/task/dominant-free-sets/ 問題概要 N個の頂点の座標が与えられる。任意の二頂点をP,Qとすると P_x>=Q_x と P_y>=Q_y を満たすものが存在しない、頂点の集合の選び方は何通りか+7の余りを求めよ。 解説 dp[i…

リンク : https://csacademy.com/contest/archive/task/consecutive-subsequence/ 問題概要 長さNの数列が与えられる。一つの任意の数字を任意の場所に入れられるとする。昇順に連続した最長の部分数列の長さを求めよ。(部分数列は連続している必要はない) …

リンク : https://csacademy.com/contest/archive/task/min-races/statement/ 問題概要 N人のレーサーとK種類のクラスが存在する。数回のレースを行う。レーサーの勝利条件は自分より順位が高い人は自分より大きいクラスに属する人のみの場合勝利となる。N人…

リンク : https://csacademy.com/contest/archive/task/unfair_game/ 問題概要 AlexとBenがゲームをする。長さNの数列を扱う。Alexは自由に1個以上の数列を取ることができる。Benは1個の数列しか取ることができない。Alexは取った数列の合計を最大化しようと…

リンク : https://csacademy.com/contest/archive/task/recursive-string/statement/ 問題概要 f(0)="a",f(1)="b",f(2)="c",f(n)=f(n-1)+f(n-2)+f(n-3) であらわされる文字列を返す関数がある。N,Kが入力されるのでf(N)のK番目の値を出力せよ。 解説 N<=35よ…

リンク : https://csacademy.com/contest/archive/task/max-even-subarray/ 問題概要 長さNの数列が与えられる。数列から連続した偶数個を取り出したときの最大値を求めよ。 解説 前から偶数個取り出した結果が負であれば、その次の2個を取り出すときは無視…

リンク : https://csacademy.com/contest/archive/task/divisor_clique/statement/ 問題概要 長さNの数列が与えられ、いくつか選んで数列を作る。この数列から任意の二数A、B(A>B)をとってきたら、必ず A%B=0 となる数列の最大の長さを答えよ。 解法 dp[i][j…

最近、競技プログラミングの熱が冷めてしまいそうで怖いので、新しいことを初めて見ようと思いましたまる 自己紹介 AtCoder 青 海外コンテストはあまり出ていない 今年のJOIの本選は2問目の初期化ミスった；； 精進ができない体のせいで最近レートが落ち始め…