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

こういうのを得意になるぞー！！！ でも AtCoder でこういうデータ構造をしっかり準備する必要がある系は珍しい気がする。 問題へのリンク 問題概要 個のマス () があって、マス上に 個の区間がある。 各 に対して、 と移動したときに何個の区間を踏むかを答…

こういうのに慣れて行きたい。 問題へのリンク 問題概要 長さ の線分上に、ランダムな区間を 個とったときの、区間が 本以上重なっている部分の長さの期待値を求めよ (998244353 で割った余りの形式で)。 なお、区間のランダムな選び方とは、線分から 2 点ず…

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

教育的な典型問題！ 問題へのリンク 問題概要 要素からなる順列 が与えられる。 の連続する各区間について、区間内の最小値を求め、その総和を求めよ。 制約 考えたこと まず思うのが、区間の個数は 個ある。たとえ各区間に対する最小値を で答えられたとし…

頭の整理が大変！！！ 問題へのリンク 問題概要 左から右に向かって 1 から N の番号がついた N 個のマスがあります。 各マスには文字が書かれており、マス i には文字 si が書かれています。また、各マスにははじめ 1 体のゴーレムがいます。 すぬけ君は Q …

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

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

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

ロリハそのものな問題！！！ 問題へのリンク 問題概要 長さ の文字列 が与えられ、 の連続する部分列が 個指定される。こうして作られる 個の文字列のうち、相異なるものは何通りあるか答えよ。 考えたこと ロリハで頑張る #include <iostream> #include <vector> #include <string> #i</string></vector></iostream>…

F2 線形代数大好き！ 問題へのリンク 問題概要 個の整数 の部分集合を選んで XOR 和を にする方法のうち、 個の区間 [ ] () について 区間の中から選ぶ個数は偶数個か奇数個かが指定される という制約を満たすものが何通りあるか求めよ。 制約 考えたこと 実…

有理数さん。。。 誤差がとんでもなく厳しいらしく、有理数ライブラリを使うということをついに覚えた！！！ あと、問題の解法自体は「区間串刺し」といういわゆる「区間スケジューリング問題」の亜種。 問題へのリンク 問題概要 とある水族館に住むイルカ君…

操作を逆順に見るとよいという、すごく良い例題！大好き！！！ 問題へのリンク 問題概要 要素からなる数列 が与えられる。今、以下の操作を好きな回数だけ行う。 長さが の区間を選んで、区間全体を白く塗るか、黒く塗る 操作を行った後に黒く塗られたマスの…

整理するのがちょっと大変系。でもとても教育的だと思う！ 問題へのリンク 問題概要 次元の整数ベクトル () が与えられる。これを以下のようなベクトルの和として表したい。 () のように「」が連続していてそれ以外は になっているベクトル 例えば、(1, 3, 3…

しゃくとり法のいい感じの練習問題 問題へのリンク 問題概要 英小文字のみから成る文字列 が与えられる。 の連続する部分文字列のうち「同じアルファベットが2度以上使われることのない」ものが何個あるかを数えよ (空文字列は 1 個とみなす) 制約 考えたこ…

700 点は絶対落とさないようにしたい！！！ 本番、DP と包除原理の二通りの方針が早期に見えて、「どちらかで詰まったらどちらかに立ち戻ろう」と思いながら DP に突き進んで見た。それでちゃんと通ってよかった。 問題へのリンク 問題概要 長さ の区間があ…

累積和の練習 問題へのリンク 問題概要 個の整数 が与えられる。 各 に対して、数列の 個の連続する区間の値の和の最大値を求めよ。 制約 考えたこと 愚直にやると計算量は の値が 通り考える必要があって 各 に対して 個の区間があって 各区間に対して 個の…

郡山駅のベンチで寒さに震えながらやる問題ではなかった...必要以上に複雑にしてしまった。。。 問題へのリンク 問題概要 すぬけさんが、座標 0 と との間を行ったり来たりする。行って方向転換できる場所は整数座標のみである。 このとき、各区間 [ ] () に…

ソートする問題。 問題へのリンク 問題概要 個のコマを数直線上に配置して、それぞれ移動させる。 それによって、 個の地点 をすべて訪れるようにしたい。総移動距離の最小値を求めよ。 制約 考えたこと とりあえず、各コマについて、「行って、引き返して」…

Mo のアルゴリズムの練習第三弾！！！！！ 問題へのリンク 問題概要 要素の整数列 が与えられる。以下の 個のクエリに答えよ: 数列の区間 [ ) 内について、各数値 について が何個出現しているかを として表して、 を求め、その総和を求めよ 制約 考えたこと…

Mo のアルゴリズムの練習第二弾。 問題へのリンク 問題概要 要素の整数列 が与えられる。以下の 個のクエリに答えよ: 数列の区間 [ ) 内に最も多く登場する値が、何回登場しているかを答えよ 制約 考えたこと Mo の練習第二弾。 最頻値の頻度を求めるのは、…

種類数クエリをマスターするぞ！ 問題へのリンク 問題概要 要素の整数列 が与えられる。以下の 個のクエリに答えよ: 数列の区間 [ ) 内に何種類の整数があるかを答えよ 制約 解法 1： BIT (区間加算、1 点取得) まずは BIT を用いる方法から。 考えやすいよ…

区間についてどうのこうのする問題、大抵は DP！ 問題へのリンク 問題概要 個の整数 がある。これらのうちいくつか選んだ合計を最大化したい。ただし、 の区間 [ ] があって、選んだ数のどの 2 つをとっても同一区間上にならないようにしなければならない。 …

これは。。。C より先に確実にこれをとったのはよかった 問題へのリンク 問題概要 (意訳) H × W の二次元グリッドがあって、各マスは通路か壁である。壁は N 個ある。最初は (1, 1) に駒がある。 毎ターン (x, y) にある駒は (x + 1, y) に進める、ここで (x…

えーーーこれが平方分割的解法って天才すぎでは 問題へのリンク 問題概要 人が一直線上を、初期位置 、速度 で等速直線運動を行う。以下の 個のクエリに答えよ: 秒後に座標 から座標 までの間にいる人数を数えよ 制約 考えたこと が 以下と小さいことが大き…

Convex Hull Trick の練習に。 問題へのリンク 問題概要 長さ の数列 が与えられる。数列を 個の区間に分割して、各区間 [, ] についての の総和を最小にせよ。 制約 解法 いかにも な DP になるのを頑張って高速化する系の問題。2 乗だから convex hull tri…

「 番目の値を求めよ」「メディアンを求めよ」といった問題では、二分探索法が有効なことが多々ありますね。 問題へのリンク 問題概要 長さ の数列 が与えられます。 この数列の連続する区間として考えられるものは 個あります。そのそれぞれの区間について…

いろんな方法が考えられそう。 せっかくなので、敢えて、N が大きくても OK な方法でやってみる。hama_du さんの記事を参照。 問題概要 M 個の区間 [l_i, r_i] が与えられる。以下の Q 個のクエリに答えよ: 区間 [p, q] に完全に含まれる区間が何個あるかを…

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

ツリー上のクエリの練習 問題へのリンク 問題概要 (意訳) N 頂点のツリーが与えられて以下の Q 個の操作を行う。初期状態では全頂点の値は 0 である。 2 頂点 u, v 間のパス上に含まれる頂点すべて (u, v も含む) の値を +1 する。 Q 回の操作後の各頂点の値…