[AtCoder] ABC 158 C – Tax Increase
消費税を題材にした問題ですね。全探索をするのが楽ですが、ここでは別の解き方をしようと思います。
\( A \) に着目\( A \) に着目すると、
\
を満たす \( x \) を求めれば ...
[AtCoder] ABC 156 E – Roaming
部屋 \( i \) にいる人の数を \( a_i \) とすると、
\
が成り立ちます。このとき、\( a_i \geq 0 \) を満たす整数解は、\( {}_{2n – 1} \mat ...
[AtCoder] ABC 156 D – Bouquet
二項係数の剰余に関する問題です。二項係数の和は、
\
となるので、花束の種類は \( 2^n – 1 \) 通りあります。したがって、求める答えは、\( 2^n – 1 R ...
[AtCoder] ABC 156 C – Rally
問題は最小二乗法に関するものなので、最適な座標は平均値となります。最小二乗法の解説が詳しいです。
コード#include <bits/stdc++.h>using namespace std;typedef lon ...
[AtCoder] ABC 154 D – Dice in Line
サイコロの出る目が \( a \) まであるとき、このサイコロの出る目の期待値は、
\
となります。したがって、累積和などを用いて最大となる値を全探索します。
コード#include <bi ...
[AtCoder] ABC 153 D – Caracal vs Monster
モンスターの体力が \( H \) から \( 1 \) になるまでのモンスターの体力の種類を考えます。このとき、\( i \) 番目に大きい体力を \( H_i \) とします。ここで、\( H_1 = H \) であり、\ ...
[Codeforces] Codeforces Round #614 (Div. 2) B. JOE is on TV!
\( i \) 回目の質問で脱落する人数を \( a_i \) とし、\( a_i \) の累積和 \( s_i \) を \( s_i = a_1 + a_2 + \cdots a_i \) とします。このとき、得られる賞金 ...
[AtCoder] ABC 152 D – Handstand 2
\( a(i, j) \) を先頭の数字が \( i \) で末尾が \( j \) である \( N \) 以下の正の整数の個数とします。これをもちいて、求める答えは、
\
となります。
コード ...
[AtCoder] ABC 152 C – Low Elements
\( 1 \leq j \leq i \) において、\( P_i \leq P_j \) が成り立つことを確認するには、\( P_j \) の最小値が条件を満たしているかどうかを調べれば良いです。よって、最小値を ...
[AtCoder] キーエンス プログラミング コンテスト 2020 C – Subarray Sum
\( 0 \leq K \leq N \) という制約なので、この問題は簡単に解くことができます。\( A \) の \( K \) 個の要素が \( S \) を取るとき、\( N – K \) 個の要素をどのよ ...