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

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

Gauss-Jordanの掃き出し法

AOJ 3369 Namori Counting (OUPC 2023 day2-D)

北大セットの D 問題。人生で初めて行列木定理を使った! 問題へのリンク editorials 問題概要 頂点数 、辺数 の連結な単純無向グラフが与えられる。 今、このグラフにおいて連結性を保ったまま 本の辺を削除する。そしてこのとき閉路が 1 個残るので、閉路…

AtCoder ABC 313 D - Odd or Even (青色, 550 点)

みたいな連立方程式を解いた経験があれば、思いつきやすいかもしれない。 問題へのリンク 問題概要 (インタラクティブ) 0 と 1 のみからなるサイズ の数列 があるが、未知である。いくつか質問を繰り返すことで、この数列を特定したい。 最大で 回まで質問す…

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

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

AtCoder ABC 128 C - Switches (緑色, 300 点)

bit 全探索 問題へのリンク 問題概要 個のスイッチがある。スイッチによって 個の電球が点いたり消えたりする。 電球 は 個のスイッチに繋がっており、スイッチ のうち on になっているスイッチの個数を 2 で割った余りが に等しい時に点灯します。 全ての電…

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

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

AOJ 2624 Graph Automata Player (JAG 夏合宿 2013 day4-F) (550 点)

グラフに行列は付き物!!! 問題へのリンク 問題概要 頂点の有向グラフが与えられる。自己ループを含み得るが、多重辺は含まないことが保証される。 各頂点に 0 か 1 の値が割り振られている (が、その値がわからない)。以下の操作を 回行った後の各頂点の…

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

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

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

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

AOJ 2530 Reverse Game

ライツアウト系のいい感じの問題。そして bitset を用いたビットベクター高速化による高速化が求められる。 問題へのリンク 問題概要 × のグリッドがあって、各マスは白か黒に塗られている。今、何個かのマスを選んで 選んだマスから四方八方に伸ばして届く…

AOJ 1308 Awkward Lights (ICPC アジア 2010 D) (550 点)

ライツアウト系の典型題 問題へのリンク 問題概要 × のグリッドと正の整数 が与えられる。各マスは 0 か 1 の値が振られている。今、以下の操作を好きな回数だけ行うことで、すべてのマスの値を 1 にしたい。それが可能かどうか判定せよ。 マスを 1 つ選んで…

AOJ 1328 Find the Outlier (ICPC アジア 2012 D) (450 点)

連立方程式の練習。多項式補間でも解ける。誤差がきつい。 問題へのリンク 問題概要 次多項式 がある (係数はわからない)。 個の点 の値がわかっている...はずだったが、そのうちの 1 個については間違った値が出力された状態で入力が与えられる。どれが間違…

AOJ 2171 Strange Couple (JAG 夏合宿 2009 day3-G) (600 点)

ランダムウォークな問題! 実数係数の連立方程式の練習に 問題へのリンク 問題概要 頂点の重み付き無向グラフが与えられる。ただし自己ループを含み得る (多重辺はない)。二頂点 が指定されていて、 から へとランダムウォークによって辿り着きたい。 ただし…

yukicoder No.803 Very Limited Xor Subset

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

みんなのプロコン 2019 E - Odd Subrectangles (橙色, 800 点)

すごく面白そうだし、これ考えたかった 問題へのリンク 問題概要 × の binary 行列 が与えられる。 行集合の部分集合 通り 列集合の部分集合 通り の組であって、 の各要素のうち、行と列がともに該当する部分集合に含まれるようなものの総和が奇数となって…

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

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

TopCoder TCO 2013 Round 2A Medium - TheMagicMatrix

mod. p での連立一次方程式の練習などに!!! 問題へのリンク 問題概要 × のマス目があり、そのうちの マスについては既に 以上 以下の数値が入れられている。残りの マスに 以上 以下の数値を入れる方法のうち どの行の和と、どの列の和をとっても、その一…