辞書順最小と言われたら......！！ 問題へのリンク 問題概要 文字 'd', 'p' からなる長さ の文字列 が与えられる。 この文字列のある区間をとって、その区間を 180 度回転させる（reverse した上で、'd' と 'p' を入れ替える）。 こうしてできる文字列のうち…

文字列の各文字について処理していく問題 問題へのリンク 問題概要 文字 '0' と '1' からなる文字列 が与えられる。 の各文字について、'0' を '1' にして、'1' を '0' にして出力せよ。 考えたこと for 文を用いて、文字列 の各文字 S[i] について、 S[i] …

「集計処理」の基本問題！ 問題へのリンク 問題概要 (意訳) 個の LED が最初はすべて光っている。 回の処理を行う。 回目の処理では 番目の LED の状態を flip する (光っていたら消して、消えていたら光らせる)。 最終的に何個の LED が光っているかを求め…

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

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

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

ネットワークフローアルゴリズムの構造をちゃんと理解しているかを問う良問ですね！！ 問題へのリンク editorials 問題概要 頂点数 、辺数 の有向グラフ と、2 頂点 が与えられます。 いま、グラフの辺を 1 本選んで向きを反転させます。それによって、- 間…

これ好き！ 問題へのリンク 問題概要 のグリッドがあって、"." と "O" と "X" のいずれかが描かれている。"O" または "X" の描かれているマス目の個数を とする。 今、いくつかのマスに対して、"O" または "X" のマス目の "OX" を入れ替える操作を行う。それ…

幅が小さいので、幅についての 通りの探索が間に合う！ 問題へのリンク 問題概要 のマス目がある。各マスの値は 0 または 1 である。次の操作を好きな順序で好きな回数だけ行うことができる。 ある行を選択して、その行の数値をすべてひっくり返す (0 を 1 …

簡単なバグを埋め込んでしまった... 問題へのリンク 問題概要 長さ の "0" と "1" のみからなる 2 つの文字列 が与えられる。 に対して以下の操作を繰り返し行うことで に一致させることができるかどうかを判定し、可能ならば最小回数を求めよ。 中の "01" …

早速遅延セグ木があればできる問題来た！！ AC Library の出番かと思った！！！ 問題へのリンク 問題概要 縦 マス、横 マスのグリッドがあり、はじめグリッドの中央 マスには黒い石が 1 個ずつ置いてあり、下辺と右辺の計 マスには白い石が 1 個ずつ置いてあ…

こういう系すごく楽しいよね 問題へのリンク 問題概要 頂点数 、辺数 の重み付き有向単純グラフ が与えられる。 このグラフ上で次の条件を満たすパス (同じ頂点を二度通らないものに限る) が存在するかどうかを判定し、そのようなパスの重みの最小値を求めよ…

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

「予め盤面をいじることができる」という設定の問題にはある程度の定石があるように思う！ 問題へのリンク 問題概要 の盤面が与えられ、左上から右下まで行きたい。'#' マスは壁を表し、'.' マスは通路を表す。 予め盤面に以下の操作を行うことができる。最…

面白かった 問題へのリンク 問題概要 長さ の整数列 が与えられる。 長さ の 0 と 1 からなる文字列 に対して定まる関数 は次のようになっている。 は、次のようにして文字列 を文字列 に一致させるのに必要な最小コストとする。 回目の操作で、 の文字 を選…

とにかく重たい... 問題へのリンク 問題概要 頂点のツリーが与えられる。各頂点には「白」か「黒」の色が塗られている。好きな頂点から開始して 今いる頂点の色を flip する 隣接する頂点を 1 つ選んで移動して、その頂点の色を flip する といういずれかの…

区間反転操作問題シリーズ！！！ それにしてもいろんな見方ができる問題な気がする。 問題へのリンク 問題概要 長さ の 'B', 'W' からなる文字列 があたえられる。今この文字列に 回の操作を行う。 まだ選んでいない 2 マス を選んで区間 [ ] の 'B' と 'W' …

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

一見複雑だけど、実質 2 通りしかないというやつ 問題へのリンク 問題概要 長さが の 0-1 列が与えられる。何個かについて 0 と 1 を入れ替えることで、 0 と 1 が交互に並んでいる状態 にしたい。そのようなことが可能な方法のうち、入れ替える数字の個数の…

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

一瞬罠があるのではと怖くなるやつ 問題へのリンク 問題概要 'W' と 'B' で構成された文字列が与えられる。 "BW" を "WB" に置き換える変換を好きな回数行える。最大回数を求めよ。 考えたこと 問題の操作はつまりは 'W' を左に動かす操作と読み替えられる。…

超苦手系。なんとか解けた。 問題へのリンク 問題概要 長さ N のバイナリ列 a, b が与えられる。a に対して 隣接二項を swap する 0 と 1 を反転する の操作を最小回数行って b にせよ。(10 -> 01 なら 1、1000 -> 0001 なら 2) 制約 1 <= N ,= 106 考えたこ…

本番中なんとか解けたけど、すごくグチャグチャしたん。 問題へのリンク 問題概要 すぬけ君は、 日間にわたって、毎日次のようなパズルを解こうとしている。 すぬけ君の持っている端末に、縦 行、横 列からなる格子状の盤面が毎日配信されてくる。それぞれの…

こうきさんに聞いて解いてみた。 木を最小個数のパスで被覆する問題はとりあえず2種類あって、辺の重複ありの場合は昨日のCSA 069 D. Cover the Treeで適切に葉同士で繋ぐ感じにする。辺の重複無しの場合は奇数次の点に適当に辺を張ってオイラー閉路作って切…

まさにこれだったん。 CSA 069 DIV2 C Build Correct Brackets ()()))(())() のようなカッコ列が与えられる。 最小回数flipして正しいカッコ列にせよ。 また最小回数flipで正しいカッコ列にする方法の数を数え上げよ。 ・1 <= 文字列長 <= 2500 まさに最短路…