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

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

条件の言い換え

AtCoder ARC 104 C - Fair Elevator (黄色, 600 点)

コーナーケースがえぐい!! 僕は最初、(1, -1), (-1, 3) で Yes を返してしまっていた。 問題へのリンク 問題概要 個の区間 があって、 両端の座標は のいずれか 両端の座標をかき集めたとき、重複がない 区間 と区間 がもし重なっているならば、区間 の長…

AtCoder ARC 104 B - DNA Sequence (茶色, 400 点)

Zero-Sum Ranges だった!!! 問題へのリンク # 問題概要 'A', 'G', 'C', 'T' からなる文字列 が相補的であるとは、 を並び替えてできる文字列 が存在して、 T[ i ] = 'A' ならば T'[ i ] = 'T' T[ i ] = 'T' ならば T'[ i ] = 'A' T[ i ] = 'G' ならば T'[…

Codeforces Grakn Forces 2020 G. Clusterization Counting (R2700)

めちゃ好きだけど、実装重い 問題へのリンク 問題概要 頂点の重み付き無向完全グラフが与えられる。各 に対して、 頂点集合を 個の互いに disjoint な集合に分割する方法であって どの同族辺 (両端点が同一のグループに属する辺) の重みも、どの異族辺 (両端…

Codeforces Grakn Forces 2020 E. Avoid Rainbow Cycles (R2400)

むずかしい 問題へのリンク 問題概要 長さ の数列 と、長さ の数列 が与えられる。これらはある操作のコストを決めるためのパラメータである。 さらに、 系列の数列が与えられる。 番目の数列の項数は で与えられる 数列の各項 は 以上 以下の値である 今、…

AtCoder ABC 179 C - A x B + C (灰色, 300 点)

でもできる! 問題へのリンク 問題概要 正の整数 が与えられる。 を満たすような正の整数 の組の個数を求めよ。 制約 考えたこと こういう整数問題は、実のところ本当に整数論的考察を必要とするパターンは少なくて、大抵は探索ベースの解法が有効になる!!…

AOJ 3184 Hokkaido High School (HUPC 2020 day3-M)

比較的簡単枠だとは思っていたけど、B よりも解かれたのはびっくり! 問題へのリンク 問題概要 北海道高校には 個の科目があり、それぞれ 1, 2, 3 の 3 段階で成績がつけられる。 各生徒の成績は長さ の文字列で表される 生徒 が生徒 の「上位互換」であると…

AOJ 3177 Painting (HUPC 2020 day3-F)

こういうの楽しいよね! 問題へのリンク 問題概要 個のマスが横一列に並んでいます。各マスは赤、青、黄、緑のいずれか 1 色で塗られている ("RBYG" からなる長さ の文字列 で与えられる)。 以下の操作を好きな順序で好きな回数だけ行えます。文字列 を作る…

AOJ 3178 Katsusando (HUPC 2020 day3-G)

いわゆる区間分割する系の DP。こういう系は高速化を要求するタイプの問題が多いけど、今回は素直な二乗 DP で OK! 問題へのリンク 問題概要 直線上にカツが 個ある。 個目のカツは位置 にあり、その重さは である。これらのカツを、次のようにしてすべて回…

AtCoder ABC 175 D - Moving Piece (水色, 400 点)

異様に難しかった!! 問題へのリンク 問題概要 の順列が与えられる。 順列の中の i から P[ i ] へ移動するとき、C[ P[ i ] ] だけスコアが加算される。 出発点を自由に選んで 回以上 回以下の移動を行うとき、得られるスコアの最大値を求めよ。 制約 考え…

AtCoder ABC 171 F - Strivore (青色, 600 点)

実は、元の文字列の形はどうでもよくて、文字列の長さだけが重要という!!! 問題へのリンク 問題概要 長さ の英子文字からなる文字列 が与えられる。これに以下の操作をちょうど 回行ってできる文字列が何通り考えられるか、1000000007 で割ったあまりを求…

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 AGC 043 D - Merge Triplets (橙色, 1200 点)

めちゃくちゃ楽しかった 問題へのリンク 問題概要 長さ の数列を 個用意する。ただしこれらのなす 個の値は が 1 個ずつ登場するようにする。これらの数列から以下の操作を繰り返して、長さ の順列を作る。 空にならずに残っている数列のうち、先頭の要素の…

AtCoder AGC 043 C - Giant Graph (赤色, 900 点)

これはマジで天才やと思うやが... いや本当にどこから Grundy 数を導けるのか、わからぬ... 問題へのリンク 問題概要 頂点数 のグラフが 3 つ与えられる。それらのグラフのカルテシアン積を考える。この頂点数 のカルテシアングラフの独立集合のうち、以下の…

AtCoder AGC 043 A - Range Flip Find Route (緑色, 400 点)

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

Codeforces Round #625 (Div. 1) D. Reachable Strings (R2500)

まさか残り 25 分で通し切れるとは思わなかった! 問題へのリンク 問題概要 長さ の '0' と '1' のみからなる文字列 が与えられる。以下の 個のクエリに答えよ 各クエリは left, right, len からなる 部分文字列 A = S[left : left + len], B = S[right: rig…

Codeforces Round #625 (Div. 1) A. Journey Planning (R1400)

面白かった 問題へのリンク 問題概要 要素の数列 が与えられる。以下の条件を満たすような部分数列のうち、要素和の最大値を求めよ。 抜き出した数列のどの 2 項についても「値の差分」と「index の差分」とが等しい 制約 考えたこと たとえば の場合は、こ…

フォルシアゆるふわ競プロオンサイト #3 F - Yet Another Cake Division locked

面白かった 問題へのリンク 問題概要 の盤面の各マスを T, M, N, P の四色に塗る方法のうち、以下の条件を満たすものが何通りあるか、1000000007 で割ったあまりを求めよ。 どの T マスと M マスについても、M マスは T マスから見て strict に右にあるか、s…

第5回 ドワンゴからの挑戦状 本選 2019 B - XOR Spread (800 点)

操作を言い換えるところは楽しいけど、BinaryTrie が必要ということで、必死に整備した。 問題へのリンク 問題概要 要素の非負整数列 が与えられる。以下の操作を好きな回数だけ行える。行なった結果得られる数列のうち、辞書順最小のものを求めよ。 index …

AtCoder AGC 006 C - Rabbit Exercise (赤色, 800 点)

操作を 回行った結果を求める系、苦手意識あるけど克服したい! 問題へのリンク 問題概要 と番号の振られた 個のボールがあって、初期状態ではそれぞれ の位置にある。以下の操作を 回行う。最終的な各ボールの座標の期待値をそれぞれ求めよ。 各操作は 個の…

CADDi 2018 F - Square (橙色, 900 点)

面白かった 問題へのリンク 問題概要 の盤面の各マスを 0 か 1 かで埋めたい。すでに 個のマスについては数字が埋まっている。以下の条件を満たすように残り マスを埋める方法は何通りあるか、998244353 で割ったあまりで求めよ。 一辺の長さが 2 以上な部分…

AOJ 2581 完全順列 / Derangement (RUPC 2014 day3-G)

今の RUPC / AUPC の先駆けとなった合宿の北大セットの問題!!! このセットは、全問題のタイトルの頭文字が 'D' というセットだった セットへのリンク 北大アーカイブへのリンク 問題へのリンク 問題概要 長さ の順列 が与えらえる。これらを並び替えて完…

Educational Codeforces Round 74 F. The Maximum Subtree (R2300)

木 DP シリーズ!!! 問題へのリンク 問題概要 区間グラフとは、 個の区間が与えられたときに、各区間を各頂点に対応させ、intersection がある区間同士に辺が張られたようなグラフのことである。 さて、 頂点の木が与えられる。この木の連結な部分グラフ (…

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

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

AOJ 2630 Dictionary (JAG 夏合宿 2014 day2-B) (550 点)

最初は「え!? i 行目の文字列情報がないと i+1 行目以降のことを考えられなくない?」となってしまって、途方に暮れてしまった 問題へのリンク 問題概要 個の文字列 があって、それぞれいくつかの文字は '?' で隠されている (したのは の例) '?' 全体をア…

CODE FESTIVAL 2016 qual A D - マス目と整数 / Grid and Integers (橙色, 800 点)

800 点埋めをしていく!!! 問題見て、コーナーケース怖い系かな...と思ったけど、ちゃんと一発で通せてよかった 問題へのリンク 問題概要 行 列のマス目があって、以下の条件を満たすように各マスに整数値を書き込みたい (整数値を とする): どのマスの数…

Codeforces Round #614 (Div. 1) A. NEKO's Maze Game (R1400)

いくらなんでも 2 分で解ける問題とは思えないのですが... 問題へのリンク 問題概要 2 × N のグリッドが与えられる。最初はグリッドのマスはすべて「通路」の状態であって、マス (1, 1) からマス (2, N) に到達することができる。以下の q 個のクエリに答え…

Codeforces Round #614 (Div. 1) C. Xenon's Attack on the Gangs (R2300)

面白かった!!!こういうのを確実に通せるようにならないと!!! 問題へのリンク 問題概要 頂点の木が与えられる。木の各辺を のラベルをつける方法のうち、 の値の最大値を求めよ。ただし は、2 頂点 を結ぶパスに含まれる辺の値の集合を考えたときに、そ…

キーエンス プログラミング コンテスト 2020 D - Swap and Flip (青色, 700 点)

隣接 swap 操作を行いながら最小回数でソートする系の問題は、過去に何度も出てる!!! drken1215.hatenablog.com drken1215.hatenablog.com これらはいずれも自然に DP で解くことができる。今回も。なお、「どれを表にするかを決め打って転倒数を求める」…

Educational Codeforces Round 80 F. Red-Blue Graph (R2900)

需要供給を考え、さらに最小流量制約もある最小費用フロー!!! 問題へのリンク 問題概要 左頂点数 、右頂点数 、辺数 の二部グラフが与えられる。各頂点は「赤」または「青」または「白」に塗られている。 さて、各辺は最初は白色である。そのうちの何本か…

yukicoder No.968 引き算をして門松列(その3)

その 2 と雰囲気は似ているけど、一気に考えづらくなった! 問題へのリンク 問題概要 3 つの整数 の組が門松列であるとは、以下の条件を満たすことである。 は互いに相異なる のいずれかが、3 整数の中で 2 番目に大きな値となっている 以下のクエリに 回答…