けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

式変形

AtCoder ARC 174 C - Catastrophic Roulette (青色, 500 点)

コンテスト中には通しきれなかった。流石に疲れていて頭が働かなかった......これはメモ代わりに記す。 問題へのリンク 問題概要 整数値 が等確率で出てくるルーレットがある。 先手と後手が交互にルーレットを回す すべての整数値が揃ったら終了である すで…

AtCoder ARC 167 A - Toasts for Breakfast Party (灰色, 300 点)

面白かった! 問題へのリンク 問題概要 個の正の整数 を 個のグループに分ける。ただし、どのグループの要素数も 1 個以上 2 個以下でなければならない。 最適なグループ分けをしたときの、各グループの要素の総和の二乗の総和の最小値を求めよ。 制約 考え…

AtCoder ABC 327 E - Maximize Ratin (水色, 475 点)

式がいかめしくて戸惑うけど、DP 自体は比較的単純 問題へのリンク 問題概要 個の値 が与えられる。 これらの中から順序を保っていくつか選ぶ。選び方のスコアは、 個の整数 を選んだとしたとき、 で与えられる。このスコアの最大値を求めよ。 制約 考えたこ…

「Polynomial Taylor Shift」に学ぶ畳み込み芸

Polynomial Taylor Shift を履修したので、簡単にまとめてみます。例によって、Yosupo Library Checker の 問題 を通します。 なお、Polynomial Taylor Shift の解法は、単なるライブラリ整備の一環とみなすというよりは、その導出過程をぜひ押さえておきた…

競プロキャンプ2023関西 L - (sum)mer

FPS + 負の二項係数 問題へのリンク 問題概要 長さが で総和が であるような、正の整数のみからなる数列 すべてについての の総和を 998244353 で割ったあまりを求めよ ( ケース)。 制約 解法 (1):FPS 求めたいものは である。これはちゃんと計算すると、 …

AtCoder ABC 201 A - Tiny Arithmetic Sequence (灰色, 100 点)

意外と頭がこんがらがるかもしれないですね。100 点問題で必須となるテクニックではないですが、ソートすると考えやすいと思います。 問題へのリンク 問題概要 個の整数 が与えられる。 これら 個の整数を適切に並び替えることで、等差数列にすることが可能…

JOIG 春合宿 2022 day1-1 Relay (難易度 6)

面白かった! ジャッジページ 問題文 問題概要 人の走者がいる。 人の中から 人を選んで、100m 走る × 3 の 300m リレーを行う。 人目の 100m 走のタイムは 秒、バトンパスタイムは 秒で与えられる。リレーの走者として、 の 人を選んでこの順に走るときの総…

AtCoder ABC 246 D - 2-variable Function (緑色, 400 点)

前回の ABC に続いて、D 問題が数学っぽい。でも実際には今回は探索問題ですね。 問題へのリンク 問題概要 非負整数 を用いて と表せる整数 を「特別数」と呼ぶことにします。 非負整数 が与えられますので、 以上である最小の「特別数」を求めてください。 …

AtCoder ABC 245 D - Polynomial division (緑色, 400 点)

問題を見て「めっちゃ数学やん!!なにこれ!??」となった人は多いと思う!!! でも落ち着いて整理して取り組めば解けるので、落ち着くことが大事そう。 もしくは、ライブラリで殴る!!!!!! 問題へのリンク 問題概要 つの多項式 次の多項式 次の多項…

AtCoder ABC 186 D - Sum of difference (茶色, 400 点)

いろんな方法が考えられそう! 問題へのリンク 問題概要 個の整数 が与えられる。 を満たすすべての の組に対する の総和を求めよ。 制約 考えたこと 絶対値のままだと厄介。ちょっと工夫する。まず、数列 の並びを入れ替えたとしても答えが変わらないことに…

AOJ 3209 Times Square (OUPC 2020 A)

ABC C にありそうな教育的問題! 問題へのリンク editorial 問題概要 正の整数 が与えられる。 かつ を満たすすべての整数組 についての の総和を 1000000007 で割ったあまりを求めよ。 制約 (テストケース数) 考えたこと 結局、 を計算すればよい。それぞれ…

AtCoder ARC 110 D - Binomial Coefficient is Fun (黄色, 600 点)

色んな解法がありそう。 問題へのリンク 問題概要 個の正の整数 が与えられる。 を満たすすべての非負整数列 に対する の総和を 1000000007 で割ったあまりを求めよ。 制約 解法 (1):経路数への帰着 (僕の解法) 二項係数を扱う方法論として、経路数へと帰着…

AtCoder AGC 035 A - XOR Circle (茶色, 300 点)

面白かった。でも茶色ってことは流石になさそう......(コンテスト中は、全部の XOR 和が 0 かどうかを判定する、という嘘解法が AC になっていたらしい) 問題へのリンク 問題概要 個の非負整数 が与えられる。これらを円環状に上手に並べることで、 「どの整…

AOJ 2629 Manhattan (JAG 夏合宿 2014 day2-A) (250 点)

伝説のりんごさんセットの 1 問目 問題へのリンク 問題概要 二次元座標平面上において、 座標と 座標のうちの少なくとも一方が整数であるような点からなる集合を「道路」と呼ぶ。 道路上の 2 点 のユークリッド距離が実数 で与えられる。 点 から道路のみを…

AtCoder ARC 107 A - Simple Math (灰色, 300 点)

よくある式変形問題 問題へのリンク 問題概要 3 つの正の整数 が与えられる。 を 998244353 で割ったあまりを求めよ。 制約 考えたこと 求める値は に一致する。あとは modint を活用すれば求められる! コード #include <bits/stdc++.h> using namespace std; // modint te</bits/stdc++.h>…

AtCoder ARC 106 F - Figures (橙色, 800 点)

コンテスト本番、こっちをやればよかった...ところで解説が天才すぎる! 問題へのリンク editorial 問題概要 個の部品と、 個の接続用部品とがある。これらを用いてフィギュアを作ろうとしている。 番目の部品には 個の穴がついている。接続用部品は、2 個の…

yukicoder No.1145 Sums of Powers

形式的冪級数すごい 問題へのリンク 問題概要 個の整数 が与えられる。各 に対して を 998244353 で割ったあまりを求めよ。 制約 考えたこと いっそ 次までではなく、無限級数にしてしまう。そして として、 の各次数の係数を求めたい。ここで、 と計算でき…

AtCoder ARC 106 D - Powers (青色, 600 点)

「要素を 1 個ずつ追加していくときに値がどう変化していくか」を観察する方向でずっと考えていて迷走してしまった... 問題へのリンク 問題概要 正の整数 と、 個の整数 が与えられる。 に対して、 の値を 998244353 で割ったあまりを求めよ。 制約 解法 個…

AtCoder ABC 177 C - Sum of product of pairs (灰色, 300 点)

茶色 diff にはなると思ったけど、灰色 diff だった...「/2」が必要と感じて詰まる人も多いと思ったのに... 問題へのリンク 問題概要 個の整数 が与えられる。 を満たすすべての に対しての の総和を 1000000007 で割ったあまりを求めよ。 制約 考えたこと …

AtCoder ABC 171 E - Red Scarf (茶色, 500 点)

XOR について完全理解することが求められる...! 問題へのリンク 問題概要 を偶数とする。 個の 0 以上の整数 であって、以下の条件を満たすものを求めよ。 個の整数のうち 番目を除外した 個の整数の XOR 和が となる 制約 考えたこと が偶数というのが不気…

AtCoder ABC 166 D - I hate Factorization (茶色, 400 点)

一瞬ヤバそうに見えるけど、落ち着いて考えると、 くらいまで調べればいいという 問題へのリンク 問題概要 正の整数 が与えられるので、 を満たす整数 を一つ求めよ。 制約 考えたこと こういうの、基本的には全探索。でも という制約を見ると、 あたりまで…

AtCoder ABC 168 C - : (Colon) (灰色, 300 点)

余弦定理を使うか、座標を求めるか、、、いずれにしても三角関数の素養を要求する問題。 問題へのリンク 問題概要 時計の時針と分針があって、それぞれ長さは , となっている。 時 分の段階において、時針の先端と分針の先端との距離がどのようになっている…

AtCoder ABC 144 D - Water Bottle (茶色, 400 点)

これかーーー数学ゲーじゃないかと物議を醸した問題。でも普通にいい問題だと思う!! 問題へのリンク 問題概要 底面が一辺 cm の正方形であり、高さが cm であるような直方体型の水筒に、体積 cm3 の水を入れる。 底面の正方形の一辺を軸として、この水筒を…

AtCoder ABC 145 D - Knight (緑色, 400 点)

この問題のおかげで、僕の二項係数記事が一躍広く普及することになったのだった。 問題へのリンク 問題概要 二次元グリッドの原点 にチェスのナイトの駒がある。 ナイトの駒はマス にあるとき か のどちらかのマスにのみ動かすことができる。 ナイトの駒をマ…

AtCoder ABC 156 D - Bouquet (緑色, 400 点)

二項係数を使いこなすっ!!! 問題へのリンク 問題概要 種類の花束から何個か選ぶ方法のうち、それが 個でも 個でもないようなものが何通りあるかを 1000000007 で割ったあまりを求めよ。 制約 考えたこと 結局、 個のものからいくつか選ぶ方法 ( 通りある)…

AtCoder ABC 163 D - Sum of Large Numbers (緑色, 400 点)

「作れる数が連続する整数になる」というの、実は結構よくある!! 問題へのリンク 問題概要 個の整数 がある。 これらから 個以上の整数を選んで合計して得られる整数としてありうるものの個数を 1000000007 で割ったあまりを求めよ。 制約 考えたこと まず…

AtCoder ABC 162 D - RGB Triplets (茶色, 400 点)

落ち着いて頭を整理。。。 問題へのリンク 問題概要 'R', 'G', 'B' のみからなる長さ の文字列 が与えられる。 の index の組 であって、 と と はすべて互いに異なる である という条件を満たすものの個数を求めよ。 制約 考えたこと 頭がごっちゃになりそ…

AtCoder AGC 017 A - Biscuits (緑色, 200 点)

これ、知らなくても解ける制約設定だけど、結構大変やね 問題へのリンク 問題概要 個の正の整数 が与えられる。これらからいくつか選ぶ方法のうち、総和を 2 で割ったあまりが となる方法が何通りあるかを求めよ。 制約 考えたこと 一般に 総和が奇数 ⇔ 和の…

AtCoder ABC 154 F - Many Many Paths (青色, 600 点)

すっごく色んな方法がありそう!!! 問題へのリンク 問題概要 正の整数 が与えられる。, を満たすすべての整数 についての の総和を 1000000007 で割ったあまりを求めよ。 制約 考えたこと とりあえず二項係数の計算自体は、適切に前処理をしておけば、 で…

Codeforces Round #616 (Div. 1) C. Prefix Enlightenment (R2400)

Union-Find を使いこなす!!! 問題へのリンク 問題概要 (意訳) 個の 0-1 変数 が与えられていて、最初はそれらの値について特に制約はない。いま、 個の制約が順に与えられる。各制約はそれぞれ 1 つの変数 と 0 か 1 の値 w を指定して、 とする 2 つの変…