ferinの競プロ帳

競プロについてのメモ

2018-12-25から1日間の記事一覧

Educational Codeforces Round 48 (Rated for Div. 2) D. Vasya And The Matrix

問題ページ 解法 bitwise xorなのでbitごとに独立に考えられる。したがってbitごとに考えればa,bは0/1の数列に帰着でき、答えの行列も0/1要素しか持たないと考えてよい。1が書かれている行・列には1を奇数個、0が書かれている行・列には1を偶数個置くような…

Xmas Contest 2018 B - Bit Smaller

問題ページ 解法 入力が与えられないので条件を満たす数を予め全列挙するプログラムをローカルで実行しておきその答えをtextで提出すればよい。数nをa1,b1,a2,b2,…,ak,bk,cと切れ目を入れたときに条件を満たしているような切り方があれば数nを答えに追加すれ…

yukicoder No.776 A Simple RMQ Problem

問題ページ 解法 この記事(Maximum Subarray Sum in a given Range - GeeksforGeeks)のセグメント木を使って解いた。このセグ木では区間[l,r)の連続した部分列の区間和のmaxを求めることができる。セグ木の各頂点に「区間和」「maximum prefix sum」「maximu…