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

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

2019-03-20から1日間の記事一覧

AOJ 2386 Sightseeing Tour (AOJ-ICPC 250 点)

完全グラフはどのように向きづけしてもハミルトンパスが存在するというね!!! その証明はすごく楽しいと思う!!! 問題へのリンク 問題概要 頂点数 の完全無向グラフが与えられる。今、すべての辺に向きをつけたい。各 i, j に対して 頂点 i から頂点 j …

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

0. はじめに 上の連立一次方程式を定式化して解く問題は過去何度も出題されています。ついこの間も、yukicoder でてんぷらたんの問題 (No.803 Very Limited Xor Subset) が出題されて話題になりました! 連立一次方程式は Gauss Jordan の掃き出し法によって…

AOJ 2624 Graph Automata Player (AOJ-ICPC 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)

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

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

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

Codeforces #547 Div. 3 F - Same Sum Blocks (Hard)

区間スケジューリングと聞いて 問題へのリンク 問題概要 要素からなる数列 が与えられる。以下の条件を満たす最大個数の区間を求めよ (どれか 1 つ復元せよ)。 どの 2 つの区間も交差しない どの区間についても含まれる値の総和が等しい 制約 考えたこと 区…

てんぷらたんの双子素数問題

TL で見たので 問題へのリンク 問題概要 双子素数 が与えられる。 を で割ったあまりと、 を で割ったあまりをそれぞれ出力せよ。 制約 解法 1: Wilson の定理 簡単のため、適切に swap して とする。 Wilson の定理というのがあり、 を素数として が成立す…

TCO 2013 Round 2A Med TheMagicMatrix

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

AOJ 2171 Strange Couple (AOJ-ICPC 600 点)

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