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

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

「選ぶ」と「選ばない」の一対一対応

AtCoder ARC 115 D - Odd Degree (黄色, 600 点)

なんとか解けた。若干エスパー気味に解いた。 問題へのリンク 問題概要 頂点数 、辺数 の無向単純グラフが与えられる。 各 に対して、この誘導部分グラフ (頂点集合はそのまま、辺集合は部分集合) であって、次数が奇数の頂点が 個であるようなものの個数を …

AtCoder ARC 109 E - 1D Reversi Builder (橙色, 700 点)

これを本番間に合わせられたなかったのは辛かった... あと、数え上げパートがあんなにスマートにはできなかった。無限に から落とせなかった... 問題へのリンク 問題概要 黒石さんと白石さんは、一列に並んだ 個のマスからなる盤面を使って遊んでいます。 マ…

Codeforces Global Round 12 H1. Multithreading (Easy Version) (R2900)

ぷよぷよみたいに 2 つ揃うと消えるような対象物の数え上げ問題。これを思い出した drken1215.hatenablog.com 問題へのリンク 問題概要 (意訳) "B", "W", "?" のみからなる長さ の文字列が与えられる ( は偶数)。"?" に "B", "W" を割り当てる方法のうち、"B…

AtCoder AGC 017 A - Biscuits (緑色, 200 点)

これ、知らなくても解ける制約設定だけど、結構大変やね 問題へのリンク 問題概要 個の正の整数 が与えられる。これらからいくつか選ぶ方法のうち、総和を 2 で割ったあまりが となる方法が何通りあるかを求めよ。 制約 考えたこと 一般に 総和が奇数 ⇔ 和の…

AtCoder ARC 096 E - Everything on It (赤色, 900 点)

部分点がなければ CE 2 完でも赤パフォ出たのに... それはともかく、この手の包除で絶対に解けるという安定感をもって解けるようになりたい! 問題へのリンク 問題概要 ラーメンに 種類のトッピングを自由に組み合わせて乗せることができます。トッピングの…

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

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

AtCoder ARC 004 D - 表現の自由 (試験管黄色)

これがインフレ!?ABC 110 D - Factorization に瓜二つ 問題へのリンク 問題概要 整数 を 個の整数の積として表す方法が何通りあるかを、1000000007 で割ったあまりを求めよ。 制約 考えたこと ほとんど、ABC 110 D - Factorization と一緒。 だが、マイナ…