NoviSteps3D
opt さんの「そのままだと優モジュラ最適化なので、青木君の選ぶ・選ばないをひっくり返せば劣モジュラ最適化。よって最小カットでできる」が賢かった。 競プロで言うところの「燃やす埋める」 問題へのリンク 問題概要 のグリッドがあって、各マス には整数…
面白かった 問題へのリンク 問題概要 以下の素数のみを素因数に持つ正整数を -smooth number と呼ぶ。 整数 および 、100 以下の素数 が与えられるので、 以下の -smooth number の個数を求めよ。 制約 考えたこと コンテスト中には、愚直 DFS を頑張って通…
DAG の最小パス被覆、忘れた頃に出て来るイメージ！ 問題へのリンク editorials 問題概要 個の直方体があり、 番目の直方体の大きさは である。 今、ある直方体の中に他のある直方体を入れたりすることで、外部から見えている直方体の体積を小さくしたい。た…
めっちゃ面白い問題だった！ Suffix Array の練習問題。 問題へのリンク 問題概要 英小文字からなる長さ の文字列 が与えられる。 の suffix は空文字列を除いて 個ある。これらの suffix を適切な順序で連結させて 1 つの文字列を作るとき、それが辞書順最…
めっちゃ面白い問題だった！ 問題へのリンク 問題概要 頂点 0 を根とする頂点数 の根付き木が与えられます。頂点 0 以外の頂点 には数値 が書かれています。今、頂点 0 にコマが置いてあります。 高橋くんと青木くんが次の動作を交互に繰り返します。 青木く…
これを機会に SA-IS を整備した！ 問題へのリンク 問題概要 2 つの文字列 に対して「先頭何文字が一致しているか」を と表すことにします。 長さ の文字列 が与えられます。 の 文字目以降のみからなる部分文字列を と表すことにします。 のそれぞれに対して…
原始根が絡む問題は時々出るイメージですね。 問題へのリンク 問題概要 素数 が与えられます。 次の条件を満たす整数 の組の個数を 998244353 で割ったあまりを求めてください。 ある正の整数 が存在して、 が成立する 制約 は素数 考えたこと 整数問題とい…
これほどシンプルな問題がグラフ最短路問題になるのは感動的ですね！ 問題へのリンク 問題概要 の正の倍数をすべて考えたときの、各桁の和として考えられる最小値を求めてください。 制約 うまく数字を並べるゲームと捉える の倍数をひたすら試す方法をまず…
なんとか解けた。若干エスパー気味に解いた。 問題へのリンク 問題概要 頂点数 、辺数 の無向単純グラフが与えられる。 各 に対して、この誘導部分グラフ (頂点集合はそのまま、辺集合は部分集合) であって、次数が奇数の頂点が 個であるようなものの個数を …
間に合わなかった！！！悔しい！！！ 問題へのリンク 問題概要 長さ の数列 が与えられます。以下の条件を満たすような、長さ の数列 の個数を 998244353 で割ったあまりを答えよ。 制約 考えたこと という条件は扱いづらいので、包除原理でやると良さそう。…
面白かった。 問題へのリンク 問題概要 人がいて、それぞれ「スパイ」か「非スパイ」かのどちらかである。 人のうち、何人かについてはスパイかどうかが予めわかっている ( で与えられる)。 個の証言がある。各証言は人 が証言者によってなされ、「人 はスパ…
添字 GCD convolution が一躍話題になった問題だった気がする 問題へのリンク 問題概要 長さ の整数列 がある。 の値を 998244353 で割ったあまりを求めよ。 制約 考えたこと 個の値のうちのすべてのペアに対するなにかの総和を求める問題では を満たす につ…
AGC っぽくない気がするけど、好き 問題へのリンク 問題概要 とする (素数である)。 個の非負整数 が与えられる。 の値を求めよ。 制約 考えたこと 「和を で割ったあまり」ではなく、「 で割ったあまりの和」であることに注意。それでも、とりあえず以下の…
5 + 7 + 5 = 17 なの、よくできてる！ 問題へのリンク 問題概要 正の整数 が与えられる。 以上 以下の数値からなる長さ の数列 であって、以下の条件を満たすものの個数を 1000000007 で割ったあまりを求めよ。 整数 が存在して、 の区間 の総和が の区間 の…
こういうのを確実に... 問題へのリンク 問題概要 1 以上の整数からなる長さ の数列 が与えられる。この数列に対して、以下の操作を好きな回数だけ好きな順序で行うことで広義単調増加となるようにしたい。最小回数を求めよ。 個の整数から 1 つ選んで -2 倍…
バチャやった。13 位相当で割とよかった。 ロリハした。 問題へのリンク 問題概要 長さ の整数列 , が与えられる。以下の条件を満たす 以上 以下の整数 と、整数 の組をすべて求めよ。 = が成立する 制約 考えたこと 整数列 を circular shift した上で、 と…
Xor Sum シリーズしゃん。典型てんこ盛り！！！ XOR は各桁ごとに独立に考えるとよい XOR に関する問題は mod. 2 での方程式みたいになることも多い であることから上位の桁から辞書順的に優先で考えるような貪欲が決まる などなど。 問題へのリンク 問題概…
めるアイコン変換すると良さそうなのはすぐに思い至った。そこから繋げられずに editorial を見た。 問題へのリンク 問題概要 二次元平面上に 個の点がある。このうちの 2 点 が指定されている。その 2 点間のマンハッタン距離を とする。 この 点について「…
結構苦手系。想定解法かはわからないけどやってみた 問題へのリンク 類題とか drken1215.hatenablog.com 問題概要 'R', 'G', 'Y' の 3 種類の文字で構成された長さ の文字列 が与えられる。これに以下の操作を行って「隣り合う 2 文字が同じになることはない…
一目見て惹かれた。すごく面白かった。割と自然な考察の流れで解けた。 問題へのリンク 問題概要 個の正の整数からなる数列 が与えられる。先手と後手が交互に以下を繰り返す。先に操作を行えなくなった方が負けである。双方最善を尽くしたときにどちらが勝…
楽しいけど重くて、重いけど楽しい 問題へのリンク 問題概要 要素から成る数列 が与えられる。 個から 2 個選んでできる 通りのペア のうち、以下の条件を満たすものを数え上げよ。 容量が の容器を用意して、以下の操作によって水の量 を汲み取れる 操作 1:…
挿入 DP。。。TDPC O - 文字列を複雑にした問題。アイディアはシンプルだけど詳細詰めが重たい。。。 問題へのリンク 問題概要 個の正の整数 が与えられる。 が 個 が 個 ... が 個 を合わせた 個の数を並べる方法のうち、どの隣り合う箇所も数値の差が 以上…
コンテスト中に解けなかったのが悔しい。 問題へのリンク 問題概要 個の座標 () が与えられる。 今、40 本以下の正の整数 を用意して、それぞれについて (), (), (), () をうまく選択して加算することで、() をすべて作れ。できないときは -1 とせよ。 各 に…
二重辺連結成分分解ライブラリを整えた。 問題へのリンク 問題概要 N 頂点, M 辺の無向単純グラフにおいて、以下の Q 個のクエリに答えよ。 A B C: A から出発して B に行くウォークと、B から出発して C に行くウォークの組のうち、辺を共有しないものがあ…
たくさんの方法がとれる超教育的な問題なので、たくさんの方法で解いてみた！ 問題へのリンク 問題概要 の 個の集合がある。 と とを併合する という操作が 回行われた。以下の 個のクエリに答えよ: と が何回目の操作後にはじめて一緒のグループになったか…
並列二分探索が想定ではなさそうだけど、並列二分探索法で解いてみました。 問題へのリンク 解法 #include <iostream> #include <vector> #include <queue> #include <map> #include <algorithm> using namespace std; struct UnionFind { vector<int> par, rank, sz; UnionFind(int n) : par(n), rank(n, 0</int></algorithm></map></queue></vector></iostream>…
オイラーツアー第三弾！ RUPC 2018 で見たばかりの問題でもある。 問題へのリンク 問題概要 頂点 1 を根とする頂点数 N の根付き木が与えられる。初期状態で各頂点に G または W の属性が割り振られている。以下の Q 個のクエリに答えよ: v: 頂点 v を根とす…
オイラーツアー練習第二弾。 そして、これにて一応、ツリーの辺に重みがある場合にも対応できることとなった。 問題へのリンク 問題概要 頂点 1 を根とした頂点数 N の根付き木が与えられる。初期状態では各頂点に 0 か 1 の値が割り当てられている。以下の …
