式変形
面白かった！ 一見 MST の問題に見えるけど、主客転倒すると Dijkstra だった。 問題へのリンク（仮） 問題概要 頂点数 、辺数 の連結な単純無向グラフが与えられる。頂点 には重み がついていて、辺 には重み がついている。このグラフの全域木のコストを次…
ちょっと工夫が必要な感じ 問題へのリンク 問題概要 長さ 正整数列 と、正の整数 が与えられる。 数列の区間であって、総和を で割った余りと、区間内に含まれる要素の個数とが等しいものの個数を求めよ。 制約 考えたこと 結構ややこしい。落ち着いて条件を…
上手に式変形しよう！ 問題へのリンク 問題概要 正の整数からなるサイズ の数列 が与えられる。次の条件を満たす組 の個数を求めよ。 制約 考えたこと 条件が不思議だ。普通は よりも の方が大きいことが多いのに、 となる条件を問うとは。 さて、この手の数…
これ面白かった！ 問題へのリンク 問題概要 数列 が与えられる。この数列の連続する部分数列について「その総和を で割った余り」を考える。 連続する部分数列をすべて考えたときの、「その総和を で割った余り」の総和を求めよ。 制約 考えたこと この問題…
maspy さんの次のツイートがすべて！！ F(cnt,sum) という組と定数加算作用が遅延セグ木にのるというのはよく知られていると思いますが、これは要素に対する (0乗和, 1乗和) と解釈できて、組 (0,1,...,k 乗和) などに一般化できます。今回は要素 (x,y) に対…
愚直に や を求めようとすると、色んな理由でおかしくなってしまう。数学的に綺麗に処理しよう！ 問題へのリンク 問題概要 整数 が与えられる。 と の大小関係を求めよ (大きい、小さい、等しい)。 制約 考えたこと や はまともに計算するとものすごい桁数に…
コンテスト中には通しきれなかった。流石に疲れていて頭が働かなかった......これはメモ代わりに記す。 問題へのリンク 問題概要 整数値 が等確率で出てくるルーレットがある。 先手と後手が交互にルーレットを回す すべての整数値が揃ったら終了である すで…
ちょっとした式変形のスキルも要求される。 問題へのリンク 問題概要 コンテストの参加回数 、表示レーティングは次のようになる。 のとき：内部レーティングに一致する のとき：内部レーティングから を引いた値となる 高橋君のコンテスト参加回数が で表示…
面白かった！ 問題へのリンク 問題概要 個の正の整数 を 個のグループに分ける。ただし、どのグループの要素数も 1 個以上 2 個以下でなければならない。 最適なグループ分けをしたときの、各グループの要素の総和の二乗の総和の最小値を求めよ。 制約 考え…
式がいかめしくて戸惑うけど、DP 自体は比較的単純 問題へのリンク 問題概要 個の値 が与えられる。 これらの中から順序を保っていくつか選ぶ。選び方のスコアは、 個の整数 を選んだとしたとき、 で与えられる。このスコアの最大値を求めよ。 制約 考えたこ…
Polynomial Taylor Shift を履修したので、簡単にまとめてみます。例によって、Yosupo Library Checker の 問題 を通します。 なお、Polynomial Taylor Shift の解法は、単なるライブラリ整備の一環とみなすというよりは、その導出過程をぜひ押さえておきた…
FPS + 負の二項係数 問題へのリンク 問題概要 長さが で総和が であるような、正の整数のみからなる数列 すべてについての の総和を 998244353 で割ったあまりを求めよ ( ケース)。 制約 解法 (1)：FPS 求めたいものは である。これはちゃんと計算すると、 …
意外と頭がこんがらがるかもしれないですね。100 点問題で必須となるテクニックではないですが、ソートすると考えやすいと思います。 問題へのリンク 問題概要 個の整数 が与えられる。 これら 個の整数を適切に並び替えることで、等差数列にすることが可能…
面白かった！ ジャッジページ 問題文 問題概要 人の走者がいる。 人の中から 人を選んで、100m 走る × 3 の 300m リレーを行う。 人目の 100m 走のタイムは 秒、バトンパスタイムは 秒で与えられる。リレーの走者として、 の 人を選んでこの順に走るときの総…
前回の ABC に続いて、D 問題が数学っぽい。でも実際には今回は探索問題ですね。 問題へのリンク 問題概要 非負整数 を用いて と表せる整数 を「特別数」と呼ぶことにします。 非負整数 が与えられますので、 以上である最小の「特別数」を求めてください。 …
問題を見て「めっちゃ数学やん！！なにこれ！？？」となった人は多いと思う！！！ でも落ち着いて整理して取り組めば解けるので、落ち着くことが大事そう。 もしくは、ライブラリで殴る！！！！！！ 問題へのリンク 問題概要 つの多項式 次の多項式 次の多項…
いろんな方法が考えられそう！ 問題へのリンク 問題概要 個の整数 が与えられる。 を満たすすべての の組に対する の総和を求めよ。 制約 考えたこと 絶対値のままだと厄介。ちょっと工夫する。まず、数列 の並びを入れ替えたとしても答えが変わらないことに…
ABC C にありそうな教育的問題！ 問題へのリンク editorial 問題概要 正の整数 が与えられる。 かつ を満たすすべての整数組 についての の総和を 1000000007 で割ったあまりを求めよ。 制約 (テストケース数) 考えたこと 結局、 を計算すればよい。それぞれ…
色んな解法がありそう。 問題へのリンク 問題概要 個の正の整数 が与えられる。 を満たすすべての非負整数列 に対する の総和を 1000000007 で割ったあまりを求めよ。 制約 解法 (1)：経路数への帰着 (僕の解法) 二項係数を扱う方法論として、経路数へと帰着…
面白かった。でも茶色ってことは流石になさそう......(コンテスト中は、全部の XOR 和が 0 かどうかを判定する、という嘘解法が AC になっていたらしい) 問題へのリンク 問題概要 個の非負整数 が与えられる。これらを円環状に上手に並べることで、 「どの整…
伝説のりんごさんセットの 1 問目 問題へのリンク 問題概要 二次元座標平面上において、 座標と 座標のうちの少なくとも一方が整数であるような点からなる集合を「道路」と呼ぶ。 道路上の 2 点 のユークリッド距離が実数 で与えられる。 点 から道路のみを…
よくある式変形問題 問題へのリンク 問題概要 3 つの正の整数 が与えられる。 を 998244353 で割ったあまりを求めよ。 制約 考えたこと 求める値は に一致する。あとは modint を活用すれば求められる！ コード #include <bits/stdc++.h> using namespace std; // modint te</bits/stdc++.h>…
コンテスト本番、こっちをやればよかった...ところで解説が天才すぎる！ 問題へのリンク editorial 問題概要 個の部品と、 個の接続用部品とがある。これらを用いてフィギュアを作ろうとしている。 番目の部品には 個の穴がついている。接続用部品は、2 個の…
形式的冪級数すごい 問題へのリンク 問題概要 個の整数 が与えられる。各 に対して を 998244353 で割ったあまりを求めよ。 制約 考えたこと いっそ 次までではなく、無限級数にしてしまう。そして として、 の各次数の係数を求めたい。ここで、 と計算でき…
「要素を 1 個ずつ追加していくときに値がどう変化していくか」を観察する方向でずっと考えていて迷走してしまった... 問題へのリンク 問題概要 正の整数 と、 個の整数 が与えられる。 に対して、 の値を 998244353 で割ったあまりを求めよ。 制約 解法 個…
茶色 diff にはなると思ったけど、灰色 diff だった...「/2」が必要と感じて詰まる人も多いと思ったのに... 問題へのリンク 問題概要 個の整数 が与えられる。 を満たすすべての に対しての の総和を 1000000007 で割ったあまりを求めよ。 制約 考えたこと …
XOR について完全理解することが求められる...！ 問題へのリンク 問題概要 を偶数とする。 個の 0 以上の整数 であって、以下の条件を満たすものを求めよ。 個の整数のうち 番目を除外した 個の整数の XOR 和が となる 制約 考えたこと が偶数というのが不気…
一瞬ヤバそうに見えるけど、落ち着いて考えると、 くらいまで調べればいいという 問題へのリンク 問題概要 正の整数 が与えられるので、 を満たす整数 を一つ求めよ。 制約 考えたこと こういうの、基本的には全探索。でも という制約を見ると、 あたりまで…
余弦定理を使うか、座標を求めるか、、、いずれにしても三角関数の素養を要求する問題。 問題へのリンク 問題概要 時計の時針と分針があって、それぞれ長さは , となっている。 時 分の段階において、時針の先端と分針の先端との距離がどのようになっている…
これかーーー数学ゲーじゃないかと物議を醸した問題。でも普通にいい問題だと思う！！ 問題へのリンク 問題概要 底面が一辺 cm の正方形であり、高さが cm であるような直方体型の水筒に、体積 cm3 の水を入れる。 底面の正方形の一辺を軸として、この水筒を…
