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

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

問題の構造をわかりやすく特徴付ける

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 個ずつ登場するようにする。これらの数列から以下の操作を繰り返して、長さ の順列を作る。 空にならずに残っている数列のうち、先頭の要素の…

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

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

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

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

AtCoder AGC 006 C - Rabbit Exercise (800 点)

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

CADDi 2018 F - Square (900 点)

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

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

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

第6回 ドワンゴからの挑戦状 予選 C - Cookie Distribution (800 点)

これ 81 人も通してるのか... 問題へのリンク 問題概要 人の子供がいる。 日間にわたって、 人の中から 人を一様ランダムに選んでクッキーを与える。 日分のあらゆるクッキーの配り方を考えたときの「各子供の最終的にもらったクッキーの個数の積」の総和を…

ARC 059 F - バイナリハック / Unhappy Hacking (800 点)

面白かった 問題へのリンク 問題概要 長さ の '0' と '1' と 'B' からなる文字列 として、以下の条件を満たすものが何通りあるか、1000000007 で割ったあまりを求めよ。 空文字列に対し、 を左から順に見て、以下の操作を順に行ってえられる文字列が に一致…

第一回日本最強プログラマー学生選手権-予選- C - Cell Inversion (500 点)

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

第一回日本最強プログラマー学生選手権-予選- E - Card Collector (800 点)

マトロイドだ!!!!!!! 問題へのリンク 問題概要 のボード上の 個のコマがあってそれぞれ重みがつけられている。同じマスに複数のコマが置かれていることもある。 今、各行から 1 個以下のコマを取り去る。次に各列から 1 個以下のコマを取り去る。 最…

AtCoder AGC 017 B - Moderate Differences (400 点)

むむむ 問題へのリンク 問題概要 長さ の整数列 であって、 が 以上 以下の整数 となるものが存在するかどうかを判定せよ。 制約 考えたこと とりあえず , としてよい。 さて、 からスタートして、 ターン目にどんなのを作れるかを考察してみる。 1 ターン目…

diverta 2019_2 E - Balanced Piles (800 点)

最初は絶望感がヤバイタイプの問題。とても解ける問題には見えない。でも落ち着くと解ける。 こういう問題を作れるのはすごい。 問題へのリンク 問題概要 個のマスに積み木を重ねていく。最初はどのマスも 0 段である。以下の操作を繰り返して、最終的にすべ…

diverta 2019_2 C - Successive Subtraction (500 点)

復元つらい 問題へのリンク 問題概要 黒板に 個の整数 が書かれている。 書かれている数字から 2 個選んで として、これらを消して を新たに書き加える という操作を 回行って最後に残る整数の最大値を求めよ。またそれを達成する操作列を復元せよ ( を毎タ…

AtCoder ABC 128 F - Frog Jump (600 点)

ジャンプの過程を無視して、最終的に出来上がるものがどうなるかを考えて、それをわかりやすく特徴づける 調和級数になるタイプの全探索 というタイプの問題。結構重たい。AGC なら C 問題でありそう。 問題へのリンク 問題概要 個の地点 にそれぞれ のスコ…

AtCoder ABC 129 E - Sum Equals Xor (500 点)

まさにこの考え方で解ける問題 drken1215.hatenablog.com 今回の問題も桁 DP でもよいのだが、実は桁 DP しなくても解ける。 問題へのリンク 問題概要 正整数 が二進数表記で与えられます。 以下の条件を満たす非負整数 の組がいくつ存在するか求めてくださ…

AtCoder AGC 003 C - BBuBBBlesort! (600 点)

楽しかった 問題へのリンク 問題概要 長さ の数列 が与えられる。どの 2 要素も互いに相異なることが保証される。これに対し 隣り合う 2 要素を swap する 連続する 3 要素を反転する という操作を行ってソートしたい。ただし、1 の使用回数を最小にしたい。…

AtCoder AGC 002 F - Leftmost Ball (1600 点)

すごく楽しかった。 問題へのリンク 問題概要 色 のボールがそれぞれ 個ずつあります。 個のボールを好きな順序で並べ、各色について最も左側にあるボールを色 へと塗り替えました。 最終的な色の並びとして考えられる個数を 1000000007 で割ったあまりを求…

AtCoder AGC E - Go around a Circle (1500 点)

本番これを間に合わせられなかったのが悔しい 問題へのリンク 問題概要 円周を 等分して、それぞれの弧を赤か青に塗る方法のうち、 'R' と 'B' のみからなる長さ の文字列 が与えられて 円周上のどの端点から出発しても弧を順番に左右どちらかに 回たどって…

AtCoder ABC 125 D - Flipping Signs (400 点)

操作をいい感じに言い換える感じ 問題へのリンク 問題概要 個の要素 が与えられる。これに対し、以下の操作を好きなだけ行える。 隣り合う 2 要素をともに -1 倍する 操作後の数列の値の和として考えられる最大値を求めよ。 制約 考えたこと こういう「操作…

AtCoder AGC 032 D - Rotation Sort (1000 点)

本番フローで無理矢理解いた!!! でも DP が本筋だね。 問題へのリンク 問題概要 の順列 が与えらえる。これを 整数 を選んで区間 [ ) を左シフトする、すなわち をそれぞれ へ置き換える、これにコスト がかかる 整数 を選んで区間 [ ) を右シフトする、…

Tenka1 2019 F - Banned X (800 点)

かなり時間かかった 問題へのリンク 問題概要 のみからなる長さ の数列であって、どの連続する部分列に対してもその総和が にならないようなものの個数を 998244353 で割ったあまりを求めよ。 制約 考えたこと 最初は包除原理かな...と思ったけど、どうにも…

AtCoder AGC 026 F - Manju Game (2000 点)

ふと考えてみた。区間 DP っぽく にはなるな...なんて思っていたけどそこから落とせなかった...いやこれ何を食べたらこんな二分探索思いつけるようになるの!?!?!?!??? なにかこういう場面で二分探索すると上手く行くよ、というパターン的なものが…