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

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

数列

AtCoder ABC 130 D - Enough Array (400 点)

超典型的なしゃくとり法そのものだった!!! 問題へのリンク 問題概要 個の整数 があたえられる。数列の連続した区間であって、その総和が 以上となっているものを数え上げよ。 制約 考えたこと しゃくとり法については以前に記事を書いた。 qiita.com この…

AtCoder ABC F - XOR Matching (600 点)

600 点問題ともなると、さすがに正解者数も少ない。 色んな人が色んな構築してそうだけど、僕なりの方法をば。 問題へのリンク 問題概要 を 以上の整数とする。 以上 以下の整数が 2 個ずつあって、これを並べ替えてできる長さ の数列 であって、 となるよう…

AtCoder AGC 001 D - Arrays and Palindrome (1000 点)

楽しかった。 回文系の問題。「〜な条件だと結局全部一緒になる」という問題の雰囲気がどことなく数オリっぽい。 必要条件を頑張って列挙したら実は十分な感じもまた、数オリっぽさと AGC っぽさの両方がある感じ。 問題へのリンク 問題概要 総和が 、長さが…

AtCoder AGC 003 C - BBuBBBlesort! (600 点)

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

AtCoder ABC 115 D - Christmas (400 点)

再帰関数の使い方に慣れるための教育的問題。 この手の再帰的なフラクタルっぽい構造を読み解く問題は「十分回数を重ねると最初の方の模様が収束する」みたいなことをするイメージがあるけど、今回はそういうのじゃなくて純粋に再帰関数の使い方を問われる問…

diverta 2019 E - XOR Partitioning (800 点)

時間かかりすぎた。シンプルで面白い。 問題へのリンク 問題概要 要素からなる 0 以上の整数列 が与えられる。 これをいくつかの連続した部分列に分割する 通りの方法のうち、各連続区間の XOR 和が互いに等しくなるものが何通りあるか、1000000007 で割った…

AtCoder ARC 074 D - 3N Numbers (500 点)

昨日の ABC で、「左右両端からの累積和」を使うと良い問題が出たので、その発展的類題の紹介に。 drken1215.hatenablog.com 問題へのリンク 問題概要 を正の整数とする。 個の要素からなる数列 にとおいて、 個の要素を取り除き、残った 個の要素のうち (前…

AtCoder AGC 032 E - Modulo Pairing (1200 点)

楽しかった。7 時間かかったけど自力 AC できたー! 問題へのリンク 問題概要 正の整数 が与えられる。 個の 以上 未満の整数 を 個ずつのペアに分けたい。 各ペア に対して % の値 (これを醜さと呼ぶ) を求め、その最大値をとる。 この最大値の最小値を求め…

AtCoder ABC 125 D - Flipping Signs (400 点)

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

AtCoder ABC 125 C - GCD on Blackboard (300 点)

累積和!累積和!累積和!!! でも累積和ならぬ累積 GCD なのと、左右両方から累積 GCD を求める。 問題へのリンク 問題概要 要素からなる数列 が与えられる。この数列に対して どれか一つ要素を選んで、 以下の好きな正の整数に書き換える という操作を行…

Codeforces 554 DIV2 E. Neko and Flashback (R2500)

面白かった 問題へのリンク 問題概要 (やや意訳) 長さ の数列 を復元したい。この数列に対し、ある並び替え順列 があって 隣り合う 2 要素の min をとってできる長さ の数列を で並び替えると となり 隣り合う 2 要素の max をとってできる長さ の数列を で…

Codeforces 553 DIV2 E. Number of Components (R2100)

面白かった。 「全体についての総和についての総和」を「個別の要素についての総和を各要素について総和」とするテク 区間の連結成分の個数は、各隙間に左端が入り込むかを数える という典型テクが詰まった問題。 問題へのリンク 問題概要 要素からなる数列 …

Tenka1 2019 D - Three Colors (600 点)

見た目とても面白そう 問題へのリンク 問題概要 要素からなる数列 があたえられる。各要素を「赤」「緑」「青」の三色のいずれかに塗る方法のうち、各色の合計値を として三辺の長さが となるような三角形が存在するようなものを数え上げよ。998244353 で割…

Codeforces 552 DIV3 F. Shovels Shop (R2300)

問題概要 個の品物があって、それぞれ価格は である。ここから 個の品物を何回かに買いたい。ここで一回の買い物につき一回ずつ使えるクーポン券が 個あって (使わなくても良い)、各クーポンは ちょうど 個の品物を買ったならば、そのうちの安い順に 個の品…

Codeforces 552 DIV3 G. Minimum Possible LCM (R2400)

天才か!!! 問題へのリンク 問題概要 個の整数 が与えられる。 < となる であって、LCM() が最小となるものを求めよ。 制約 考えたこと という制約がいかにも怪しい。この制約が意味するのは 配列 a をバケットで表せる。すなわち a = (2, 3, 5) みたいな…

AtCoder ABC 115 C - Christmas Eve (300 点)

今の 300 点に比べると少し易しめで、でも 300 点っぽくていい感じだなと。 問題へのリンク 問題概要 個の整数 が与えられる。ここから 個の整数を選ぶ。 「選ばれた数の最大値と最小値の差」の最小値を求めよ。 制約 < 考えたこと すごく 300 点問題っぽく…

AtCoder ABC 124 D - Handstand (400 点)

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

AtCoder ABC 124 B - Great Ocean View (200 点)

こういうのが素早くストレスなく書けるようになるといい感じな気がする 問題へのリンク 問題概要 海から順番に建物 があって、それぞれの高さは である。 海が見える建物が何個あるかを求めよ。なお、 番目の建物から海が見えるとは より前の 番目の建物より…

AtCoder ABC 123 D - Cake 123 (400 点)

priority_queue で動的に 個出力する問題作りたいな〜と思ってぼんやりストックしてた問題と一緒だった!!!!!! 問題へのリンク 問題概要 個の要素からなる数列 個の要素からなる数列 個の要素からなる数列 が与えられる。 からそれぞれ 1 個ずつとりだ…

AtCoder AGC 010 B - Boxes (500 点)

状況がゴチャゴチャとして来て、整理するのが大変だった 問題へのリンク 問題概要 個のマスがあって最初は全マスに が書かれている。これに以下の操作を好きな回数だけ好きな順序で行って数列 にできるかどうか判定せよ。 を巡回させてできるものを足す 制約…

AtCoder AGC 020 C - Median Sum (700 点)

コンテスト中に真剣に考えて解けなかった 700 点問題!!! 問題へのリンク 問題概要 個の整数 があたえられる。 個の整数の部分和は空集合に対応するものを除くと 個ある。 このうちの中央値を求めよ。 制約 考えたこと とりあえず部分和問題みたいなことを…

エクサウィザーズ 2019 D - Modulo Operations (600 点)

楽しい問題だった!!! 問題へのリンク 問題概要 すぬけ君は黒板と 個の整数からなる集合 を持っています。すぬけ君は黒板に整数 を書いたのち、以下の操作を 回行います。 から要素を 1 つ選んで取り除く。 その後、現在黒板に書かれた数を 、 から取り除…

AtCoder AGC 013 A - Sorted Arrays (300 点)

個人的には超苦手系。。。 でもちゃんと Greedy 思考を整理すればできる。こういうのは Greedy 思考の「型」を理解することが大事そう。 問題へのリンク 問題概要 長さ の数列 が与えられる。 を何箇所かで切って、 の連続した部分であるようないくつかの数…

AtCoder AGC 012 A - AtCoder Group Contest (300 点)

これほとんど drken1215.hatenablog.com と同じ問題!!! 問題へのリンク 問題概要 を整数として 個の整数 が与えられる。これらを 3 個ずつ 組のペアを作る。 ペアリングのスコアは、各ペアにおいて 2 番目に大きい値の総和で決まる。ペアリングのスコアを…

AtCoder AGC 032 A - Limited Insertion (400 点)

好き!!!!!でも A 問題としてはかなり難しいね。 問題へのリンク 問題概要 数列 が空の状態から出発して以下の操作を 回行った結果が数列 と一致するようにできるかどうか判定せよ。 回目の操作においては 以上 以下の整数 を一つ選んで、数列の 番目に …

Educational Codeforces 62 E - Palindrome-less Arrays

楽しかった 問題へのリンク 問題概要 未完成の数列 が与えられる。未完成部分には が書かれている。完成部分には 以上 以下の整数が書かれている。 のところを 以上 以下の整数を埋める方法であって、整数列が奇数長の回文を含まないものは何通りあるか? 制…

AtCoder AGC 009 A - Multiple Array (300 点)

教育的 Greedy 問題! 問題へのリンク 問題概要 個の整数からなる数列 と数列 がある。以下の操作を好きな回数だけ行える: 以下の整数 を 1 つ選び、 の値を ずつ増やす すべての に対して が の倍数となるようにしたい。これを実現するための操作回数の最小…

Codeforces #547 Div. 3 F - Same Sum Blocks (Hard)

区間スケジューリングと聞いて 問題へのリンク 問題概要 要素からなる数列 が与えられる。以下の条件を満たす最大個数の区間を求めよ (どれか 1 つ復元せよ)。 どの 2 つの区間も交差しない どの区間についても含まれる値の総和が等しい 制約 考えたこと 区…

yukicoder No.802 だいたい等差数列

面白い!!!!!!!!! 問題へのリンク 問題概要 長さ の整数列 であって、 を満たすものの個数を 1000000007 で割ったあまりを求めよ。 制約 まずは変数変換 まずは数列 の差分に注目してみることにする。 とする ( とする)。そうすると、条件は () とい…

AOJ 2942 Absum (RUPC 2019 day1-F)

難しくて、てんぷらたんが天才だった!!!!!!! とにかくすごかった!!!!! そしてすごく面白い問題だった!!!!! 問題へのリンク 問題概要 長さ の数列 が与えられる。数列の 2 要素を選んで swap する操作を高々 回まで行うことができる。 操作…