ARC

AtCoder Regular Contest 083 E - Bichrome Tree

http://arc083.contest.atcoder.jp/tasks/arc083_c 問題概要 N頂点の根付き木とN要素の数列Xが与えられる。木の各頂点に白or黒の色と非負整数を割り当てるとき、頂点nを根とする部分木に含まれる頂点のうちnと同じ色のものに割り当てられた数の合計がX_nとな…

AtCoder Regular Contest 078 E - Awkward Response

http://arc078.contest.atcoder.jp/tasks/arc078_c 問題概要 ある正整数Nが設定されている。64回以内の質問クエリでNを特定せよ。質問クエリで正整数nを投げると、「n <= N かつ str(n) <= str(N)」または「n > N かつ str(n) > str(N)」 のときYESが、そう…

AtCoder Regular Contest 082 F - Sandglass

http://arc082.contest.atcoder.jp/tasks/arc082_d 問題概要 砂時計に合計X[g]の砂が入っている。砂は1秒に1[g]のペースで上から下に落ちる。砂時計はr1, r2, …, rK秒後にひっくり返される。ここでQ個のクエリ(ti, ai)が与えられるので、初めに砂時計の上の…

AtCoder Regular Contest 082 E - ConvexScore

http://arc082.contest.atcoder.jp/tasks/arc082_c 問題概要 二次元平面上のN個の点が与えられる。これらの点の部分集合Sであって凸多角形をなすものについて考える。このようなSの凸包に対し、凸包の周上の点と内部の点の数の合計をnとし、2n-|S|をSのスコ…

AtCoder Regular Contest 081 F - Flip and Rectangles

http://arc081.contest.atcoder.jp/tasks/arc081_d 問題概要 H×Wの2次元のマス目が与えられる。各マスは白か黒のどちらかで塗られている。任意の行または列を選びその行または列に含まれるすべてのマスの色を反転させる、という操作を好きなだけ行えるとき、…

AtCoder Regular Contest 081 E - Don't Be a Subsequence

http://arc081.contest.atcoder.jp/tasks/arc081_c 問題概要 文字列Sが与えられる。Sの部分列ではないような文字列のうち、最も短いものを求めよ。答えが複数ある場合には辞書順で最小のものを答えること。文字列はいずれも英小文字のみからなるものとする。…

AtCoder Regular Contest 080 F - Prime Flip

http://arc080.contest.atcoder.jp/tasks/arc080_d 問題概要 1, 2, …と順に番号の振られた無限枚のカードと、N要素の数列Xがある。数列Xに含まれる番号のカードは表向きで、それ以外は裏向きである。奇素数pと連続するp枚のカードを自由に選びそれらを裏返す…

AtCoder Regular Contest 080 E - Young Maids

http://arc080.contest.atcoder.jp/tasks/arc080_c 問題概要 偶数N、1~Nの順列P、空の数列Qがある。Pが空になるまで以下の操作を行う。 操作: Pの隣り合う2要素を選び、順序を保ったままQの先頭に追加する。 これによってできるQのうち、辞書順で最小のもの…