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

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

0と1の問題

JOIG 2024 A - 三連続 (難易度 2)

for 文の練習問題! 問題へのリンク 問題概要 o と x からなる長さ の文字列 が与えられる。 の中に o が 3 つ連続している箇所があれば "Yes" を出力し、そうでなければ "No" を出力せよ。 制約 考えたこと for 文を用いて判定しよう。具体的には、各 i に…

AtCoder ABC 081 A - Placing Marbles (灰色, 100 点)

ABS にも採用した問題! 問題へのリンク 問題概要 長さが 3 の文字列 が与えられる。この文字列の文字は '0' か '1' である。 '1' が何文字あるかを答えよ。 解法 3 文字それぞれについて、'1' かどうかを調べれば OK。 #include <bits/stdc++.h> using namespace std; int </bits/stdc++.h>…

JOIG 2023 D - コイン集め 2 (難易度 6)

データを上手に持って、差分更新する系の問題 問題へのリンク 問題概要 のグリッドがあって、各マスは文字 '#' か '.' のいずれかが書かれている。先手は '#' の個数が得点となり、後手は '.' の個数が得点となる。双方得点を最大化したい。 先手は行を 1 つ…

AtCoder ABC 330 D - Counting Ls (茶色, 400 点)

次の問題にとても似ていた! drken1215.hatenablog.com 問題へのリンク 問題概要 のグリッドが与えられる。各マスには文字 'o' または 'x' が描かれている。これらのマスから 3 個選ぶ方法であって、 3 マスに書かれた文字はすべて 'o' である 3 マスのうち…

AtCoder ARC 168 D - Maximize Update (橙色, 700 点)

コンテスト中は迷走しまくってしまった 問題へのリンク 問題概要 マスがあって、最初はすべて白色である。以下の 種類の操作を好きな順序で好きな回数行うことができる。 種類目の操作: マス からマス までを黒色で塗る マス目の状態を変化させるような操作…

AtCoder Library Practice Contest L - Lazy Segment Tree

タイトル "Lazy Segment Tree" の名の通り、遅延評価セグメント木の練習問題! 問題へのリンク 問題概要 長さ の 0 と 1 のみからなる数列 が与えられる。この数列に対して、次の 回のクエリに答えよ。 クエリタイプ 1 ():数列の区間 内の各要素の値につい…

AtCoder ABC 309 B - Rotate (灰色, 200 点)

これ、詰まる人には詰まると思う。二次元配列の添字の扱いに習熟していないと難しい。 問題へのリンク 問題概要 のグリッドが与えられる。各マス目には 0 か 1 の値が書かれている。 このグリッドに対して、外周を時計回りに 1 マス分回して得られるグリッド…

AtCoder ABC 323 A - Weak Beats (灰色, 100 点)

添字の偶奇によって処理を分岐する系 問題へのリンク 問題概要 0 と 1 のみからなる、16 文字の文字列 が与えられる。 の左から偶数番目の文字がすべて '0' であるかどうかを判定せよ。 コード 先頭が S[0] なので、S[1], S[3], ..., S[15] の中に 1 がある…

AtCoder ABC 322 F - Vacation Query (青色, 550 点)

遅延評価セグメント木の練習問題! 問題へのリンク 問題概要 0 と 1 のみからなる長さ の文字列 が与えられる。次の 2 種類のクエリに答えよ。 クエリ (1 L R):文字列 の区間 内における、1 が連続する区間の長さの最大値を答えよ クエリ (2 L R):文字列 …

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

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

AtCoder AGC 063 A - Mex Game (緑色, 300 点)

考察に時間をかけすぎた 問題へのリンク 問題概要 文字 'A' と 'B' のみからなる長さ の文字列 が与えられる (先頭の文字を 0 文字目とする)。各 について、次の問に答えよ。 Alice と Bob が交互に、以下の操作を合計 回行う。Alice が先手である。なお、最…

AtCoder ABC 311 E - Defect-free Squares (水色, 475 点)

有名な DP をするか、二次元累積和 + 二分探索をするか 問題へのリンク 問題概要 のグリッドが与えられる。グリッドの各マスのうち、指定された 個のマスには穴があいている。その他のマスは穴があいていない。 グリッドに含まれる正方形であって、その内部…

AtCoder ABC 311 F - Yet Another Grid Task (青色, 525 点)

最初、各マスをタスクに見立てて、タスクの依存関係を考える DAG 上で DP できないかなどと考えたけど、うまくいかなかった。普通にグリッドを左から舐めていく DP でよかった! 問題へのリンク 問題概要 のグリッドがある。各マスはすでに白色 (文字 '.') …

AtCoder ABC 311 B - Vacation Together (灰色, 200 点)

二次元配列を活用する練習問題。また、「条件が連続する区間」を求める練習問題でもある。 問題へのリンク 問題概要 のグリッドが与えられる。各マスの値は 'o' か 'x' のいずれかである。 「どの行も文字 'o' であるような列」が最長で何個連続するかを求め…

AtCoder ABC 304 F - Shift Table (青色, 525 点)

メビウス関数を用いた約数系包除原理を使いこなそう! 問題へのリンク 問題概要 (表現改) 文字 '.' と '#' のみからなる長さ の文字列 が与えられる。今、文字 '#' をいくつか '.' に書き換えることによって、文字列 が周期的文字列となるようにしたい。 な…

AtCoder ABC 301 D - Bitmask (緑色, 400 点)

基本的に Greedy にやればよさそうなのに、意外とやりづらい問題。基本に忠実にやれば解ける! 問題へのリンク 問題概要 文字 '0', '1', '?' のみからなる文字列 が与えられる。 中の各 '?' をそれぞれ '0' または '1' に置き換えて得られる文字列を二進法表…

AtCoder ABC 009 D - 漸化式 (試験管黄色)

AND と XOR は、それぞれ「掛け算」と「足し算」に対応するので、行列累乗が使える! 問題へのリンク 問題概要 個の整数の組 と が与えられる。 数列 は次の漸化式で定義される。 () AND XOR AND XOR ... XOR AND () の値を求めよ。 制約 考えたこと AND は…

AtCoder ABC 300 C - Cross (茶色, 300 点)

実装が難しい系。僕は DFS をした。「島の個数」を数える問題なので、何も考えずに DFS すればいいと思った。 問題へのリンク 問題概要 下図のような のグリッドの入力が与えられる。 「# で作られた x の形からなる島」が何個あるかを、島の大きさごとに答…

AtCoder ABC 300 F - More Holidays (青色, 500 点)

二分探索すれば楽できることをすぐに思いつけてよかった。 問題へのリンク 問題概要 o と x のみからなる長さ の文字列 が与えられる。 文字列 を 回繰り返して得られる文字列 を考える。この文字列 に対して、最大 回まで、x を o に書き換える操作を行うこ…

AtCoder ABC 300 Ex - Fibonacci: Revisited (銅色, 600 点)

「TDPC T - フィボナッチ」の亜種とも言える問題ですね。 問題へのリンク 問題概要 () によって定義される数列を考える。 整数 が与えられので、 AND を満たすすべての非負整数 に対する の総和を 998244353 で割った余りを求めよ。 制約 考えたこと この問…

AtCoder ABC 299 C - Dango (灰色, 300 点)

「要するに o の最長連続箇所を求めればいい (ただし例外あり)」って感じに、シンプルに整理する力が問われる問題! 問題へのリンク 問題概要 正の整数 に対して、 レベル のダンゴ文字列とは、以下の条件を満たす文字列である。 o と - からなる長さ の文字…

AtCoder ABC 283 Ex - Popcount Sum (橙色, 600 点)

floor sum と聞いて!! 問題へのリンク 問題概要 以上 以下の整数のうち、 で割って 余るものを考える。そのような整数の popcount 値の総和を求めよ。 ( ケース与えられる) 制約 考えたこと TL を見て、floor sum と知った上での考察。 「popcount の総和…

AtCoder ABC 281 F - Xor Minimization (青色, 500 点)

数列に対して、2 進法で表して、再帰的に上位桁から 0 と 1 で分類した木を作る!!! こどふぉではよく見るやつですね。 問題へのリンク 問題概要 個の非負整数 が与えられる。ある非負整数 を上手に選んだときの、 の値の最小値を求めよ。 制約 考えたこと…

JOIG 2021 C - イルミネーション 2 (AOJ 0703, 難易度 4)

落ち着いて整理して考えましょう。問題自体は「累積和」が使える良い問題ですね! 問題へのリンク editorial 問題概要 個の電球を一列に並べていて、オンオフ状態が であるような状態を作りたいとします。ただし は 番目の電球をオンにしたいことを表し、 は…

EDPC (Educational DP Contest) W - Intervals

まさに、「DP 配列をセグメント木に載せる」というセグ木上の in-place DP ですね!!! 問題へのリンク 問題概要 0 と 1 のみからなる長さ の文字列を 0-1 文字列と呼ぶことにします。 今、文字列中の 個の連続する区間 ( 番目の区間を とします) が与えら…

AtCoder ABC 213 A - Bitwise Exclusive Or (100 点)

XOR は 2 回やると元に戻る!!!(素振り!) 問題へのリンク 問題概要 非負整数 が与えられます。 ^ = を満たす整数 を求めてください。 制約 XOR とは XOR 演算は、AND と OR と同じく、ビット (整数) 同士で定義される演算です。ビットについては次の記事…

Codeforces Round #557 (Div. 1) D. Palindrome XOR (R2400)

面白かった。重み付き Union-Find を使った。 問題へのリンク 問題概要 0 と 1 と ? のみからなる長さ の文字列 が与えられる。先頭の文字が 1 であることが保証されている。 以下の条件を満たす整数の組 () の個数を求めよ。 はともに回文数である (11 や 1…

Codeforces Round #673 (Div. 1) C. XOR Inverse (R2000)

バチャ中に TLE が取れなかった... で実装してしまっていたけど、 にする必要があったみたい。 問題へのリンク 問題概要 長さ の 0 以上の整数からなる数列 が与えられる。 0 以上の整数 を適切に定めて XOR で定まる数列 の転倒数が最小となるようにせよ。…

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

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

AOJ 3213 Xor Mart (OUPC 2020 E)

半分全列挙 + Binary Trie!! あるいは、Binary Trie 自体を意識しなくても、上の位から順に桁 DP 的発想で考えていると、それが自然に Binary Trie 上の探索そのものとみなせる! すごくいい Binary Trie の経験になった!! 問題へのリンク editorial 問…