銅色 diff 問題が自力で解けて嬉しい。(修正：赤色になった) 問題へのリンク editorial 問題概要 原点を中心とする半径 1 の円周上に 個の点 がある (偏角が入力として与えられる)。 これらの点からランダムに 3 点選んでできる三角形の内心の座標の期待値を…

構築楽しかった 問題へのリンク editorial 問題概要 のグリッド上に のドミノを互いに重ならないように配置していく。 どの行・列を見ても、その行・列上にある のドミノの個数が互いに等しいような配置を求めよ。存在しない場合は "-1" を出力せよ。 制約 …

こういう問題めっちゃ好き！！！ 問題へのリンク editorial 問題概要 '0' と '1' のみからなる長さ の文字列が与えられる。以下の操作を 回以上 回以下まで行うことができる。 i < j であって S[ i ] = '0'、S[ j ] = '1' であるような (i, j) を選ぶ S[ j ]…

ある程度探索でゴリ押した。 問題へのリンク 問題概要 英小文字のみからなり、どの 2 文字も互いに相異なる文字列を「多彩」であると呼ぶこととする。多彩な文字列 が与えられる。以下の条件を満たす文字列の中で最も辞書順が小さいものを求めよ。 よりも辞…

少し手を動かせば見えてくる！ 問題へのリンク 問題概要 高橋君、中橋君、低橋君は、それぞれ整数 を持っている。 以下の操作を 回行った後の、高橋君の持っている整数から中橋君の持っている整数を引いた値を求めよ。ただし、答えの絶対値が を超える場合は…

面白かった！ 問題へのリンク 問題概要 頂点数が の木であって、各頂点 から最も遠い頂点への距離がそれぞれ であるような木が存在するかどうかを判定せよ。 制約 考えたこと 面白そう！！！！！！似た見た目の問題としては、次の問題もあった。 drken1215.h…

少し慎重に 問題へのリンク 問題概要 以下の正の整数の 10 進法での各桁の和の最大値を求めよ。 制約 考えたこと とかだったら答えは になりそうだ。一般に、 の形をしたものだけ考えれば良さそう。仮に とかが最適解だったとしても、その場合は として、 も…

シンプルだけど、すごい好き 問題へのリンク editorial 問題概要 マス と区切られた マス上でゲームする。 Alice は最初マス に、Bob は最初マス にいる。交互に左右どちらかに動かす。ただし「マスの外」や「相手のいるマス」には動かせない。 先に動かせな…

添字 GCD 畳み込みの練習問題！ 問題へのリンク 問題概要 長さ の正整数列が 個ある。 各数列から高々 1 個ずつ整数を抜き取って得られる数列は 通り考えられる。そのうち抜き取られた数値が 2 個以上あるようなものすべてについての、「それらの数値の最大…

添字 GCD convolution が一躍話題になった問題だった気がする 問題へのリンク 問題概要 長さ の整数列 がある。 の値を 998244353 で割ったあまりを求めよ。 制約 考えたこと 個の値のうちのすべてのペアに対するなにかの総和を求める問題では を満たす につ…

状態空間を上手に削減する系の問題 問題へのリンク editorial 問題概要 種類の長方形形状 () をしたスタンプがある (それぞれ「赤」「緑」「青」の 3 種類がある)。 これらを使って 4 × 4 のグリッド上に所望の模様を作りたい。グリッドからはみ出して押して…

BNF が書かれているので、LL(1)文法を再帰降下とかするのが標準みたいだけど、ad-hoc にスタックでなんとかしてしまった 問題へのリンク 問題概要 以下の BNF によって定義された文字列が与えられる。 <Cipher> ::= <String> | <Cipher><String> <String> ::= <Letter> | '['<Cipher>']' <Letter> ::= '+'<Letter> | '-'<Letter> | 'A' | 'B' |</letter></letter></letter></cipher></letter></string></string></cipher></string></cipher>…

TLE が厳しかった... 問題へのリンク editorial 問題概要 頂点数 の単純無向グラフ が与えられる (連結とは限らない)。各頂点 には重み がついている。 頂点 1 を含む の安定集合をすべて考えたときの、安定集合中の頂点の重もの総和の最大値を求めよ。 制約…

コーナーケースがエグい 問題へのリンク editorial 問題概要 個の非負整数 が与えられる。これらの並び替え であって が最大となるものを求めよ。複数通り考えられる場合には辞書順最小のものを答えよ。ただし、 とする。 制約 考えたこと エグい場合分けが…

本質的には彩色数を求めるだけだけど、幾何パートがちょっと面倒... 問題へのリンク 問題概要 二次元平面上に 個の多角形領域 (すべて単純) がある。各領域はそれぞれある国に属している。異なる多角形領域が同一の国に属していることもある。今、国ごとに「…

最大流問題の構造についての理解を問ういい感じの問題！ 問題へのリンク 問題概要 頂点数 、辺数 の単純有向グラフが与えられる (すべての辺の容量は 1)。2 点 間の最大フロー (辺素パスの本数) について考える。 今、いくつかの辺を選んで向きを反転するこ…

とても面白い問題です！ 問題へのリンク 問題概要 頂点数 、辺数 の、連結な重み付き無向単純グラフ が与えられる。 このグラフの「最小全域木」はさまざまなものが考えられるが、そのすべてに含まれるような辺の集合を考える。 その集合の要素数と、その集…

原始根 + NTT 問題へのリンク 問題概要 素数 と、数列 、 が与えられる。 各整数 に対して、 の値を 998244353 で割ったあまりを求めよ。 制約 考えたこと 添字積 convolution はできるのかと一瞬戸惑う。しかし が素数であることに着目すると、原始根 を介…

AGC っぽくない気がするけど、好き 問題へのリンク 問題概要 とする (素数である)。 個の非負整数 が与えられる。 の値を求めよ。 制約 考えたこと 「和を で割ったあまり」ではなく、「 で割ったあまりの和」であることに注意。それでも、とりあえず以下の…

離散対数の verify に 問題へのリンク 問題概要 4 つの整数 が与えられる。 は素数である。 整数 が の範囲を動くときの、 を で割ったあまりの最小値を求めよ。 制約 は素数 考えたこと まず、 を満たす最小の正の整数 を求める (これを位数と呼ぶ)。これは…

Pell 方程式！！！ 問題へのリンク editorial (day2-E) 問題概要 (意訳) 正の整数 が与えられる。 を正の整数として、 の値が最小となるような を 1 つ求めよ。 制約 考えたこと が平方数のときは として、 が答えとなる (最適値は 0)。 が平方数でないとき…

ペル方程式の練習 問題へのリンク 問題概要 数列 は次の漸化式で定義される。 この数列の母関数 を定義する。正の整数 が golden であるとは、 を満たす が有理数であることをいう。具体的には ... となっている。小さい方から 30 番目までの golden 整数の…

最初まんまと罠にひっかかった 問題へのリンク 問題概要 頂点数 の木が与えられる。各頂点には 0, 1, 2 のいずれかの色 (0: 灰色, 1: 白色, 2: 黒色) が割り振られている。以下の操作を最小回数行うことで、木を消滅させたい。最小回数を求めよ。 [操作]：残…

から落とせる気がまったくしなかった... 問題へのリンク 問題概要 個の広義単調増加数列 が与えられる。 それぞれの数列から、先頭から 個ずつとってきた値の総和の最大値を求めよ。ただし でなければならないものとする。 制約 考えたこと 個数に関する con…

AOJ-ICPC みを感じる！ 問題へのリンク 問題概要 頂点数 、辺数 の有向グラフが与えられる。頂点 1 から頂点 へとたどり着きたい。以下の 2 種類の操作ができる。 頂点 上にいるとき、辺 をたどって、頂点 へと移動する 移動に要するコストは 1 任意の頂点に…

りんごさんセット！！！ 問題へのリンク 問題概要 次元空間において () を満たす部分の体積を とすると は整数値となる。この整数値を 1000000007 で割ったあまりを求めよ。 制約 考えたこと 最初は色々迷走していた。三次元の場合を考えていて思っていたの…

どんな風に操作しようとも、毎回「左右のうちの何個選べるか」が変わらない！！ 問題へのリンク 問題概要 の順列 と、空の配列 が与えられる。これらに対して以下の操作を 回行うことで、配列 が に一致した状態にしたい。 そのような操作方法が何通りあるか…

区間加算操作は、「差分」をとる (いもす法) と、2 点加算になる！ 問題へのリンク 問題概要 長さ の数列 が与えられる。これに対して以下の操作を好きな順序で好きな回数だけ行うことで、数列の値がすべて 0 になるようにすることが可能かどうか、判定せよ…

undo 付き Union-Find ってなんぞ！？ 問題へのリンク 問題概要 頂点数 、辺数 の単純無向グラフが与えられる。色が 種類あって、各頂点は のいずれかの色で塗られている。このとき、以下の条件を満たすような色の組 () の個数を求めよ。 個の頂点のうち、色…

面白い。けど問題文長い...。問題概要を短くまとめてみた。 問題へのリンク 問題概要 正の整数 が与えられる。 あなたは、 以上の整数を 個用意する ( とする)。この 個の整数のスコアを、以下の条件を満たす最小の整数 として定める。 は のいずれでも割り…