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

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

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

第一回日本最強プログラマー学生選手権-予選- 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 っぽく にはなるな...なんて思っていたけどそこから落とせなかった...いやこれ何を食べたらこんな二分探索思いつけるようになるの!?!?!?!??? なにかこういう場面で二分探索すると上手く行くよ、というパターン的なものが…