けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

XOR

AtCoder ABC 141 F - Xor Sum 3 (黄色, 600 点)

Xor Sum シリーズしゃん。典型てんこ盛り!!! XOR は各桁ごとに独立に考えるとよい XOR に関する問題は mod. 2 での方程式みたいになることも多い であることから上位の桁から辞書順的に優先で考えるような貪欲が決まる などなど。 問題へのリンク 問題概…

AtCoder ABC 129 E - Sum Equals Xor (水色, 500 点)

まさにこの考え方で解ける問題 drken1215.hatenablog.com 今回の問題も桁 DP でもよいのだが、実は桁 DP しなくても解ける。 問題へのリンク 問題概要 正整数 が二進数表記で与えられます。 以下の条件を満たす非負整数 の組がいくつ存在するか求めてくださ…

AtCoder ABC 126 F - XOR Matching (青色, 600 点)

600 点問題ともなると、さすがに正解者数も少ない。 色んな人が色んな構築してそうだけど、僕なりの方法をば。 問題へのリンク 問題概要 を 以上の整数とする。 以上 以下の整数が 2 個ずつあって、これを並べ替えてできる長さ の数列 であって、 となるよう…

diverta 2019 E - XOR Partitioning (橙色, 800 点)

時間かかりすぎた。シンプルで面白い。 問題へのリンク 問題概要 要素からなる 0 以上の整数列 が与えられる。 これをいくつかの連続した部分列に分割する 通りの方法のうち、各連続区間の XOR 和が互いに等しくなるものが何通りあるか、1000000007 で割った…

AtCoder ABC 124 D - Handstand (緑色, 400 点)

これ...以前 Twitter につぶやいた問題とよく似てた!!! 400 点くらいの問題【問題】N 要素の 0 と 1 から成る数列が与えられる。以下の操作を最大 K 回行なって錬成し得る数列が何通りあるか 10e9 で割った余りを求めよ「数列の連続する区間を選んで 0 と…

Gauss-Jordan の掃き出し法と、連立一次方程式の解き方

0. はじめに プログラミングコンテストにおいて、連立一次方程式を解くことに帰着できる問題は数多く出題されています。 連立一次方程式は Gauss Jordan の掃き出し法によって解くことができるのですが、「その解の個数を求めよ」などと言われたときに詰まり…

yukicoder No.184 たのしい排他的論理和(HARD)

何度も出題されて典型となった「XOR 和が K となる部分集合は何通りか」という問題の亜種。 連立方程式を解くのとはちょっと違う趣向の、でもランクを求める感じの問題。 問題へのリンク 問題概要 個の正の整数 が与えられる。これらのうちから何個か選んで …

CODE FESTIVAL THANKS 2017 F - Limited Xor Subset (500 点)

ここでは行列の掃き出し法で殴ってみる 問題へのリンク 問題概要 個の正の整数 が与えられる。これらのうち 個以上選んで、その XOR 和が となるようにしたい。そのような選び方が何通りあるか、1000000007 で割った余りを求めよ。 制約 考えたこと 実は本番…

yukicoder No.803 Very Limited Xor Subset

F2 線形代数大好き! 問題へのリンク 問題概要 個の整数 の部分集合を選んで XOR 和を にする方法のうち、 個の区間 [ ] () について 区間の中から選ぶ個数は偶数個か奇数個かが指定される という制約を満たすものが何通りあるか求めよ。 制約 考えたこと 実…

AtCoder ARC 045 C - エックスオア多橋君 (試験管青色)

XOR について a ^ a = 0 な性質を上手く使う問題として。 問題へのリンク 問題概要 頂点の重み付きツリーが与えられる。 整数 が与えられ、ツリー上のパスであってパス上の重みの XOR 和が となるものが何個あるかを数えよ。 制約 考えたこと 根を 1 つ決め…

AtCoder ABC 121 D - XOR World (緑色, 400 点)

みんな早い...!!! 問題へのリンク 問題概要 2 つの整数 () が与えられる。 以上 以下のすべての整数の XOR 和を求めよ。 制約 「A 以上 B 以下」と、「XOR の引き算」とは まず「 以上 以下の値の総和を求めよ」という問題は、「 以下の値の総和を求めよ…

AtCoder ABC 117 D - XXOR (水色, 400 点)

以下の典型思考で解けるけど、苦手意識...^^; XOR な問題は各桁ごとに見る の動ける範囲が 以下と指示されているときは、 を上位ビットから見ていったときに、それがどこまで と一致するかを考える (桁 DP でおなじみの考え方) 問題へのリンク 問題概要 個の…

AtCoder ABC 091 D - Two Sequences (ARC 092 D) (黄色, 500 点)

桁ごとに考えるしかなさそうなのはそれはそう... 問題へのリンク 問題概要 (ARC 092 D / ABC 091 D) 要素の数列 と が与えられる。 個の整数 の XOR 和を求めよ。 制約 < 解法 XOR 和と言われた時点で、各桁ごとにカウントしたい気持ちにはなる。 個の整数の…

Codeforces Round #198 (Div. 1) D - Iahub and Xors (R2500)

領域加算、領域和取得の両方に対応した二次元 BIT ライブラリを目指した 問題概要 N × N の盤面において以下の M 個のクエリに答えよ: 長方形領域 [x0, y0] × [x1, y1] の XOR 和を出力 長方形領域 [x0, y0] × [x1, y1] 全体に一様に値 v を XOR 加算 考えた…

Codeforces Manthan Codefest 18 (Div. 1 + Div. 2) C. Equalize (R1300)

超苦手系。なんとか解けた。 問題へのリンク 問題概要 長さ N のバイナリ列 a, b が与えられる。a に対して 隣接二項を swap する 0 と 1 を反転する の操作を最小回数行って b にせよ。(10 -> 01 なら 1、1000 -> 0001 なら 2) 制約 1 <= N ,= 106 考えたこ…

2018 codeFlyer 本選 F - 配信パズル (800 点)

本番中なんとか解けたけど、すごくグチャグチャしたん。 問題へのリンク 問題概要 すぬけ君は、 日間にわたって、毎日次のようなパズルを解こうとしている。 すぬけ君の持っている端末に、縦 行、横 列からなる格子状の盤面が毎日配信されてくる。それぞれの…

2018 codeFlyer 本選 D - 数列 XOR (600 点)

本番、最後には綺麗な解法になったけど、何度も WA を出して大変だったん。 問題へのリンク 問題概要 要素の数列 が与えられる。この数列に以下の操作を好きな回数だけ繰り返して数列 にできるかどうかを判定せよ。 【操作】 を xor に置き換えるか、 を xor…

AtCoder ABC 098 D - Xor Sum 2 (ARC 098 D) (水色, 500 点)

こんなしゃくとり法もあるのんな。面白いん。 ABC 098 D Xor Sum 2 問題概要 長さ の正の整数列 が与えられる。整数列の連続する部分列のうち、「xor 和と加算和とが等しい」という条件を満たすものを数え上げよ。 制約 数値例 1) 答え: 5 (2), (2, 5), (5),…

CS Academy 061 F - Xor the Graph (超鮮やかなオイラー閉路!)

こうきさんに聞いて解いてみた。 木を最小個数のパスで被覆する問題はとりあえず2種類あって、辺の重複ありの場合は昨日のCSA 069 D. Cover the Treeで適切に葉同士で繋ぐ感じにする。辺の重複無しの場合は奇数次の点に適当に辺を張ってオイラー閉路作って切…

TopCoder SRM 694 DIV1 Easy - TryShell

いい問題だった。 問題概要 0 以上 255 以下の整数が n 個与えられる。 この n 個の整数を 3 組に分ける方法のうち、各組の xor 和の総和が最大となるものを求めよ。(制約) ・3 解法 dp[ i+1 ][ j ][ k ] := i 番目までみたとき、二組の和がそれぞれ j, k の…