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

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

ランレングス圧縮

JOIG 2024 C - 座席 2 (難易度 6)

色んな解法が考えられそうな問題で、ドツボにハマりやすくて危険な問題だったと思う。落ち着いて整理してシンプルに考える力が問われる。実は、二分探索などは必要ない問題である。 問題へのリンク editorial 問題概要 人の選手 がいる。選手 の出身国は で…

AtCoder ABC 329 C - Count xxx (灰色, 300 点)

ランレングス圧縮の典型題! なお、ランレングス圧縮は鹿本でみっちり解説している。 問題へのリンク 問題概要 英小文字のみからなる長さ の文字列 が与えられる。 の連続する部分文字列のうち、1 種類の文字のみからなる文字列の種類数を答えよ。 制約 考え…

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

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

AtCoder ABC 213 F - Common Prefixes (黄色, 500 点)

これを機会に SA-IS を整備した! 今回の記事はあくまで自分が読んでわかる以上を目指さない備忘録として。 問題へのリンク 問題概要 2 つの文字列 に対して「先頭何文字が一致しているか」を と表すことにします。 長さ の文字列 が与えられます。 の 文字…

AtCoder ABC 136 D - Gathering Children (茶色, 400 点)

「大体こういう感じ」というところまではすぐに見えるけど、細かいところを詰めるのが大変な問題かもしれない。 問題へのリンク 問題概要 マスがあって、各マスには "L" または "R" が書かれている (左端は "R" で右端は "L" であることが保証される)。また…

JOI 予選 2009 C - 連鎖 (AOJ 0534, 難易度 6)

いろんな実装方法がありそう。でも が間に合うので、すべての書き換え方法について でできるなら十分。 問題へのリンク 問題概要 1 と 2 と 3 のみからなる長さ の数列が与えられる。同じ数値が 4 個以上連続することはない。 この数列のうちの 1 箇所の値を…

AtCoder ABC 185 D - Stamp (茶色, 400 点)

番兵を入れるとかすれば、怖いケースをあらかじめ除去できそう 問題へのリンク 問題概要 左右方向一列に 個のマスが並んでいます。 この 個のマスのうち、マス の 個のマスは青色で、それ以外のマスは白色です。 あなたは一回だけ、正整数 を一つ選んで幅 の…

AtCoder AGC 039 A - Connection and Disconnection (茶色, 300 点)

区間分割して考える系、AGC-A にめちゃくちゃ多いね 問題へのリンク 問題概要 文字列 が与えられる。 を 回繰り返してできる文字列を とする。 の文字をひとつ選んで他の文字に書き換える操作を繰り返すことで T のどの隣り合う 2 文字も相異なるようにする…

CPSCO2019 Session4 D - Boring Sequence (400 点設定)

一目二分探索ゲーだし、実際二分探索で解けるのだけど、実はもっとすごく楽に解ける!! 問題へのリンク 問題概要 長さ の整数列 が与えられる。数列の退屈さとは「同じ値が連続している区間の長さの最大値」として定義する。 与えられた数列において、最大…

CPSCO2019 Session4 E - ox Concatenation (600 点設定)

これすごく好き!!!普通に難しい。 問題へのリンク 問題概要 'o' と 'x' のみからなる長さ の文字列 を作りたい。部品として使えるのは以下のものたち ( となっている)。 "ox" が 個 "xo" が 個 "o" が 個 "x" が 個 これらを適切な順序で concat すること…

AtCoder ABC 140 D - Face Produces Unhappiness (緑色, 400 点)

ABC では数少ない発想力系。 問題へのリンク 問題概要 L と R から成る 文字の文字列 が与えられる。文字列のスコアは次のようにして決められる。 各 index i について S[ i ] = 'L' ならば、i + 1 >= 0 かつ S[ i - 1 ] = 'L' のときに限り、1 を加算 S[ i …

AtCoder ABC 149 D - Prediction and Restriction (茶色, 400 点)

ちょっと問題を理解するのが大変かもしれない 問題へのリンク 問題概要 ロボットと 回ジャンケンをする。ロボットの出す手はあらかじめすべてわかっている。 グーを出して勝つと 点 チョキを出して勝つと 点 パーを出して勝つと 点 が得られる。ただし 回目…

AtCoder ABC 122 B - ATCoder (灰色, 200 点)

E8君問題集第3問! 問題へのリンク 問題概要 長さ の文字列 が与えられる。 の連続する部分列であって、'A', 'C', 'G', 'T' のみからなる部分の長さの最大値を求めよ。 制約 考えたこと が小さいので、全部調べても間に合う。連続する部分列は 個ある。 それ…

AtCoder AGC 016 A - Shrinking (緑色, 300 点)

一瞬コーナーケースがないかと怖くなる 問題へのリンク 問題概要 長さ の文字列 が与えられる。この文字列に対し、以下の操作を好きな回数だけ行うことができる。文字列を「単一の文字からなる状態」にするのに必要な操作回数の最小値を求めよ。 文字列の各…

Codeforces Round #489 (Div. 2) D. Nastya and a Game (R2100)

方針立ってからも、ちょっと実装辛い ^^; 問題へのリンク 問題概要 長さ の正の整数列 と、正の整数 が与えられる。 正数列の連続する部分列であって、その積が、和の 倍となっているものが何通りあるかを求めよ。 制約 考えたこと パッと思うことは、積の中…

Judge System Update Test Contest 202004 D - Calculating GCD (400 点)

面白かった 問題へのリンク 問題概要 要素からなる正の整数列 が与えられる。以下の 個のクエリに答えよ 各クエリは整数 が与えられる の順に、 という更新を行う 初めて となる瞬間の を求めよ 最終結果が 1 より大きいときは、その値を答えよ 制約 解法 (1…

AtCoder AGC 003 B - Simplified mahjong (水色, 400 点)

微妙なコーナーケースに注意 問題へのリンク 問題概要 の書かれたカードがそれぞれ 枚ある。以下の条件を満たすようにペアリングしていくとき、最大で何組できるか? ペアとなるカードの数値の差は 1 以下 制約 考えたこと 一瞬、 値が等しいペアを作れるだ…

CODE FESTIVAL 2017 qual C C - Inserting 'x' (緑色, 400 点)

少しでも実装を楽にしたい 問題へのリンク 問題概要 英小文字のみからなる長さ の文字列 が与えられる。以下の操作を最小回数行って回文にしたい。その最小回数を求めよ。不可能な場合は -1 を出力せよ。 のどこかに 'x' を挿入する 制約 考えたこと まず可…

Educational Codeforces Round 74 D. AB-string (R1800)

面白かった 問題へのリンク 問題概要 文字列 が good であるとは、 の連続部分文字列であって回文であるような区間をすべてとってきたときに、それらによって が被覆されることをいう。たとえば "aaba" は、"aa" と "aba" によって被覆されるので good であ…

DISCO ディスカバリーチャンネル 2020 予選 D - Digit Sum Replace (青色, 500 点)

すごく面白かった! 問題へのリンク 問題概要 ある数値が与えられる。ただしその数値は非常に桁数が大きいことがあるので、数値を 10 進法で表したときの文字列をランレングス圧縮した状態で与えられる。具体的には 組の値 が与えられて、 の順に、数値 が …

AtCoder ABC 143 C - Slimes (灰色, 300 点)

区間ごとに分割していく処理は、ものすごく大事な典型処理なので、是非ともテンプレ化してノータイムで書けたらすごくいい感じ!!!!! 問題へのリンク 問題概要 "aabbbbccbaaa" のような長さ N の文字列 S が与えられる。同じ文字が連続している区間が何…

AtCoder ABC 127 D - Integer Cards (緑色, 400 点)

混ぜてソートは賢すぎる!!!惚れた!!! 問題へのリンク 問題概要 枚のカードにそれぞれ の数値が書かれている。あなたは、 について順に以下の操作を 1 回ずつ行います。 カードを 枚まで選ぶ(0 枚でもよい)。選んだカードに書かれている整数をそれぞれ …

AtCoder AGC 011 D - Half Reflector (赤色, 900 点)

この問題が解けた勝因は、「実験しよう」と思えたことな気がする。 問題へのリンク 問題概要 高橋君は,ある特殊な装置をたくさん持っています. この装置は筒状で,左右からボールを入れることができます. また,この装置には 2 種類の状態 A, B がありま…

diverta 2019 E - XOR Partitioning (橙色, 800 点)

時間かかりすぎた。シンプルで面白い。 問題へのリンク 問題概要 要素からなる 0 以上の整数列 が与えられる。 これをいくつかの連続した部分列に分割する 通りの方法のうち、各連続区間の XOR 和が互いに等しくなるものが何通りあるか、1000000007 で割った…

AtCoder ABC 124 D - Handstand (緑色, 400 点)

これ...以前 Twitter につぶやいた問題とよく似てた!!! 400 点くらいの問題【問題】N 要素の 0 と 1 から成る数列が与えられる。以下の操作を最大 K 回行なって錬成し得る数列が何通りあるか 10e9 で割った余りを求めよ「数列の連続する区間を選んで 0 と…

AtCoder ABC 116 C - Grand Garden (茶色, 300 点)

整理するのがちょっと大変系。でもとても教育的だと思う! 問題へのリンク 問題概要 次元の整数ベクトル () が与えられる。これを以下のようなベクトルの和として表したい。 () のように「」が連続していてそれ以外は になっているベクトル 例えば、(1, 3, 3…

AtCoder AGC 029 C - Lexicographic constraints (黄色, 700 点)

弱かった。。。 問題へのリンク 問題概要 個の正の整数 が与えられる。 文字列の列 であって の文字数が である 辞書式順序で < < < を満たすもののうち、登場文字数の最小値を求めよ。 制約 考えたこと が狭義単調増加だったら、"a" の個数だけで行けるので…