入力が定数個
この平方分割のやり方はちゃんとマスターしたい 問題へのリンク 問題概要 種類のレベル 1 の宝石がある。各種類のレベル 1 の宝石は無限個ある。 個の宝石を合成することで、レベル の宝石を作ることができる。ただし、その 個の宝石は次の条件を満たす必要…
floor sum のいい感じの練習問題！ 問題へのリンク 問題概要 正整数 が与えられる。 非負整数 を用いて という形で表せる正の整数のうち、 番目に小さいものを求めよ。 ( 個の入力ケースが与えられる) 制約 考えたこと いかにも二分探索という問題。次の判定…
残り 1 分でなんとか通せた。 問題へのリンク 問題概要 頂点数 の連結な単純無向グラフ (頂点番号は であって、次の条件を満たすものの個数を で割ったあまりを求めよ。 なお、ここで、頂点 から各頂点 までの最短距離を としている。 制約 考えたこと グラ…
緑色下位 diff かなと思っていたのですが、これが茶色なのすごいですね！ 問題へのリンク 前提知識 エラトステネスのふるい 二分探索 問題概要 素数 を用いて と表される数を「250 に似た数」であると言います。 整数 が与えられますので、 以上 以下の「250…
XOR は 2 回やると元に戻る！！！(素振り！) 問題へのリンク 問題概要 非負整数 が与えられます。 ^ = を満たす整数 を求めてください。 制約 XOR とは XOR 演算は、AND と OR と同じく、ビット (整数) 同士で定義される演算です。ビットについては次の記事…
入出力の練習をしましょう。 問題へのリンク editorial 問題概要 3 人の生徒がそれぞれ 個、 個、 個の金平糖をもらいました。 これからそれぞれの生徒たちに何個かの金平糖を追加で渡すことで、3 人の生徒がもらった金平糖の個数が等しくなるようにしたいと…
原始根が絡む問題は時々出るイメージですね。 問題へのリンク 問題概要 素数 が与えられます。 次の条件を満たす整数 の組の個数を 998244353 で割ったあまりを求めてください。 ある正の整数 が存在して、 が成立する 制約 は素数 考えたこと 整数問題とい…
これほどシンプルな問題がグラフ最短路問題になるのは感動的ですね！ 問題へのリンク 問題概要 の正の倍数をすべて考えたときの、各桁の和として考えられる最小値を求めてください。 制約 うまく数字を並べるゲームと捉える の倍数をひたすら試す方法をまず…
これ FFT を使えば でもできるね。実際は で間に合う。 ジャッジページ 問題文 問題概要 正の素数 と、正の整数 が与えられる。 は 以上 以下の整数 を満たすような の組の個数を求めよ。 制約 は素数 考えたこと まずは次のように集計処理をしよう。このよ…
最初は二次元 FFT が必要な気分になっていて右往左往していた。個数制限なしナップサック問題になるのは面白かった！ 問題へのリンク 問題概要 正の整数 が与えられる。長さ の非負整数列 であって という条件を満たすものの個数を、1000000007 で割ったあま…
これは天才パズル！！！ 問題へのリンク 問題概要 のグリッドに 0, 1 の数値を書き込む方法であって、 どの行をみても、それに含まれる 0 の個数と 1 の個数のうちの小さい方の個数が どの列をみても、それに含まれる 0 の個数と 1 の個数のうちの小さい方の…
これまた楽しい数え上げ！！！ 解説があまりにも天才だけど、解説の方法が思いつかなくても一応できた！！！ 問題へのリンク editorial 解説放送 問題概要 "A", "B", "C" のみからなる長さ の文字列であって、以下の条件を満たすものの個数を 998244353 で割…
こういう数え上げ、大好きすぎる！！！ 問題へのリンク 問題概要 長さ の数列 がある。初期状態ではすべての値が 0 となっている。この数列に以下の操作をちょうど 回行って得られる数列が何通りあるか、998244353 で割ったあまりを求めよ。 となる を選んで…
構築楽しかった 問題へのリンク editorial 問題概要 のグリッド上に のドミノを互いに重ならないように配置していく。 どの行・列を見ても、その行・列上にある のドミノの個数が互いに等しいような配置を求めよ。存在しない場合は "-1" を出力せよ。 制約 …
少し慎重に 問題へのリンク 問題概要 以下の正の整数の 10 進法での各桁の和の最大値を求めよ。 制約 考えたこと とかだったら答えは になりそうだ。一般に、 の形をしたものだけ考えれば良さそう。仮に とかが最適解だったとしても、その場合は として、 も…
Pell 方程式！！！ 問題へのリンク editorial (day2-E) 問題概要 (意訳) 正の整数 が与えられる。 を正の整数として、 の値が最小となるような を 1 つ求めよ。 制約 考えたこと が平方数のときは として、 が答えとなる (最適値は 0)。 が平方数でないとき…
面白い。けど問題文長い...。問題概要を短くまとめてみた。 問題へのリンク 問題概要 正の整数 が与えられる。 あなたは、 以上の整数を 個用意する ( とする)。この 個の整数のスコアを、以下の条件を満たす最小の整数 として定める。 は のいずれでも割り…
貴重な区間篩の問題 問題へのリンク editorial 問題概要 2 つの正の整数 が与えられる。以下の条件を満たす整数 の個数を求めよ。 の相異なる素因数の個数が素数個 制約 考えたこと が小さいので、それを活かした解法が考えられそう。具体的には区間篩が使え…
伝説のりんごさんセットの 1 問目 問題へのリンク 問題概要 二次元座標平面上において、 座標と 座標のうちの少なくとも一方が整数であるような点からなる集合を「道路」と呼ぶ。 道路上の 2 点 のユークリッド距離が実数 で与えられる。 点 から道路のみを…
いろんな DP が考えられそう！ 問題へのリンク editorial 問題概要 正整数 が与えらる。以下の条件を全て満たす有理数の多重集合は何種類存在するか、998244353 で割ったあまりを求めよ。 多重集合の要素数は 多重集合の要素の総和は 多重集合の要素は全て (…
よくある式変形問題 問題へのリンク 問題概要 3 つの正の整数 が与えられる。 を 998244353 で割ったあまりを求めよ。 制約 考えたこと 求める値は に一致する。あとは modint を活用すれば求められる！ コード #include <bits/stdc++.h> using namespace std; // modint te</bits/stdc++.h>…
山登り法で見つかった！スコアが下がっていくのを眺めるの快感！ 問題へのリンク 問題概要 のグリッドに以下の条件を満たすように英小文字を入れよ。 横方向、縦方向に連結しているマス目を抜き出してできる文字列は 個ある そのすべてが互いに相異なる これ…
こういう条件を言い換えながら数え上げる問題好き！ 問題へのリンク 問題概要 タプリスちゃんは現在、長さ 1 の数列 を持っている。 タプリスちゃんは に対して、以下のいずれかの操作を選んで行うことを 回繰り返すことにした。 の末尾に または を追加する…
5 + 7 + 5 = 17 なの、よくできてる！ 問題へのリンク 問題概要 正の整数 が与えられる。 以上 以下の数値からなる長さ の数列 であって、以下の条件を満たすものの個数を 1000000007 で割ったあまりを求めよ。 整数 が存在して、 の区間 の総和が の区間 の…
このセットの writer をしていました 問題へのリンク 問題概要 を並び替えてできる数列 は 通りあるが、そのうち以下の条件を満たすものが何通りあるかを、1000000007 で割ったあまりを求めよ。 を満たすような がちょうど 個 を満たすような がちょうど 個 …
最初、「これは本当に AGC か！？？」となってた 問題へのリンク 問題概要 以上 以下の整数の中からいくつか選んで、OR 和をとってできる値が何通りあるか求めよ。 制約 考えたこと 一見するとこどふぉっぽい見た目の問題だけど、実はすごく AGC っぽい感じ…
1, 2, ..., i のうちのいくつか選んで和を取った値は、連続した自然数を作れる 問題へのリンク 問題概要 からいくつか選んでできる総和が となるようにしたい。 選んだ数の最大値が最小となるような場合の数を求めよ。 制約 考えたこと 一般に、 によって作…
すごく NTT したくなる 問題へのリンク 問題概要 正の整数 が与えられる。 をそれぞれ 個以上 個以下とってくる方法のうち、平均が となるものの個数を素数 で割ったあまりを、各 に対して求めよ。 制約 考えたこと まず、平均制約を次のように言い換える。…
ならば になるネタ、結構見る！ 問題へのリンク 問題概要 数列 があって、初期状態では となっている。ここで 2 つの正の整数の組 に対して正の整数 を返す関数 を考える。 次の条件を満たす操作列を構築せよ。1 つの操作は整数 で与えられ、 , をともに で…
ゴリ (prd さん) と一緒に出て楽しかったコンテスト。 そして「グラフのサイクル・パスの列挙」に関する問題は北大セットの定番というイメージになってきた。 問題へのリンク 問題概要 下図のような 角錐が与えられる (底面が 角形で "頂点" の頂点番号を 0 …
