共通接線ライブラリの整備 問題へのリンク 問題概要 互いに重ならない円が N 個ある。 直線を考えたとき、そのスコアは 各円に対して、その円と共有点を持たず、その円との距離がある一定 (円に依存して決まる値) 以下であるとき 1 を加算、そうでないとき 0…

3 次元幾何の練習 問題へのリンク 問題概要 円錐を平面によって切断するとき、分離された2つの部分の体積を求めよ。 解法 ちょっと複雑だが、2次元に射影して考える。 そのためには、3次元幾何の正射影が必要になる #include <iostream> #include <vector> #include <cmath> #include <iomanip></iomanip></cmath></vector></iostream>…

2 日目：AGC 027 E - ABBreviate (1300 点)https://t.co/mvWcvtxfRz3 で割った余りについて不変量であることは既出。重複を除くために「文字列の部分文字列の数え上げ」的な考え方をするのも恐らく典型。自力で詰め切るのはまだ辛いけど「赤くならないうちは…

悔しい... 問題へのリンク 問題概要 整数 が与えらる。以下の条件を満たすような 行列 a を 1 つ構築せよ: 各要素の値は 以上 以下 ある正の整数 が存在して、行列の上下左右に隣接する 2 数 をどこから取り出しても、max() を min() で割ったあまりは とな…

たくさんの方法がとれる超教育的な問題なので、たくさんの方法で解いてみた！ 問題へのリンク 問題概要 の 個の集合がある。 と とを併合する という操作が 回行われた。以下の 個のクエリに答えよ: と が何回目の操作後にはじめて一緒のグループになったか…

部分永続 Union-Find 木の練習をした。 問題概要 N 頂点 M 辺の無向グラフがあります。 グラフは連結です。以下の Q 個のクエリに答えよ: 頂点 x, y が与えられ、「x と y を含む z 個の頂点からなる集合に含まれる頂点の番号の最大値」の最小値を求めよ 解…

並列二分探索が想定ではなさそうだけど、並列二分探索法で解いてみました。 問題へのリンク 解法 #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>…

問題概要 2 個の正整数 A,B が与えられる。 A! の約数である B! の倍数である ような正整数の個数を 1,000,000,007 で割った余りを求めよ。 制約 解法 求める正整数は とおける。これが の約数であることから、 | であることが言える。よって、 の約数の個数…

もれなく正確に解くための考え方とかが問われる感じ。 問題へのリンク 問題概要 整数 が与えられる。 に以下のいずれかの操作を最小回数行って に一致させよ: を 1 増やす を にする 解法 最適解は 最初に反転する (かしないか) 「1 増やす」を繰り返す 最後…

一見 な bitDP だけど、これはアレだ！！！ よくある にできるやつだ！！！！！ 問題へのリンク 問題概要 個の数 がある。これを最小個数のグループに分けて、各グループの合計値が 以下となるようにせよ。 制約 解法 とりあえず一見 な bitDP に見える。AGC…

最初は「一度選んだマスを使えない」を完全に呼び飛ばしてしまった上に、それに気づいた後も「奇数マス同士をマッチングして、うまく経路を設定する」という方向の考察をしまくって、上手くいかずに迷走した... 問題へのリンク 問題概要 縦 行、横 列に区切…

一瞬「訪れる順番によって状況が変わらないか...」と不安になるかもな問題だけど、よく考えたら訪れる順番を考える必要もない。ソートしても OK だけどソートする必要はなかった。 問題へのリンク 問題概要 個の点が一直線上に並んでいて、各頂点の座標は で…

桁ごとに考えるしかなさそうなのはそれはそう... 問題へのリンク 問題概要 (ARC 092 D / ABC 091 D) 要素の数列 と が与えられる。 個の整数 の XOR 和を求めよ。 制約 < 解法 XOR 和と言われた時点で、各桁ごとにカウントしたい気持ちにはなる。 個の整数の…

最適性を失わずに解を変形していくことで、都合のいい解の形だけ考えればいいようにする系の問題。 問題へのリンク 問題概要 (ARC 094 D / ABC 093 D) 人の参加者が 2 回のプログラミングコンテストに参加しました。順位がつくのですが、同順位はないものと…

Disjoint Sparse Table の勉強をした！！！ 詳しいことは Disjoint Sparse Table と セグ木に関するポエム (のししゃん) Codechef Tutorial - Disjoint Sparse Table あたりを参考に。 問題概要 数列が与えられて、「区間 [L, R) の積を P で割ったあまりを…

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

今回は Suffix Array でやってみたけど、ローリングハッシュとか、KMP とか、Z-Algorithm とか、色んな方法があるみたいなので追々やってみたい。 → やってみた (3/14) 問題へのリンク 問題概要 文字列 がよい文字列であるとは「いかなる文字列 および 2 以…

問題概要 N 本のろうそくが一直線上に並んでいる。最初は原点にいて、N 本のうち K 本のろうそくに火をつけたい。ろうそくと同じ座標に到達すると火をつけることができる。火をつけるのに要する時間は 0 秒である。移動距離を最小化せよ。 解法 K 個の連続す…

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

考え方はすぐわかるけど実装が大変... 問題へのリンク 問題概要 長さ の数列 と整数 が与えられる。 この数列に対して次のような操作を繰り返す 連続する k 個の区間についての最大値をすべて書き出す この操作を 1 回行うごとに数列の長さは だけ減ることに…

領域加算、領域和取得の両方に対応した二次元 BIT ライブラリを目指した 問題概要 N × N の盤面において以下の M 個のクエリに答えよ: 長方形領域 [x0, y0] × [x1, y1] の XOR 和を出力 長方形領域 [x0, y0] × [x1, y1] 全体に一様に値 v を XOR 加算 考えた…

二次元 BIT ライブラリ の verify をした 問題へのリンク 問題概要 H × W のプレートにたこ焼きを置いて焼いていく。配置されたたこ焼きは「焼き上がった」「まだ焼き上がっていない」の 2 つの状態を持つ。なお、たこ焼きは配置されてから焼き上がるまでの…

十分多い回数重ねるとなにかが収束する系はよく見るん 問題へのリンク 問題概要 (ABC 106 C) 1 から 9 までの数字からなる文字列 S がある。以下の操作を 5000 兆回行う: 文字列 S に含まれるそれぞれの 2 が 22, 3 が 333, 4 が 4444, 5 が 55555, 6 が 666…

こういうの苦手。。。 問題へのリンク 問題概要 整数 k と、N 頂点 0 辺のグラフが最初に与えられる。以下の M 個のクエリに答えよ。 a, b: 辺 (a, b) を追加する。この時点でグラフの各頂点を以下の条件を満たすように白黒に塗る「任意の黒い頂点は、隣接す…

こういうの超苦手。。。解き方はわかるけど実装を工夫する感じの。 問題へのリンク 問題概要 N 頂点のツリー (頂点番号は 1, 2, ..., N) と、(1, 2, ...., N) の順列 a が与えられる。 このツリーを頂点 1 から出発して BFS したとして、その頂点訪問順序が …

超苦手系。なんとか解けた。 問題へのリンク 問題概要 長さ N のバイナリ列 a, b が与えられる。a に対して 隣接二項を swap する 0 と 1 を反転する の操作を最小回数行って b にせよ。(10 -> 01 なら 1、1000 -> 0001 なら 2) 制約 1 <= N ,= 106 考えたこ…

メッチャ楽しい問題！！！ 問題へのリンク 問題概要 (ARC 102 F) 1 〜 N の順列が与えられる。 連続する三要素が単調減少のとき、それをひっくり返す という操作を好きなだけ行って、恒等順列にできるかどうか判定せよ。 制約 1 <= N <= 3 × 105 解法 (全然…

いろんな解法がありそうなんな 問題へのリンク 問題概要 整数 が与えられる。各 に対して、 どの に対しても を満たす整数組 の個数を で割った余りを求めよ ( 面サイコロを 個振るという設定)。 制約 解法 1: 漸化式を立ててそれを展開 (本番で通した解法) …

好きだけど細かいところで時間とられるやつなん 問題へのリンク 問題概要 整数 L が与えられる。N 頂点 M 辺の重み付き有向グラフ (頂点番号は 1, 2, ..., N) であって N <= 20 M <= 60 任意の辺 (u, v) について u < v でなければならない 頂点 1 から頂点 …

editorial に載っている解法は整数論で でやっているし、僕も本番それでやったけど、この制約なら全探索でパッと書けるべきですね... 参考: ABC108/ARC102 C: 解説に書かれていませんが、制約が手加減されているので a か a % K の値を全探索できます、この…