ABC
jjjjjjjtgpptmjjさんのAtCoder Beginner Contest 218での成績：2007位パフォーマンス：1136相当レーティング：1428→1402 (-26) :(#AtCoder #ABC218 https://t.co/gykafsug4z :(— naga (@long_ng_cp) September 11, 2021 A - Weather Forecast 解説 実装 B - …
D - Squares 問題へのリンク 解説 X(答え) 重ならないという現象の数え上げは難しいので、重なる(X1)を数えて全体から引く X = X0 - X1 X0 = (N-A+1)2 * (N-B+1)2 X1(重なる) 重なるという現象は、AとBの満たす区間がxでもyでも重なるときで対称性から、 xで…
E - Throne 拡張ユークリッドの互除法による逆元計算 NとKが互いに素のとき NとKが互いに素でないとき 実装 中国剰余定理 実装 E - Throne 問題へのリンク を満たす最小の整数を求めよ。 拡張ユークリッドの互除法による逆元計算 まず、与式をと変形すること…
ABCE青パフォでした。Dが難しかったですね・・・。 jjjjjjjtgpptmjjさんのHHKB プログラミングコンテスト 2020での成績：571位パフォーマンス：1728相当レーティング：1443→1475 (+32) :)#AtCoder #HHKBプログラミングコンテスト2020 https://t.co/hTuwuCdLL…
A - Plural Form 解説 実装 B - Go to Jail 解説 実装 C - A x B + C 解説 実装 D - Leaping Tak 解説 実装 E - Sequence Sum 解説 実装 F - Simplified Reversi A - Plural Form 問題へのリンク 解説 末尾を確認します。 実装 int main() { string S; cin >…
5完で水パフォでした。青パフォstreakが切れて悲しいですね。 jjjjjjjtgpptmjjさんのAtCoder Beginner Contest 178での成績：864位パフォーマンス：1597相当レーティング：1412→1432 (+20) :)Highestを更新しました！#AtCoder #ABC178 https://t.co/JlM3Zncq…
5完2ペナで青パフォでした。初の青パフォstreak2で嬉しいです。 jjjjjjjtgpptmjjさんのAtCoder Beginner Contest 177での成績：605位パフォーマンス：1732相当レーティング：1371→1412 (+41) :)Highestを更新し、3 級になりました！#AtCoder #ABC177 https:/…
D - Wizard in Maze 解説 実装 E - Bomber 解説 実装 列の最大をとる range max queryのセグ木 F - Brave CHAIN 50分5完で青パフォでした。 そういえば競プロを始めてから2年が経っていました。 D - Wizard in Maze 問題へのリンク 解説 見た瞬間にグリッド…
Eまでノーペナ30分だったのにF既出を検索できずにしょっぱいパフォを取ってしまいました。もったいなかったです。 jjjjjjjtgpptmjjさんのAtCoder Beginner Contest 174での成績：1161位パフォーマンス：1476相当レーティング：1307→1325 (+18) :)#AtCoder #A…
C - 収集王 解説 実装 C - 収集王 問題へのリンク 解説 行にある点の個数が個のとき、列が個のとき和がになりそうなところから考察を進める。 ここで、列が個の列の個数を追加すれば良さそうだが、ここに罠がある。その列に点があるときはその列は、点がない…
問題へのリンク 解説 実装 公式解説 解説 公式解説とは異なる方針でACしたので記録を残しておきます。 まず、いわゆる主客転倒（寄与ゲー）と呼ばれる問題だと捉えます。 今回求めたいのは、の並びのうち、表のコインの数の期待値ですが、 これを期待値では…
問題へのリンク 解説 まず、「閉路のない無向グラフにおいて、連結成分数 = 頂点数 - 辺数」が成り立つことを使います。 すると、問題は以下のように言い換えられます。 頂点数は の計算でで求められます。は区間の長さです。 辺数に関しては、について考え…
24分4完水パフォでした。少しhighestを更新しましたが、Eの実装で凡ミスしていて悲しくなりました。 A - Payment 解説 実装 B - Judge Status Summary 解説 実装 C - H and V 解説 実装 D - Chat in a Circle 解説 実装 E - Multiplication 4 記事を分けまし…
問題へのリンク 解説 まずの場合は調整しようがないのでやります。負の数が奇数個あったら負にします。 以降はとします。 が奇数の場合、正の数が存在するならその最大値をまず使うことにします。 すると、以降に選ぶ数が偶数個になります。 正の数が存在し…
解説 問題の言い換え 面積Sの計算 登場回数Cの数え上げ ~ xとyは独立 ~ シグマの計算 実装 問題へのリンク 解説 問題の言い換え 数え上げの典型として、「問われている対象を別のものの数え上げで考える」という方針があります。今回もその例に漏れず、出て…
E - NEQ 問題文 制約 解説 実装 E - NEQ 問題へのリンク 問題文 以上以下の整数からなる長さの数列との組であって、以下の条件をすべて満たすものの個数を求めよ。 なる任意のについて なる任意のについてかつ 制約 解説 まず、対称性から、数列を固定して考…
72分5完2ペナで青パフォでした。数え上げを少し練習してたのがよかったんだと思います。 C - Tsundoku 解説 実装 D - Sum of Divisors 解説 実装 E - NEQ F - Unfair Nim C - Tsundoku 解説 令和ABC-Cなのでとで小さい方を取っていく貪欲解を考えますが、す…
3完で緑パフォでした。Dでvectorやmapを使うのをやめたら通ったので泣きそうです。 -> 追記：vectorは問題なくて、mapのlogがTLEの原因でした。 提出へのリンク C - Fobidden List D - Not Divisible C - Fobidden List 0 ~ 1000くらいまで、確認します。に…
atcoder.jp 個数と和が同じなら同じ数、個数が異なるなら和が同じでも異なる数にカウントする問題。 個選ぶと決め打ったとき、できる数は 前個の和と、後ろ個の和の間すべて である。 これは簡単な帰納法で証明できる。 int main() { ll N, K; cin >> N >> K…
4完で水パフォでした。長針は離散的に動きません。余弦定理がTwitterトレンドに入っていて笑っていました。 提出へのリンク 順位表 A - ∴ (Therefore) B - ... (Triple Dots) C - : (Colon) D - .. (Double Dots) E - ∙ (Bullet) F - Bracket Sequencing A -…
5完で青パフォでした。ムーブ的にはよかったと思います。 提出へのリンク 順位表 A - Registration B - Easy Linear Programming C - Skill Up D - Teleporter E - Colorful Blocks F - Bracket Sequencing A - Registration pop_back()するのが最適っぽいで…
atcoder.jp 広義単調増加列の数え上げ。 これなので、 coonevo.hatenablog.com
E - Rotation Matching 解説 まず操作ですが、人の数字割り当てが回転するのではなく、対戦場の割り当てが回転していくと考えても同じことです。 ある対戦場の割り当ては回回転するので、円形に考えると一周することになります。 同じ割り当てになってしまう…
5完で水パフォでした。ムーブがダメダメすぎましたし、Eは無限人が瞬殺していたので解けたことで喜ぶこともできないみたいです。Dは問題文が優しくないなあと思いつつも、よく読まない人が悪いということになるので・・・ A B C D E F A はい B お菓子持って…
AtCoder、AtCoder Beginner Contest、D - Multiple of 2019、E - Two Currencies、拡張ダイクストラ、競技プログラミング
C - Many Requirements 解説 単調増加列の数え上げですが、以下の考え方がわかりやすいです。 maspyさん 単調増加数列の数え上げは、・1 <= x < y < z <= Nbinom(N,3) それはそう・1 <= a <= b <= c <= Nx=a, y=b+1, z=c+2 とおくと、1<=x
AtCoder、AtCoder Beginner Contest、D - Multiple of 2019、E - Two Currencies、拡張ダイクストラ、競技プログラミング
公式想定解と異なる解き方をしたので共有します。 問題概要 解説 方針 DPの定義、初期化、遷移 定義 初期化 遷移 実装 問題概要 問題へのリンク 正の整数が以下の条件を満たすとき、はルンルン数であるといいます。 Xを(leading zeroなしで)十進数表記した際…
参加しました。3完で緑パフォ、緑に戻りました。水切り楽しいですね。 E、Fは読んでないのでそのうち復習します。 My Submissions C chokudaiさんのすごろくの考え方が面白かったです。 C問題、数学の問題といえばそうなんだけど、「無限に長いすごろくがあ…
F - Distributing Integers F - Distributing Integers 問題概要 方針 k = 1パート 更新パート 実装 類題 タイトルの上に全方位DPタグがあると思うので、そこから類題を探してもいいと思います。類題が見たくない人は実装の下まで見ないように注意してくださ…
