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

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

スタートを0としてよい

AtCoder ABC 131 C - Anti-Division (300 点)

「A 以上 B 以下の整数のうち〜を満たすものの個数を求めよ」という問題では (B 以下の整数のうちの〜を満たすものの個数) から (A-1 以下の整数のうちの〜を満たすものの個数) を引く とすると、すごくやりやすい!!!!! このテクニックは大昔の topcode…

AtCoder AGC 017 B - Moderate Differences (400 点)

むむむ 問題へのリンク 問題概要 長さ の整数列 であって、 が 以上 以下の整数 となるものが存在するかどうかを判定せよ。 制約 考えたこと とりあえず , としてよい。 さて、 からスタートして、 ターン目にどんなのを作れるかを考察してみる。 1 ターン目…

AtCoder AGC 031 C - Differ by 1 Bit (800 点)

証明はできるし、その証明に基づいた構成を数学的に与えることまではできるけど、それを実装に落とすのがすごく大変な問題。。。 問題へのリンク 問題概要 整数 が与えられます。 の順列 であって、 次の条件をすべて満たすものが存在するかどうか判定してく…

AOJ 2530 Reverse Game

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

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

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

AtCoder ABC 121 D - XOR World (400 点)

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