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

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

方程式

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

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

AtCoder ABC 133 D - Rain Flows into Dams (400 点)

時々こういうの見る気がする。とりあえず求めたい値を と置いてみる感じ。 問題概要 を奇数とする。整数 が与えられるので ... を満たすような を求めよ。 制約 は奇数 考えたこと 問題の構造として 「 を決めると、残りが芋づる式にすべて決まってしまう」 …

AtCoder ABC 128 C - Switches (300 点)

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

AtCoder ABC 126 E - 1 or 2 (500 点)

これまた Union-Find を用いる教育的問題!!!!! 問題へのリンク 問題概要 枚のカードがあって、それぞれ 1 か 2 の数値が書かれている。 枚のカードの数値 をすべて当てたい。 現在、以下の形式をした条件が 個与えらている: 整数 に対して、 は偶数であ…

AOJ 2624 Graph Automata Player (AOJ-ICPC 550 点)

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

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 2171 Strange Couple (AOJ-ICPC 600 点)

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

AOJ 1089 Strawberry Cake

面積二等分系の第二弾 問題へのリンク 問題概要 頂点の凸多角形が与えられる。原点を通る直線であって、この凸多角形を面積が等分になるように切断するものを求めよ。複数ある場合はどれか 1 つ求めればよい。 制約 原点は凸多角形に内包される 考えたこと …

AOJ 2336 スプリング・タイル (AOJ-ICPC 600 点)

グリッド系は苦手意識あるけど解けてよかった 問題へのリンク 問題概要 二次元マップが与えられて、各マスは 床 ('.') 壁 ('#') バネ ('*') の 3 つの属性がある。スタート ('s') とゴール ('g') が設定されていて、いずれも床属性である。 s から g へ最速…