最大スコア
これは楽しい！！！ 順番をうまく決めれば、全部の情報を持たなくても、個数のみの情報に落とせる系。 問題へのリンク 問題概要 要素の数列 と、 の二次元数列 が与えられる。 個の の中から 個を選び、 残りの 個の index の中から 個分、 の行ベクトルを選…
期待値の線形性！！！ 問題へのリンク 問題概要 個のサイコロが左から右に一列に並べてある。 番目のサイコロは目が となっていて、これらが当確率に出る。 隣接する 個のサイコロを選んでそれぞれ独立に振ったとき、出る目の合計の期待値の最大値を求めよ。…
こういうのを素早く処理できるようになりたい 問題へのリンク 問題概要 長さ の 種類の文字からなる文字列 が与えられる。いま、 種類の文字の順列 として考えられる 通りの並びのうち最適なものを求めたい。 順列のスコアは、 上のすべての連続する 2 文字…
面白かった！！！こういうのを確実に通せるようにならないと！！！ 問題へのリンク 問題概要 頂点の木が与えられる。木の各辺を のラベルをつける方法のうち、 の値の最大値を求めよ。ただし は、2 頂点 を結ぶパスに含まれる辺の値の集合を考えたときに、そ…
すごく面白かった！！！ 問題へのリンク 問題概要 長さ の数列 が与えられる。ここから何個か選ぶ。選んだ値を としたとき、そのスコアを以下のように定義する。 選んだ値のメディアンを とする 奇数個の場合は真ん中の値 偶数個の場合は真ん中の 2 つの値の…
最初、罠に引っかかった 問題へのリンク 問題概要 長さ の数列 が与えられる。これらの連続する区間の総和を書き出していく ( 個ある)。 これらの中から 個選んで AND をとった値として考えられる最大値を求めよ。 制約 嘘貪欲 とりあえず なので、 個の整数…
「区間」と「二次元平面上の点」とはしばしば互いに行き来することで問題が解けたりする！！！ 問題へのリンク 問題概要 二次元平面上の 点が与えられる (いずれも 座標が 0 以上の格子点)。各点にはスコア が与えられる。 対角線のうちの一つが 上にあるよ…
すんごく横長な行列に関する問題だけど、実は横の長さを縦の長さ以下にできるというタイプ。 そうすれば の問題に帰着できて、。あとは の bit DP...なのだが、TLE がとれなかった。微妙に詰めが甘かった。。。 問題へのリンク 問題概要 の行列があたえられ…
ジャンプの過程を無視して、最終的に出来上がるものがどうなるかを考えて、それをわかりやすく特徴づける 調和級数になるタイプの全探索 というタイプの問題。結構重たい。AGC なら C 問題でありそう。 問題へのリンク 問題概要 個の地点 にそれぞれ のスコ…
混ぜてソートは賢すぎる！！！惚れた！！！ 問題へのリンク 問題概要 枚のカードにそれぞれ の数値が書かれている。あなたは、 について順に以下の操作を 1 回ずつ行います。 カードを 枚まで選ぶ(0 枚でもよい)。選んだカードに書かれている整数をそれぞれ …
学び多き問題。 僕にとっては後半のデータ構造パートが苦戦を強いられ、本当に勉強になった！ 問題へのリンク 問題概要 個の寿司があって、それぞれネタ と美味しさ をもっている。この中から 個の寿司を選びたい。選んだ寿司集合のスコアは 選んだ寿司の美…
部分文字列の遷移は愚直に求めた。。。 問題へのリンク 問題概要 長さ の文字列 c と、短い文字列 s, t が与えられ、'a'〜'z' と '?' からなっている。'?' を埋める方法のうち、 c の連続する部分文字列として s を含む箇所の個数から c の連続する部分文字…
昨日の ABC で、「左右両端からの累積和」を使うと良い問題が出たので、その発展的類題の紹介に。 drken1215.hatenablog.com 問題へのリンク 問題概要 を正の整数とする。 個の要素からなる数列 にとおいて、 個の要素を取り除き、残った 個の要素のうち (前…
操作をいい感じに言い換える感じ 問題へのリンク 問題概要 個の要素 が与えられる。これに対し、以下の操作を好きなだけ行える。 隣り合う 2 要素をともに -1 倍する 操作後の数列の値の和として考えられる最大値を求めよ。 制約 考えたこと こういう「操作…
面白かった 問題へのリンク 問題概要 文字列 が与えられる。あらかじめ文字列の中の 文字を自由に変更することができる。 こうして得られた文字列と、それを反転した文字列の LCS (最長共通部分列) の長さとして考えられる最大値を求めよ。 制約 考えたこと …
これ...以前 Twitter につぶやいた問題とよく似てた！！！ 400 点くらいの問題【問題】N 要素の 0 と 1 から成る数列が与えられる。以下の操作を最大 K 回行なって錬成し得る数列が何通りあるか 10e9 で割った余りを求めよ「数列の連続する区間を選んで 0 と…
たったこれだけの問題でも、学ぶべきことがすごくあるイメージ！！！ 問題へのリンク 問題概要 2 つのボタンがあってそれぞれ大きさが である。 大きさ のボタンを押すとコインが 円もらえて、ボタンの大きさが 1 減って になる。 2 回だけ好きなボタンを押…
これほとんど drken1215.hatenablog.com と同じ問題！！！ 問題へのリンク 問題概要 を整数として 個の整数 が与えられる。これらを 3 個ずつ 組のペアを作る。 ペアリングのスコアは、各ペアにおいて 2 番目に大きい値の総和で決まる。ペアリングのスコアを…
楽しかった 問題へのリンク 問題概要 個のアイテムがあって、それぞれ時間 と美しさ の属性がある。今、 個の中から 個選びたい。選んだアイテムたちのスコアは (選んだアイテムの時間の総和) × (選んだアイテムの美しさの最小値) で決まる。このスコアの最…
伝説の始まり 問題へのリンク 問題概要 個の整数 が与えられる。 これらを 個ずつ 組作り、各組についての「小さい方の値」の総和を最大にしたい。 制約 考えたこと 小さすぎる値と大きすぎる値とを組合せてしまうと、大きい値が小さい値に吸収されてしまっ…
燃やす埋めるは今度こそちゃんとマスターする！！！ 問題へのリンク 問題概要 × の各格子点に電球がある。 が偶数となるような について、 を頂点とする正方形の中心に装置があって、各装置を押すことで四隅の電球を点灯することができる。 ただし、装置を起…
難しくて、てんぷらたんが天才だった！！！！！！！ とにかくすごかった！！！！！ そしてすごく面白い問題だった！！！！！ 問題へのリンク 問題概要 長さ の数列 が与えられる。数列の 2 要素を選んで swap する操作を高々 回まで行うことができる。 操作…
操作を逆順に見るとよいという、すごく良い例題！大好き！！！ 問題へのリンク 問題概要 要素からなる数列 が与えられる。今、以下の操作を好きな回数だけ行う。 長さが の区間を選んで、区間全体を白く塗るか、黒く塗る 操作を行った後に黒く塗られたマスの…
「TDPC うなぎ」の類題。 問題へのリンク 問題概要 頂点の重み付きツリーが与えられる。ツリー上の「頂点を共有しないようなパスの集合」として考えられるもののうち、パスの重みの総和の最大値を求めよ。 制約 考えたこと ツリー二重 DP をする。 ツリー DP…
累積和の練習 問題へのリンク 問題概要 個の整数 が与えられる。 各 に対して、数列の 個の連続する区間の値の和の最大値を求めよ。 制約 考えたこと 愚直にやると計算量は の値が 通り考える必要があって 各 に対して 個の区間があって 各区間に対して 個の…
好き 問題へのリンク 問題概要 正の整数 が与えられる。 を満たすような 個の正の整数 の組合せをすべて考えたとき、 の最大公約数として考えられる最大値を求めよ。 考えたこと を素因数分解して、各素因子たちを に振り分けることを考える。 このとき、各…
区間についてどうのこうのする問題、大抵は DP！ 問題へのリンク 問題概要 個の整数 がある。これらのうちいくつか選んだ合計を最大化したい。ただし、 の区間 [ ] があって、選んだ数のどの 2 つをとっても同一区間上にならないようにしなければならない。 …
最初は「一度選んだマスを使えない」を完全に呼び飛ばしてしまった上に、それに気づいた後も「奇数マス同士をマッチングして、うまく経路を設定する」という方向の考察をしまくって、上手くいかずに迷走した... 問題へのリンク 問題概要 縦 行、横 列に区切…
かなり悩んだ 問題へのリンク 問題概要 長さ の整数列 を 3 箇所で切って、4 つの連続する数列に切り分ける。このとき、4 つの区間の値の和を とするとき、 の最小値を求めよ。 制約 考えたこと こういうの、 連続する区間が 4 個だけであることを活かす解法…
本番では回避したん。こういうのをサッサササッとバババババーンと解けるようになりたい。 問題へのリンク 問題概要 個の数列 が与えられる。以下の操作を好きな回数だけ行って得られる数列の総和を最大化せよ。 連続する 個の区間の数列を一斉に 0 にする …
