D - Squares 問題へのリンク 解説 X(答え) 重ならないという現象の数え上げは難しいので、重なる(X1)を数えて全体から引く X = X0 - X1 X0 = (N-A+1)2 * (N-B+1)2 X1(重なる) 重なるという現象は、AとBの満たす区間がxでもyでも重なるときで対称性から、 xで…

ABCE青パフォでした。Dが難しかったですね・・・。 jjjjjjjtgpptmjjさんのHHKB プログラミングコンテスト 2020での成績：571位パフォーマンス：1728相当レーティング：1443→1475 (+32) :)#AtCoder #HHKBプログラミングコンテスト2020 https://t.co/hTuwuCdLL…

A. Cubes Sorting すべての要素が異なり、逆順に並んでいるとき、バブルソートは最大で回の操作が必要になります。そうでないとき、それ未満で終わります。 void solve(){ int N; cin >> N; vector<ll> a(N); rep(i,N)cin >> a[i]; rep(i,N-1){ if(a[i] <= a[i+1</ll>…

5完で水パフォでした。青パフォstreakが切れて悲しいですね。 jjjjjjjtgpptmjjさんのAtCoder Beginner Contest 178での成績：864位パフォーマンス：1597相当レーティング：1412→1432 (+20) :)Highestを更新しました！#AtCoder #ABC178 https://t.co/JlM3Zncq…

B - RGB Coloring 解説 実装 B - RGB Coloring 問題へのリンク 解説 各マスの状態が4種類ある 無 デフォルトを無だと考えて、そこに得点を割り振っていくと考えると、にするかしないかを独立に決めて、重なったらにすると考えればよいことがわかる。 よって…

問題へのリンク 解説 実装 公式解説 解説 公式解説とは異なる方針でACしたので記録を残しておきます。 まず、いわゆる主客転倒（寄与ゲー）と呼ばれる問題だと捉えます。 今回求めたいのは、の並びのうち、表のコインの数の期待値ですが、 これを期待値では…

問題へのリンク 解説 まず、「閉路のない無向グラフにおいて、連結成分数 = 頂点数 - 辺数」が成り立つことを使います。 すると、問題は以下のように言い換えられます。 頂点数は の計算でで求められます。は区間の長さです。 辺数に関しては、について考え…

問題概要 制約 解説 E1 E2 実装 E1 Easy Version 問題へのリンク E2 Hard Version 問題へのリンク 問題概要 Yuzuはキャンディー個を持っています。人の敵がいて、敵は個キャンディーを持っています。Yuzuは長さの順列の順番に従って敵と闘います。 戦闘では…

解説 問題の言い換え 面積Sの計算 登場回数Cの数え上げ ~ xとyは独立 ~ シグマの計算 実装 問題へのリンク 解説 問題の言い換え 数え上げの典型として、「問われている対象を別のものの数え上げで考える」という方針があります。今回もその例に漏れず、出て…

E - NEQ 問題文 制約 解説 実装 E - NEQ 問題へのリンク 問題文 以上以下の整数からなる長さの数列との組であって、以下の条件をすべて満たすものの個数を求めよ。 なる任意のについて なる任意のについてかつ 制約 解説 まず、対称性から、数列を固定して考…

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

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

公式想定解と異なる解き方をしたので共有します。 問題概要 解説 方針 DPの定義、初期化、遷移 定義 初期化 遷移 実装 問題概要 問題へのリンク 正の整数が以下の条件を満たすとき、はルンルン数であるといいます。 Xを(leading zeroなしで)十進数表記した際…

問題概要 問題へのリンク の盤面が与えられます。個の箱が座標に積み上げられている盤面を初期盤面と呼びます。以下の処理を繰り返し、すべての盤面の高さを揃えるゲームをします。 2つの隣り合う箱の上に一つずつ箱を積み上げる 一つの箱の上に二つの箱を積…

参加しました。 順位表 Sum of Odd Integers 問題概要 解説 提出 Princesses and Princes 問題 問題 入力 出力 解説 提出 Game with Chips 問題概要 解説 提出 D - Infini Path 問題概要 E - Count The Blocks 問題概要 解説 提出 Sum of Odd Integers 問題…

問題へのリンク 問題概要 提出 問題概要 個の約数なので、その性質自体を活かした解法もあるが、今回はあえて一般的な問題として捉え、DPをしてみる。 dp[i][j]: i個目までの素因数で約数の個数がj個 とする。 dp[0][1] = 1として（の約数は個と考える） 個…

AtCoder Beginner Contest 129 E - Sum Equals Xor 解説 提出 解説 a + b = a xor b a + b = a xor b + 2 * (a & b) より a & b = 0 と読み替える a + b <= L以下で、a & b = 0となるaとbの組み合わせの個数を答える問題に変わる。 桁DPをする。 a + bがL未…

AtCoder Begginer Contest 129 E - Sum Equals Xor 解説 提出 解説 a + b = a xor b a + b = a xor b + 2 * (a & b) より a & b = 0 と読み替える a + b <= L以下で、a & b = 0となるaとbの組み合わせの個数を答える問題に変わる。 桁DPをする。 a + bがL未…

参加しました。 A Two Regular Polygons 解説 提出 B Bogosort 解説 提出 C Adding Powers 解説 提出 D Count the Arrays 解説 提出 A Two Regular Polygons 解説 N % M == 0 提出 #include <bits/stdc++.h> using namespace std; #define rep(i,N) for(int i=0;i</bits/stdc++.h>

ABC127 E - Cell Distance 方針 xとyは別に計算してあとで足し合わせてよい もっと言えば、xとyは対称なので、xについて考えればよい 距離は2点間に定義される量なので、K個選ぶとか考えずに、距離dが何回現れるかを考える d=0は考える必要がない dは1 ~ N-1…