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

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

Codeforces

Codeforces Round 897 (Div. 2) D. Cyclic Operations

Functional Graph のサイクル列挙!!! ライブラリ整備したことがあったおかげでライブラリ使えてよかった! 問題へのリンク 問題概要 (意訳) 要素数 の数列 があって、はじめは全要素が 0 となっている。以下の操作を好きな回数だけ行って、数列を の状態…

Codeforces Round 539 (Div. 1) D. Sasha and Interesting Fact from Graph Theory (R2400)

また一つ、プリューファーコードの練習問題が増えた! 問題へのリンク 問題概要 正の整数値 が与えられる。 頂点数 の重み付き木であって、以下の条件を満たすものの個数を 1000000007 で割った余りを求めよ。 各辺の重みは 以上 以下の整数値である 2 頂点 …

Codeforces Round 824 (Div. 2) D. Meta-set (R1700)

なんとか通した。結構迷走した。 問題へのリンク 問題概要 0 と 1 と 2 のみからなる の行列が与えられる。これらの行列のある 3 つの行が good であるとは、「どの列についても、それら 3 行の値がすべて等しいか、すべて互いに異なる」という条件を満たす…

Codeforces Global Round 15 C. Maximize the Intersections (R1800)

企業合コンで解いた。ギャグ系だった。 問題へのリンク 問題概要 円周上に 個の点があって、2 個ずつ 組のペアを作って線分で結ぶ。 すでに 組のペアができていて、線分が結ばれている。残りの点についてペアを作って線分を作っていったときの交差数の個数の…

Codeforces Round 892 (Div. 2) E. Maximum Monogonosity (R??00)

つい最近 CodeQUEEN 決勝 E 問題でも出てきた「最大値の最大化」典型テクニック!!!! 問題へのリンク 問題概要 長さ の 2 つの数列 と が与えられる。今、互いに disjoint な区間群 をとる ( は自由)。ただし、区間の長さの総和がちょうど となるようにす…

Codeforces Round 892 (Div. 2) D. Andrey and Escape from Capygrad (R??00)

区間を整理する考え方が楽しかった。 問題へのリンク 問題概要 下図のように 組の「黒い区間」と「赤い区間」がある。赤い区間は黒い区間に完全に包含されている。 この区間上でコマを動かしていく。コマが 番目の黒い区間の内部にあるとき、 番目の赤い区間…

Educational Codeforces Round 9 C. The Smallest String Concatenation (R1700)

すごくシンプルな面白い問題。 問題へのリンク 問題概要 個の文字列 が与えられる。 これらを並び替えて連結して 1 つの文字列を作る。作れる文字列のうち、辞書順最小のものを求めよ。 制約 解法 単純に を辞書順にソートして、小さい順に連結するのでは反…

Codeforces Round #557 (Div. 1) C. Thanos Nim (R2000)

面白かった! 問題へのリンク 問題概要 個の石の山がある ( は偶数)。 番目の山には 個の石がある。先手と後手が交互に以下の操作を行う。操作できなくなった方が負けである 石の山のうち、まだ石が 1 個以上残っている山をちょうど 子選ぶ そのそれぞれの山…

Codeforces Round #557 (Div. 1) B. Chladni Figure (R1900)

KMP 法で殴ったけど、愚直にやっても調和級数的計算量で間に合うね。 問題へのリンク 問題概要 円周上に等間隔に 個の点が打たれている。これらの点を端点とした 個の線分がある (下図のような感じ)。 これが回転対象性をもつかどうかを判定せよ (1 周未満の…

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

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

Codeforces Round #673 (Div. 1) D. Graph and Queries (R2600)

いろんな方法がありそう。Union-Find のマージ過程を表す木でやったけど、ほかにも Undo 付き Union-Find を使うなど 問題へのリンク 問題概要 頂点数 、辺数 のグラフが与えられる。初期状態では各頂点に という値がついている (すべて 1 以上で disjoint)…

Codeforces Round #673 (Div. 1) B. Make Them Equal (R2000)

こどふぉ特有の 回以下の操作で〜を達成せよ、という問題 問題へのリンク 問題概要 長さ の正の整数からなる数列 が与えられる。以下の操作を 回以下繰り返すことで、数列の値がすべて等しくなるようにしたい。そのような操作列を一つ求めよ。不可能である場…

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

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

Codeforces Global Round 12 E. Capitalism (R2700)

なんとなくできそうだけどできないみたいな問題だった。そうか、牛ゲーに帰着すれば明快だ... 問題へのリンク 問題概要 頂点数 、辺数 の連結グラフが与えられる。いくつかの辺は無向辺であり、いくつかの辺は有向辺である。 各頂点 に 0 以上の整数値 を割…

Codeforces Global Round 12 F. The Struggling Contestant (R2400)

こういう個数合わせ系の問題は実は得意かもしれない 問題へのリンク 問題概要 長さ の数列 が与えられる。これに対して の順列 であって、 のどの隣接する二項も同じ数値でないようなものを考える。 そのような順列 のうち、 を満たさない の個数の最小値を…

Codeforces Global Round 12 H1. Multithreading (Easy Version) (R2900)

ぷよぷよみたいに 2 つ揃うと消えるような対象物の数え上げ問題。これを思い出した drken1215.hatenablog.com 問題へのリンク 問題概要 (意訳) "B", "W", "?" のみからなる長さ の文字列が与えられる ( は偶数)。"?" に "B", "W" を割り当てる方法のうち、"B…

Codeforces Global Round 12 D. Rating Compression (R1800)

頑張った 問題へのリンク 問題概要 正の整数のみからなる長さ の数列 が与えられる。各 に対して、以下の問に答えよ。 数列 を左から順に「連続する 個の最小値」をとっていってできる長さ の数列が、 の順列になっているかどうかを判定せよ。 制約 の総和 …

Codeforces Global Round 12 C2. Errich-Tac-Toe (R2300)

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

Codeforces Round #683 (Div. 1) D2. Frequency Problem (R3000)

平方分割で解法を分岐する系の問題で、そのうちの片方の問題は Easy Version として D1 で出題されてた (Easy Version は R2600) 問題へのリンク 問題概要 正の整数 が与えられる。 以上 以下の整数のみからなる 要素の数列 が与えられる。 数列の連続する区…

Codeforces Round #683 (Div. 1) C. Xor Tree (R2100)

こどふぉのこの回、いい問題が多かった気がするので解き直し。最上位の桁から順に見ていって、0 と 1 とに分類していって...とするのはよく見る気がする!!! 問題へのリンク 問題概要 どの要素も互いに相異なる非負整数列 が good であるとは、以下の条件…

Codeforces Round #683 (Div. 1) B. Catching Cheaters (R1800)

結構悩んだ!!! 問題へのリンク 問題概要 長さ の文字列 と、長さ の文字列 が与えられる。 の連続する部分文字列 と、 の連続する部分文字列 をとったとき、 とする。 の考えられる最大値を求めよ。 制約 考えたこと 単純にそれぞれの部分文字列を探索し…

Codeforces Round #687 (Div. 1) C. New Game Plus! (R2200)

すごい面白い!! 問題へのリンク 問題概要 体の敵がいて、敵に付随するスコアはそれぞれ で与えられる (負数になることもある)。 これらの敵を順に倒していきたい。Boss Score, Total Score と呼ばれる値が初期状態ではともに 0 となる。敵 を倒すとき、次…

Codeforces Round #687 (Div. 1) B. XOR-gun (R2000)

こどふぉ特有の、ややギャグ要素ありの楽しい問題。結構好き。 問題へのリンク 問題概要 長さ の正の整数からなる広義単調増加な数列 が与えられる。以下の操作を何度か行うことで、広義単調増加ではない状態にしたい。 数列の隣接する 2 つの要素を選んで、…

Codeforces Round #687 (Div. 1) A. Bouncing Ball (R1400)

個置きに累積和をとるの、3 ヶ月前の僕だったら思いつかなかったかもしれない。 問題へのリンク 問題概要 整数 が与えられる。また、長さ の 0 と 1 のみからなる文字列 が与えられる。文字列 に対して以下の操作を行うことができる。 文字列 中の文字 "0" …

Codeforces Round #684 (Div. 1) B. Graph Subset Problem (R2600)

TLE が厳しくて話題になってた 問題へのリンク 問題概要 頂点数 、辺数 の単純無向グラフ [tex G] が与えられる。また、正の整数 が与えられる。 以下のいずれかの条件を満たすものが存在するかどうかを判定し、存在するならばそれを出力せよ。 type 1: の…

Codeforces Round #682 (Div. 2) C. Engineer Artem (R2000)

グリッドグラフは二部グラフ!!! 問題へのリンク 問題概要 のマス目に整数値 (マス には ) が書かれている。 各マスについて、「元の整数値のままにする」または「元の整数値に 1 を足したもの」をすることによって、どの隣接する 2 マスの値も互いに相異…

Codeforces Round #681 (Div. 1) E. Black, White and Grey Tree (R3000)

最初まんまと罠にひっかかった 問題へのリンク 問題概要 頂点数 の木が与えられる。各頂点には 0, 1, 2 のいずれかの色 (0: 灰色, 1: 白色, 2: 黒色) が割り振られている。以下の操作を最小回数行うことで、木を消滅させたい。最小回数を求めよ。 [操作]:残…

Codeforces Round #681 (Div. 1) D. Sum (R2800)

から落とせる気がまったくしなかった... 問題へのリンク 問題概要 個の広義単調増加数列 が与えられる。 それぞれの数列から、先頭から 個ずつとってきた値の総和の最大値を求めよ。ただし でなければならないものとする。 制約 考えたこと 個数に関する con…

Codeforces Round #681 (Div. 1) C. Graph Transpositions (R2400)

AOJ-ICPC みを感じる! 問題へのリンク 問題概要 頂点数 、辺数 の有向グラフが与えられる。頂点 1 から頂点 へとたどり着きたい。以下の 2 種類の操作ができる。 頂点 上にいるとき、辺 をたどって、頂点 へと移動する 移動に要するコストは 1 任意の頂点に…

Codeforces Round #681 (Div. 1) B. Identify the Operations (R1800)

どんな風に操作しようとも、毎回「左右のうちの何個選べるか」が変わらない!! 問題へのリンク 問題概要 の順列 と、空の配列 が与えられる。これらに対して以下の操作を 回行うことで、配列 が に一致した状態にしたい。 そのような操作方法が何通りあるか…