二分探索
codeforces.com 問題 You are a given an array 𝑎 of length 𝑛. Find a subarray 𝑎[𝑙..𝑟] with length at least 𝑘 with the largest median. Then, output the maximum median you can get. 解説 まず「中央値がxにできるか」という判定問題をO(N)で解くこと…
2完青パフォでした。ACLはほとんど対策できてなかったのですが、自分のレート帯なら関係ないだろうと思って考察を頑張りました。Bでコンテスト前にたまたま目にした拡張ユークリッドの互除法が使える問題が出て、運がよかったです。 jjjjjjjtgpptmjjさんのAC…
B - Minimum Sum 解説 実装 B - Minimum Sum 問題へのリンク 解説 区間がたくさん与えられるので、その中のある値の和を求めよという問題は多くありますが、基本的に区間をすべて列挙して解くことはできません。今回も例によってそのパターンで、ある値が、…
問題概要 制約 解説 E1 E2 実装 E1 Easy Version 問題へのリンク E2 Hard Version 問題へのリンク 問題概要 Yuzuはキャンディー個を持っています。人の敵がいて、敵は個キャンディーを持っています。Yuzuは長さの順列の順番に従って敵と闘います。 戦闘では…
72分5完2ペナで青パフォでした。数え上げを少し練習してたのがよかったんだと思います。 C - Tsundoku 解説 実装 D - Sum of Divisors 解説 実装 E - NEQ F - Unfair Nim C - Tsundoku 解説 令和ABC-Cなのでとで小さい方を取っていく貪欲解を考えますが、す…
コンテスト参加記はこちら。 coonevo.hatenablog.com D - Multiset 問題概要 解説 D - Multiset 問題へのリンク 問題概要 集合の初期状態が与えられる。 以下2つのクエリを処理したあと、残っている要素のいずれかを出力せよ(空の場合は-1)。 要素を追加。…
コンテストへのリンク Gがわかりません・・・。 A B C D E F G H A 問題へのリンク として一辺は。 void solve() { ll a, b; cin >> a >> b; if(a >= b)swap(a,b); if(2*a >= b){ cout << 2 * a * 2 * a << endl; } else{ cout << b*b << endl; } } B 問題へ…
コンテストへのリンク 参加しました。結果は以下です。 (プレテスト中) Dができて嬉しかったです。 A B C1 C2 D E A 問題へのリンク 周期性があるのでごちゃごちゃやるといいです(こういうの嫌い) void solve(){ ll a,b,c,d; cin >> a >> b >> c >> d; i…
問題へのリンク 問題概要 制約 解説 問題概要 問題が問あり、番目の問題のスコアはである。人が独立に問選び、それらのスコアをずつ上げる。人の選択後、スコアの降順に並べられ、最初の問が採用される。採用される可能性のある問題は何問あるか? 制約 解説…
公式想定解と異なる解き方をしたので共有します。 問題概要 解説 方針 DPの定義、初期化、遷移 定義 初期化 遷移 実装 問題概要 問題へのリンク 正の整数が以下の条件を満たすとき、はルンルン数であるといいます。 Xを(leading zeroなしで)十進数表記した際…
参加しました。3完で緑パフォ、緑に戻りました。水切り楽しいですね。 E、Fは読んでないのでそのうち復習します。 My Submissions C chokudaiさんのすごろくの考え方が面白かったです。 C問題、数学の問題といえばそうなんだけど、「無限に長いすごろくがあ…
問題 方針 単調性 判定問題 区間の中央値がX以上になる条件 区間列挙の解決策 実装 問題 長さNの数列が与えられる。この中の全ての連続部分列における中央値の中央値を求めよ。 問題へのリンク 方針 単調性 二分探索する。 中央値がX以上となる区間の数が全…
AtCoder Beginner Contest 091 ABC091 D - Two Sequences AtCoder Beginner Contest 091 ABC091 D - Two Sequences 問題概要 解説 方針 解答方法 提出 問題概要 長さNの二つの数列a,bがある。これらの全ての組み合わせa_i + b_jに対して、全てxorをとったと…
ABC149 E - Handshake 問題へのリンク ABC149 E - Handshake 問題概要 解説 提出 問題概要 i,jをM回選んだとき、A[i] + A[j]の最大値を答えよ。ただし、同じi,jを選べない。 解説 方針として、全てのi,jを列挙して大きい方からM個とってくれば良いことがわか…
Educational Codeforces Round 81 (Rated for Div. 2)にVirtual参加しました。 A - Display The Number 問題概要 解説 提出 B - Infinite Prefixes 問題概要 解説 提出 C - Obtain The String 問題概要 解説 提出 D - Same GCDs 問題概要 解説 提出 参考 A -…
ABC146に参加しました A - Can't Wait for Holiday mapで管理すると楽そうです。 提出 B - ROT N アルファベットをN個スライドする問題。 ('S[i] - 'A' + N) % 26 + 'A' をすると通ります。 提出 C - Buy an Integer X円で買える数字の最大値を求める問題。 …